목록코팅테스트/백준 문제 모음 (296)
For Programmer
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cpw4SS/btrrDdsim9u/MSKZkcAiQAVJzD9cdmvk0K/img.png)
큐로 구현하면 간단하게 풀 수 있다. 우선 리스트의 원소들을 큐에 담고 0 부터 k-1번째까지의 원소를 맨뒤로 보내고 k 번째 원소(그렇게 되면 k 번째 원소가 맨앞에 오게 됨으로)를 출력할 리스트에 차근차근 담아준다. from collections import deque N, K = map(int, input().split()) K = K - 1 array = [x for x in range(1, N + 1)] yosepoose = [] # 출력할 요세푸스 배열 선언 queue = deque(array) while True: for i in range(K): # k - 1 번째 까지 돈다. queue.append(queue.popleft()) # 큐의 맨 앞의 원소를 큐의 맨뒤로 순서대로 보낸다. yo..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/lfs0d/btrrB52hUk7/UnZH4q0Nso604NJhLwHCf0/img.png)
이 문제는 bfs와 비슷하게 움직일 수 있는 좌표를 리스트로 저장해놓고 푸는 것이 편하다. 전체 코드는 다음과 같다. omok = [list(map(int, input().split())) for _ in range(19)] dx = [+1, +1, 0, -1] # 행이동 하,우하,우,우상 dy = [0, +1, +1, +1] # 열이동 하,우하,우,우상 def solution(): for k in range(len(omok)): for h in range(len(omok[k])): if omok[k][h] != 0: x, y = k, h # 현재 좌표를 저장 for i in range(4): # 각 방향 이동 nx = x + dx[i] ny = y + dy[i] if nx = len..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/KrW2S/btrrirLjXkk/fQiwINu0Vc3ht8RF9FxEq0/img.png)
1. set 함수 집합의 연산을 이용하여 풀기 nA, nB = map(int, input().split()) A = set(map(int, input().split())) B = set(map(int, input().split())) print(len(A - B)) # 차집합의 길이를 출력 print(*sorted(list(A - B))) # 차집합의 원소를 출력 2. Hash함수(딕셔너리)를 이용하여 풀기 a, b = map(int, input().split()) A, B = {}, {} for n in map(int, input().split()): A[n] = 1 for n in map(int, input().split()): B[n] = 1 # 리스트로 풀면 시간초과가 나지만 해쉬로 풀면 문제를 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/tmeqB/btrqysR81LK/w0G5Br32XrF9WQJ0Ev0uYK/img.png)
해당 문제도 간단한 구현 문제라 max 함수나 sum 함수를 내장함수를 이용하지 않고 직접 구현해서 문제를 풀어보았다. N = int(input()) def max_(score): max_ = 0 for i in score: if i > max_: max_ = i return max_ def sum_(score): sum_ = 0 for i in score: sum_ += i return sum_ score = list(map(int, input().split())) M = max_(score) for i in range(len(score)): score[i] = score[i] / M * 100 print(sum_(score) / N)
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bT8VSo/btrnrjLrDna/dwwT33knKdXrSqVlYhsKdk/img.png)
이 문제는 여태 푼 BFS문제보다는 어려운 문제이다. 이 문제는 크게 2가지를 생각할 수 있어야 한다. 1. 벽을 깬 횟수를 따로 저장해 놓는 리스트를 하나 선언해야 한다. (아래의 코드에서는 dist라고 표현) 2. 입력받은 그래프(방 정보)에서 0을(즉, 연결되어 있는방) 우선적으로 돌도록 큐에 추가할때 따로 appendLeft로 추가를 해주어야 한다는 것이다. 그래야만 0인 방을 우선적으로 돌고 그 후에 1(벽이 있는방)을 돌게 된다. 아래의 코드에 주석을 달아 놓았다. from collections import deque N, M = map(int, input().split()) graph = [] for i in range(M): graph.append(list(map(int, input()))..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/b2TsRi/btrndn0s1fs/oKMO4kMgmHbGS2DKWINnkK/img.png)
이 문제는 다른 숨바꼭질 문제들과 다르게 2*x 로이동할 때 0초가 걸린다. 따라서 0초가 걸리는 경우를 가장먼저 처리해주어야 한다. 그 경우만 잘 생각한다면 쉽게 해결할 수 있다. 다른 분들의 코드를 보면 2*x 처리를 큐에 추가할 때 appendleft 로 처리를 했는데 그렇게 해주어도 된다. from collections import deque def bfs(start): queue = deque([[start, 0]]) while queue: x, cnt = queue.popleft() # find 함수 (자기 노드의 부모를 찾아가는 함수) if x == K: return cnt # 본인의 노드까지 리스트에 넣어 반환 for i in range(3)[::-1]: if i != 2: nx = x +..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/dLIUGm/btrlZvrZ6sy/KKYEImwzutSCSNHCNKUJs1/img.png)
이 문제는 답을 보고도 생각하는데 오래 걸렸던 문제이다. 문제의 핵심은 bfs를 돌기위하여 방문 처리를 이중리스트로 만드는 것이 핵심이다. 즉, visited[화면이모티콘 개수][클립보드 이모티콘 개수] 로 설정하여 각각의 경우마다 방문처리를 해주어야 한다는 것이다. 또한 이모티콘 개수가 범위를 벗어나지 않도록 범위처리를 해주는것도 핵심이다. from collections import deque S = int(input()) queue = deque([[1, 0, 0]]) # 화면의 이모티콘 개수, 클립보드 이모티콘 개수, 연산 횟수 visited = [[False] * 1001 for _ in range(1001)] visited[1][0] = True while queue: screen, clipbo..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cqIPbF/btrlY5tmN2S/W6lrcBQGv7OcwPQKdnlyN0/img.png)
위 문제는 https://ji-gwang.tistory.com/298 문제에서 방문기록을 추가로 출력하라는 문제이다. 그러면 여기서 접근할 수 있는 방법이 방문기록을 찾아나가면서 방문기록을 어딘가에 저장하면 된다는 것이다. 여기서 생각해볼 수 있는 상황이 있다. 위에 2번째 계층 트리 4, 6, 10 에 5를 저장하고 3번째 계층 트리에서 3, 5, 8 에 4, 그리고 5, 7, 12 에 6 마지막으로 9, 11, 20 에 10을 추가하면 된다. 이런식으로 방문기록을 추가해놓고 마지막에는 그 방문기록을 역으로 찾아 나가면서 출력하면 된다. 예를들어 시작점이 5 이고 목적지가 12라고 하자. 위의 그림을 보면 12에 저장되어있는 6을 찾고 그리고 그 6 값을 가지고 거슬러 올라가면서 6에 저장되어있는 5를..