본문 바로가기

전체 글149

보석 도둑 - 1202번 백준에서는 파이썬 모듈인 queue모듈을 사용할 수 없다.(이 모듈안에 우선순위큐 모듈이 있다.) 따라서 max heap을 이용하여 풀었다. 보석들은 무게가 작은 순으로, 가방은 적게 담을 수 있는 가방 순으로 정렬을 한다. 가방을 한개씩 검사한다. while 무한루프를 통해 보석을 하나씩 뺀다. 이때, 보석의 무게가 가방의 무게를 넘지 않도록 한다. 만약 while이 정지하면 앞에서 하나씩 뺐던 보석들을 max heap으로 담아둔 heap에서 root위치에 있는 값을 결과 변수에 pop하여 더해준다. 만약 더이상 뺄 보석이 없으면 중지한다. 문제를 풀 때, 답은 맞았는데 시간초과와 런타임에러가 많이 떠서 코드의 구조를 갈아엎어가면서 새로운 구조를 만들어 갔다. 무한루프로 하나씩 꺼내서 담아두는 방식을 .. 2022. 10. 12.
가운데를 말해요 - 1655번 우선순위 큐로 풀다가 시간초과로 해결하지 못하여 근본적인 문제를 찾던 도중 힙 2개를 이용하여 풀면 된다는 것을 알게 되었다. 최대힙과 최소힙에 입력받은 숫자들을 절반씩 나눠 저장한 뒤 중간값만 출력하는 방식이다. 예를들어 문제에 있는 테스트 케이스를 보면서 사람이 직접 푼다고 가정하자 입력으로 7개의 숫자를 입력받는다. 입력 = [ 1, 5, 2, 10, -99, 7, 5] 입력 : 1 >> 출력 : 1 입력 : 5 >> 출력 : 1 입력 : 2 >> 출력 : 2 입력 : 10 >> 출력 : 2 입력 : -99 >> 출력 : 2 입력 : 7 >> 출력 : 2 입력 : 5 >> 출력 : 5 이렇게 표로 표현해볼 수 있다. 여기서 최대힙과 최소힙을 사용하여 입력받는 수들을 2부분으로 쪼갤 것이다. 처음부터.. 2022. 10. 11.
달팽이는 올라가고 싶다 - 2869번 단순하게 반복시키면서 검사하여 찾기는 쉽지만 시간이 오래걸린다. 공식화 시켜서 빠르게 해결해야 할 부분을 계산해버리고 나머지 조금 남은 부분에 대해서만 반복시켜 검사하는 방식으로 해결하였다. a,b,v = map(int,input().split()) day = 0 dis = 0 gap = a-b day += (v-a)//gap v -= gap * day while True: day+=1 dis+=a if v 2022. 10. 10.
요세푸스 문제 0 - 11866번 큐를 이용하여 해결했다. 큐에 1~n까지의 수를 넣고, 큐가 텅 빌때까지 무한루프를 돌려준다. 무한루프 안에서 k-1번 popleft() 후 큐에 다시 append()를 해주고 k번째에 popleft() 를 해주고 결과 배열에 값을 담는다. 큐가 빌 때까지 반복하면된다. from collections import deque n, k = map(int,input().split()) q = deque(i for i in range(n+1)) q.popleft() result = [] while q: for i in range(1,k): a = q.popleft() q.append(a) out = q.popleft() result.append(out) print('') 2022. 10. 10.
좌표 정렬하기 - 11650번 입력 받은 좌표들을 2중 배열에 담아서 그냥 sort()해줘도 답이 나오지만 람다식을 사용해서 풀어보았다. sort()매소드의 key로 람다식을 넣었는데, lambda x: (x[0], x[1]) 을 key로 넣어줬다. 람다식의 의미는 0번 인덱스를 기준으로 정렬하고 같은것은 1번 인덱스를 기준으로 정렬하라는 것이다. n = int(input()) arr = [] for i in range(n): arr.append(list(map(int,input().split()))) # arr.sort() arr.sort(key = lambda x: (x[0], x[1])) for i in arr: for j in i: print(j,end=' ') print() 2022. 10. 10.
체스판 다시 칠하기 - 1018번 입력으로 들어온 체스판에 대하여 8X8크기의 체스판이 될 수 있는 경우를 하나하나 다 조사를 한 뒤 다시 칠해야 할 칸만 배열에 모두 담고 최소값을 출력한다. import sys y_axis, x_axis = map(int,input().split()) graph = [[0]*x_axis for _ in range(y_axis)] visited = [[False]*x_axis for _ in range(y_axis)] result = [] for y in range(y_axis): p = sys.stdin.readline() for x in range(x_axis): graph[y][x] = p[x] for i in range(y_axis-7): for j in range(x_axis-7): black .. 2022. 10. 9.
나이순 정렬 - 10814번 2중 배열을 만들어 담은 후 정렬을 해주면 된다. 인덱스 번호 0번을 기준으로 정렬하는 방법은 lambda 함수를 사용하여 만들어줬다. n = int(input()) arr = [] for _ in range(n): a,b = input().split() arr.append([int(a),b]) arr.sort(key = lambda x : x[0]) for i in arr: for j in i: print(j,end=' ') print() 2022. 10. 9.
영화감독 숌 - 1436번 처음에 만들어지는 수들 간에 규칙을 찾으려고 시간을 쏟았지만 마땅한 규칙을 찾진 못하였다. 그래서 666부터 1씩 더해가며 수에 '666'이 있는지 검사하는 방식을 사용했다. n = int(input()) no = 0 cnt = 665 while no 2022. 10. 5.
적록색약 - 10026번 bfs로 문제를 해결하였다. graph를 2개, bfs함수를 3개를 만들어서 사용했다. 한 for 루프 안에서, 정상인의 결과를 구하고, 적록색약인 사람의 결과를 따로 구해줬다. import sys from collections import deque t = int(input()) graph = [[0] * 101 for _ in range(101)] special_graph = [[0] * 101 for _ in range(101)] d = [[1, 0], [-1, 0], [0, 1], [0, -1]] for y in range(t): inn = sys.stdin.readline() for x in range(t): graph[y][x] = inn[x] special_graph[y][x] = inn[x.. 2022. 10. 4.
미로탐색 - 2178 번 bfs로 해결하였다. 처음 시작점으로부터 마지막 점까지의 계층을 구분짓기 위하여 while 문 다음에 데큐 크기를 중심으로 for 문을 하나 끼워줬다. import sys from collections import deque # y_axis == n, x_axis == m y_axis, x_axis = map(int,input().split()) # 방향 d = [[1,0],[-1,0],[0,1],[0,-1]] graph = [[0]*101 for _ in range(101)] visited = [[False]*101 for _ in range(101)] for y in range(y_axis): a = sys.stdin.readline() for x in range(x_axis): graph[y][x].. 2022. 10. 4.
유기농 배추 - 1012번 BFS로 해결하였다. x, y로 나타낼 수 있는 문제의 어려웠던 점은 2중 배열로 표현을 하거나, 인덱스로 접근할 때, y와 x의 위치를 바꿔서 사용해줘야 한다는 점이다. 가로 5칸, 세로 3칸을 x = 5, y = 3이라 할 수 있다. 이것을 우리가 익숙한 좌표평면행태로 보고 싶다면 arr[5][3] 이 아니라 arr[3][5]모양으로 만들어줘야한다. (파이썬에서는 이런방식으로 array를 표현하지 않지만 편의상 이렇게 적었다.) arr[3][5]를 파이썬 식으로 표현하면 arr [ [ 0 ] * 5 for _ in range(3) ] 이고, arr = [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] 로 보인다. 만약 이 배열에서 x = 2, y = 1 에 .. 2022. 10. 4.
N과 M (2) - 15650 번 백트래킹 함수에서 바로 출력하지 않고 미리 배열에 담아둔 다음 중복되는 것을 빼고 출력해주는 과정을 마지막에 넣어줬다. n, m = map(int,input().split()) arr = [0] * 10 visited = [False] * 10 ans = [] def bt(idx): if idx == m: p = arr[:m] p.sort() ans.append(p) return for i in range(1, n+1): if not visited[i]: arr[idx] = i visited[i] = True bt(idx+1) visited[i] = False bt(0) result = [] for i in ans: if i not in result: for j in i: print(j,end=' ') .. 2022. 10. 3.

티스토리툴바