우노

문제 링크 https://www.acmicpc.net/problem/11724 풀이 연결 리스트를 사용해 입력 간선 정보를 양방향으로 저장 1차원 배열을 사용해 각 노드가 어떤 그룹에 속해있는지를 저장 1번 노드부터 마지막 노드까지 순서대로 탐색하며, 현재 노드와 연결된 노드들을 모두 같은 그룹으로 처리 추가 사항 BOJ의 채점 서버에서, Python의 최대 재귀 깊이는 1,000으로 설정되어있습니다. 만약, 재귀 호출 횟수가 해당 값을 넘어가게되면 ReferenceError가 발생하게 됩니다. 따라서, sys.setrecursionlimit()을 사용해 최대 재귀 깊이를 변경해야합니다. 코드 import sys sys.setrecursionlimit(10**6) # 정점의 개수 N과 간선의 개수 M n..

문제 링크 https://www.acmicpc.net/problem/11725 풀이 2차원 연결 리스트를 사용해, 각 노드간 연결 정보를 양방향으로 모두 저장합니다. 루트 노드(1)부터 연결된 노드들을 확인하며, 연결된 노드의 부모 노드가 없을 경우, 현재 노드를 연결된 노드의 부모 노드로 저장합니다. 이후, 연결된 노드들을 기반으로 다시 DFS를 진행합니다. 추가 사항 BOJ의 채점 서버에서, Python의 최대 재귀 깊이는 1,000으로 설정되어있습니다. 재귀 호출 횟수가 해당 값을 넘어가게되면 RecursionError가 발생하게 됩니다. 따라서, sys.setrecursionlimit()을 사용해 최대 재귀 깊이를 변경해야합니다. 코드 import sys sys.setrecursionlimit(1..

문제 링크 https://www.acmicpc.net/problem/1655 풀이 우선, 최대힙을 위한 leftheap과 최소힙을 위한 rightheap을 생성합니다. leftheap은 중간값보다 같거나 작은값으로, rightheap은 중간값보다 큰값으로 유지하기 위함입니다. 이후, 요소들을 순서대로 입력 받으며, 아래 알고리즘을 진행합니다. 현재 leftheap과 righteap의 길이가 같다면, (현재 요소 * -1) 을 leftheap에 삽입하고, 길이가 같지 않다면, (현재 요소)를 rightheap에 삽입합니다. 파이썬의 heapq는 기본적으로 최소 힙만을 제공하기 때문에, -1 을 곱함으로써 leftheap을 최대힙으로 만들 수 있습니다. 이후, leftheap의 루트와 rightheap의 루..

문제 링크 https://www.acmicpc.net/problem/5430 풀이 R 함수 시, 정말 배열의 모든 원소를 뒤집는다면, 시간 초과가 발생합니다. RR -> 그대로이므로 뒤집을 필요가 없습니다. 따라서, 모든 함수에 등장한 R의 개수가 홀수일 경우에만, 모든 함수들을 처리한 뒤, 마지막으로 reverse를 수행하면 됩니다. 함수 중간에 D가 등장하는 경우에는, 현재까지 등장한 R의 개수에 따라, 배열의 모든 원소를 ‘유지’ 또는 ‘reverse’ 한다고 가정한 뒤, deque의 popleft 또는 pop을 사용해 원소를 삭제하면 됩니다. 추가 예외처리 빈 배열(n이 0인 경우)이 입력으로 들어올 수 있습니다. 하지만, 배열이 비어있어도 R 함수는 실행할 수 있습니다. 코드 import sys..

문제 링크 https://www.acmicpc.net/problem/3079 풀이 m명을 심사할 수 있는 최소 시간을 찾기 위해, 이분 탐색의 범위를 [0 ~ m명을 모두 심사했을 때의 가능한 최대 시간]로 잡는게 핵심입니다. 자세한 알고리즘은 하단 예제 코드에 설명되어있습니다. 코드 import sys # 심사대의 개수와 심사를 받는 인원 n, m = map(int, sys.stdin.readline().split()) # 각 심사대의 심사 시간 arr = [] for _ in range(n): arr.append(int(sys.stdin.readline())) # m명을 심사할 수 있는 최소 시간을 찾기 위해 # [0 ~ m명을 모두 심사했을 때의 가능한 최대 시간]을 start, end 범위로 설정..

