조준장 개발자 생존기

문제 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 알고리즘 - dfs 탐색을 통해 문제를 수행한다. - 적록색약인이 아닌 사람이 보는 그림의 구역을 dfs 탐색을 통해 찾는다. - 적록색약인이 아닌 사람이 보는 그림의 구역을 찾았다면 적록 색약인 보는 그림으로 바꿔준다.(G -> R) - 바꿔준 그림으로 다시 dfs 탐색을 하여 적록색약인이 보는 그림의 구역을 찾는다. 코드 import sys sys.setrecursionlimit(10 ** 6) # dfs 탐색 def dfs(x, y, c): vi..

문제 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 알고리즘 - bfs로 문제를 수행한다.(dfs 풀이는 좀 더 고민해봐야 할 것 같다.) - 시간 초과를 줄이기 위해 중복되는 곳을 제거한다. - 말이 지날 수 있는 최대 칸을, 칸을 탐색할 때마다 초기화한다. - 말이 지날 수 있는 칸을 상/하/좌/우로 탐색한다. - 범위 내에 있고 알파벳이 중복이 안된다면 탐색한다. 코드 bfs 풀이 import sys # bfs 풀이 # bfs def bfs(): global cnt queue = set([(0,..

문제 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 알고리즘 - LCA 알고리즘으로 풀었다. - dfs 탐색을 통해 루트 노드부터 연결된 노드를 재귀적으로 탐색하여 부모 노드와 그 노드의 레벨을 찾는다. - LCA 알고리즘인 두 노드의 레벨을 맞추고 부모 노드를 찾아가며 공통 조상을 찾는다. 코드 pypy3 해결 # pypy3 해결.. # python3 (94%) 시간초과 import sys sys.setrecursionlimit(10 ** 5) # dfs 탐색 def dfs(x, l): visited[..

문제 20364번: 부동산 다툼 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N = 1: flag = target # 다른 오리의 점유된 땅의 번호를 초기화 # 2로 나눠 루트 땅까지 이동 target //= 2 # 루트 땅까지 이동하면서 점유된 땅을 밟았다면 if flag: print(flag) # 밟은 땅의 번호를 출력 # 그게 아니라면 땅을 점유하고 0을 출력 else: visited[tan] = 1 print(0) github GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법 내가 푼 코딩 테스트 문제와 해결법. Contribute to junjange/CodingTest development by crea..

문제 2078번: 무한이진트리 첫째 줄에 두 정수 A, B(1 ≤ A, B ≤ 2,000,000,000)가 주어진다. 잘못된 입력은 주어지지 않는다고 가정한다. www.acmicpc.net 알고리즘 - 어떤 노드에서 루트 노드로 이동하는 횟수를 카운트하는 방법으로 문제를 수행했다. - a와 b가 1보다 클 때까지 반복하여 한쪽의 이동만을 하게끔 만든다. - 반복이 끝나고 난 후에는 남은 이동 거리를 계산해줘 왼쪽 이동 횟수와 오른쪽 이동 횟수를 출력한다. 코드 import sys a, b = map(int, sys.stdin.readline().split()) l = 0 # 왼쪽 이동 횟수 r = 0 # 오른쪽 이동 횟수 # a와 b가 1보다 클 때까지 반복한다. while a > 1 and b > 1:..

문제 13116번: 30번 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1 www.acmicpc.net 알고리즘 - 문제를 해석하면 결국 두 노드의 가장 가까운 부모 노드를 찾는 것이다. - 부모 노드는 자식 노드에서 2로 나눈 값을 가진다. - 두 노드의 부모 노드가 같을 때까지 반복하여 두 노드의 가장 가까운 부모 노드를 찾는다. 코드 import sys n = int(sys.stdin.readline()) # 테스트 케이스만큼 반복 for _ in range(n): a, b = map(int, sys.stdin.readlin..

문제 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 알고리즘 - 산술 평균은 round() 함수를 통해 수행한다. - 중앙값은 오름차순으로 정렬 후 중간에 있는 정수를 출력한다. - 최빈값은 collection 모듈의 Counter 클래스를 사용한다.(Counter 클래스에서도 most_common() 함수를 사용해도 됨) - 범위는 최댓값에서 최솟값을 빼준 값을 출력한다. 코드 import sys from collections import Counter n = int(sys.stdin.readline()) m = [in..

문제 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 알고리즘 - 각 노드의 부모 노드를 저장한다. - 공통 조상을 구하려는 두 노드는 따로 저장하여 두 노드의 부모 노드들을 찾는다. - 두 노드의 부모 노드를 레벨별로 비교하여 제일 마지막에 같았던 부모 노드를 구한다. - 제일 마지막에 같았던 부모 노드가 가장 가까운 공통 조상 노드가 된다. 코드 import sys t = int(sys.stdin.readline()) # 테스트 케이스만큼 반복 for _..

문제 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 알고리즘 - 후위 순회에서 끝점이 루트 노드인 것을 이용한다. - 중위 순회에서 루트 노드 기준으로 서브 트리 노드가 좌, 우로 나뉘는 것을 이용한다. - 위 두 가지 성질을 이용하여 분할 정복을 재귀적으로 수행한다. - 분할 정복을 수행할 때 각 트리의 루트 노드를 출력한다. 코드 import sys sys.setrecursionlimit(10**9) # 분할 정복 def divide(in_start, in_end, post_start, post_end): # 중위 순회 시작점과 ..

문제 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 알고리즘 - 분할 정복을 통해 문제를 수행한다. - 문제를 보면 중위 순환을 통해 빌딩을 방문한 것을 확인할 수 있다. - 중위 순환이고 완전 이진 트리이기 때문에 중간에 있는 노드가 루트 노드가 된다. - 루트 노드를 찾고 왼쪽 서브 노드와 오른쪽 서브 노드를 나눠 각 트리를 재귀적으로 탐색한다. 코드 import sys sys.setrecursionlimit(10 ** 9) # 분할 정복 def divide(start, end,..