문제 링크 https://www.acmicpc.net/problem/4307 풀이 "두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다." 해당 문구는 전혀 고려하지 않아도 되는 문제입니다. 예를 들어, 길이 10의 막대기가 있고, 개미 3마리가 순서대로 2, 6, 7의 위치에 존재한다면, 각 개미가 땅으로 떨어지는 최소 시간과 최대 시간은 아래와 같습니다. 개미 1 최소 : 2, 최대 : 8 개미 2 최소 : 4, 최대 : 6 개미 3 최소 : 3, 최대 : 7 모든 개미가 땅으로 떨어지는 최소 시간과 최대 시간을 구하는 문제이므로, 각 개미가 땅으로 떨어지는 최소 시간 중 제일 큰 값은 4, 각 개미가 땅으로 떨어지는 최대 시간 중 제일 큰 값은 8이므로, 주어진 예제의 정답과 같게 됩니다..

문제 링크 https://www.acmicpc.net/problem/5397 풀이 커서의 위치를 index = 0으로 둔 다음, 화살표에 따라 index를 변환하는 방식은 시간 복잡도가 높아 시간 초과가 발생합니다. 문자열이 최대 길이는 1,000,000 이기 때문입니다. 따라서, 커서는 그대로 두고, 커서를 기준으로 왼쪽 문자열은 left라는 배열에, 오른쪽 문자열은 right라는 배열에 담는 방식으로 문제를 해결할 수 있습니다. 세부 알고리즘은 다음과 같습니다. 문자열이 들어오면 왼쪽 배열에 붙입니다. ‘>’ 가 들어오면 오른쪽 배열의 마지막 문자를 왼쪽 배열의 마지막에 붙입니다. ‘’ 는 오른쪽 배열의 마지막 문자를 왼쪽 배열의 마지막에 붙이는것이므로, 오른쪽 배열에 문자가 존재해야합니다. ‘

문제 링크 https://www.acmicpc.net/problem/2839 풀이 남아있는 N이 5로 딱 나눠떨어질때까지 3씩 덜어냅니다. 세부 알고리즘은 아래 코드와 같습니다. 입력이 9일땐, N이 마지막에 0이 되더라도, if (n % 5 == 0) 의 조건은 만족하므로, 3으로만 나눈 결과값이 출력됩니다. 코드 import sys # 설탕 무게 n = int(sys.stdin.readline()) # 봉지 개수 bag = 0 while n >= 0 : if n % 5 == 0 : # 남은 설탕이 5로 나눠떨어진다면 bag += (n // 5) # 5로 나눈 몫을 봉지 개수에 추가 print(bag) break n -= 3 # 남은 설탕이 5로 나눠떨어지지않는다면, 3씩 덜어내기 bag += 1 # ..

문제 링크 https://www.acmicpc.net/problem/1790 풀이 단순히 문자열을 이어붙이면 메모리초과가 발생합니다. 따라서, 각각의 자릿수에 해당하는 숫자의 개수와 각 숫자의 글자수를 활용해 문제를 해결할 수 있습니다. 1의 자리인 숫자는 9개이며, 각 숫자의 글자수는 1개입니다. 10의 자리인 숫자는 90개이며, 각 숫자의 글자수는 2개입니다. 100의 자리인 숫자는 900개이며, 각 숫자의 글자수는 3개입니다. 따라서, 원하는 자릿수 K가 200이라면 아래와 같은 방식으로 해당하는 문자를 추측할 수 있습니다. 우선, 200을 넘지 않는 선에서, 1의 자리숫자와 10의 자리숫자가 모두 사용되는 것을 알 수 있습니다. 1 x 9 + 90 x 2 = 189 200 - 189 = 11 이므..

문제 링크 https://www.acmicpc.net/problem/3020 풀이 누적 합(Prefix Sum) 문제입니다. 먼저, 전체 높이 만큼의 인덱스를 가지는 배열을 2개 생성한 뒤, 각 배열에 대해, 석순과 종유석의 높이에 맞는 인덱스에 1을 증가시키고, 인덱스를 역순으로 누적합을 계산합니다. 이는, 석순 또는 종유석을 기준으로한 높이에 따라 잘리는 개수를 의미합니다. 각 장애물을 기준으로한 높이를 의미하기 때문에, 석순의 높이가 1, 3, 5 로 이루어져있을 때, 1의 높이에서 잘리는 석순의 개수는 3이며, 종유석의 높이가 5, 3, 1 로 이루어져있을 때, 1의 높이에서 잘리는 종유석의 개수는 3입니다. 결과적으로, 해당 누적합 배열을 통해, 각 장애물을 기준으로, 높이가 i일 때 잘리는 석..