백준-풀이

편집 시간: 2022년 2월 16일 오후 7:38 코드 Algorithm/9663.py at main · Junroot/Algorithm 풀이 재귀함수를 이용해서 모든 경우의 수를 탐색하면 된다. 퀸을 둘 때 대각선 방향의 인덱스 범위를 계산하는데 어려움을 겪었다.

편집 시간: 2022년 3월 23일 오후 10:19 코드 Algorithm/9466.py at main · Junroot/Algorithm 풀이 사이클이 존재하는지 확인하는 과정이 필요했다. 서로소 집합을 사용해서 사이클이 존재하는지 확인했다. 선호하는 학생을 나타내는 구조를 방향 그래프로 그렸을 때 자신이 방향을 따라 갔을 때 최종적으로 가리키게 되는 숫자를 parent라고 정의한다. 배열을 이용해서 parent를 관리하다가, parent가 자기 자신이라면 사이클이 발생한 것이라고 확인할 수 있다. 다른 풀이 위상 정렬을 이용해서도 사이클을 구할 수 있다. import sys from collections import deque input = sys....

편집 시간: 2022년 5월 14일 오후 10:33 코드 Algorithm/9465.py at main · Junroot/Algorithm 풀이 일단, 2줄의 스티커이므로 각 열마다 하나의 스티커만 선택할 수 있다는 것을 알 수 있었다. 그래서 처음에는 각 열마다 지그재그로 스티커를 선택한 두 가지 경우중 최대값이 정답이라고 생각했다. 하지만, 아래와 같이 한 열을 포기하고 선택하는 경우가 더 최대인 경우가 있었다. x x x 그래서 dp로 문제를 접근했다. f(x, y): 0번열부터 x열까지에서 x열 y행을 마지막으로 선택하는 경우의 최대값...

편집 시간: 2022년 4월 12일 오후 3:02 코드 Algorithm/9328.py at main · Junroot/Algorithm 풀이 bfs를 이용하면 쉽게 해결할 수 있다. 이동하다가 문을 만났을 때, 열쇠가 있는지 판별하고 있다면 이동하고, 없다면 열쇠를 기다리는 문 컬렉션에 추가 하는 형태로 문제를 풀었다.

편집 시간: 2022년 3월 24일 오후 1:45 코드 Algorithm/9252.py at main · Junroot/Algorithm 풀이 기존의 LCS 문제에서 dp원리를 이해하면 쉽게 해결할 수 있다. dp에 저장된 값을 보고 어떤 문자가 사용되었는지 확인하면되는데, 현재 위치에 저장된 값이 (왼쪽 위의 값) + 1인 순간이 해당 문자를 사용한 것이다.

오답 여부: o 편집 시간: 2022년 2월 24일 오후 6:02 코드 Algorithm/9251.py at main · Junroot/Algorithm 풀이 잘못된 풀이 문자열 하나에 대한 dp로 접근했다. 첫번째 문자열로 dp를 한다면 아래와 같이 접근할 수 있었다. f(x): x번째 문자열을 마지막으로 가지는 str2과의 (LCS, 마지막으로 사용한 index) f(n) = max( f(m) ) + 1 {m | m은 정수, 0 ≤ m < n, f(n)의 index > f(m)의 인덱스} max는 LCS가 같다면 마지막으로 사용한 index가 더 작은 것을 우선으로....

편집 시간: 2022년 2월 18일 오후 6:45 잘못된 풀이 first = input() second = input() cache = [(0, 9999) for _ in range(len(first))] def find_indexes_in_second(char): result = [] for i in range(len(second)): if second[i] == char: result.append(i) return result for i in range(len(first)): char = first[i] indexes = find_indexes_in_second(char) if len(indexes) == 0: continue cache[i] = (1, indexes[0]) for j in range(i): max_length = cache[j][0] last_index = cache[j][1] for index in indexes: if last_index < index: if cache[i][0] < max_length + 1: cache[i] = (max_length + 1, index) break elif cache[i][0] == max_length + 1 and index < cache[i][1]: cache[i] = (max_length + 1, index) break print(max(cache)[0])

편집 시간: 2022년 2월 9일 오후 6:18 코드 Algorithm/9095.py at main · Junroot/Algorithm 풀이 정수 n을 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 f(n)이라고 했을 때, f(n) = f(n - 1) + f(n - 2) + f(n -3) 라는 점화식이 만들어지는 것을 확인할 수 있으면 된다. 마지막에 더해지는 수가 1인 경우의 수는 f(n-1)이고, 2인 경우는 f(n-2), 3인 경우는 f(n-3)이기 때문이다.

편집 시간: 2022년 1월 31일 오후 5:52 코드 Algorithm/9012.py at main · Junroot/Algorithm 풀이 현재 열린 괄호의 개수를 깊이(depth)라고 하고, 문자열을 읽으면서 깊이가 음수가 되는 지점을 확인하면 된다. 또한, 문자열이 끝났을 때 깊이가 0으로 끝나는지 확인하면 된다.

편집 시간: 2022년 2월 16일 오후 4:02 코드 Algorithm/7662.py at main · Junroot/Algorithm 풀이 실패한 풀이: Node 클래스 만들기 최대 힙과 최소 힙을 두 개 마련해두고, 삭제 될 때 해당 숫자가 삭제되었다고 표시만 하면되기 때문에, 힙의 각 노드들을 아래와 같이 클래스로 만들어 deleted 필드를 두려고했다. class Node: def __init__(self, data): self.data = data self.deleted = False 하지만 한 가지 문제가 있었다. heapq 라이브러리는 최대 힙을 만들 수 없다. 그래서 일반적인 힙 문제에서는 음수를 취하여 힙에 추가하는데 현재는 최소 힙과 최대 힙이 노드를 공유하고 있어야되기 때문에 불가능하다....

편집 시간: 2022년 3월 31일 오후 9:53 코드 Algorithm/7579.py at main · Junroot/Algorithm 풀이 처음에는 아래와 같은 방식으로 dp로 풀려고 했다. 아래에서 f(i, m)의 정의는 0번째부터 i번째까지 앱으로 메모리 m을 비우기위한 최소 cost를 뜻한다. $$ f(i, m) = min(f(i-1,m-m_i)+c_i,f(i-1,m)) $$ 하지만, m의 범위가 10,000,000 까지기때문에 이 방법을 사용할 수 없다. 그래서 i와 cost를 사용해서 dp로 접근해봤다. $$ f(i,c)=max(f(i-1,c-c_i)+m_i,f(i-1,c)) $$ c의 범위는 0에서 10000까지라서 최대 100 * 10000번 계산으로 계산할 수 있다....

편집 시간: 2022년 2월 9일 오후 6:43 코드 Algorithm/7576.py at main · Junroot/Algorithm 풀이 bfs를 이용해서 모든 토마토를 탐색하면 된다. 시간을 출력해야되기 때문에 큐에 시간 정보도 같이 저장했다. 다른 방법으로는 현재 큐에 담겨있는 값들을 같은 시간에 방문하는 토마토라고 해두고, 그 개수만큼만 루프를 돌면 주기가 한번 돌았다고 계산하면 된다. 모든 토마토가 익었는지 확인해기 위해서 마지막에 박스 전체를 확인해봐도 되고, 익지 않은 토마토의 개수를 카운팅해도 된다.

편집 시간: 2022년 2월 7일 오후 8:37 코드 Algorithm/4153.py at main · Junroot/Algorithm 풀이 딱히 생각할 필요없이 피타고라스 정리로 비교하면 된다.

편집 시간: 2022년 4월 20일 오후 5:11 코드 Algorithm/3190.py at main · Junroot/Algorithm 풀이 현재 시간에 회전이 있는지 빠르게 파악하기 위해서 dictionary로 저장했다. 보드 정보를 나타내는 2중 배열을 만들어서 비어있으면 0, 사과가 있으면 1, 뱀이 있으면 2로 표현했다. 뱀의 꼬리를 제거할 때, 가장 끝 부분 정보를 얻기 위해서 덱을 사용했다.

편집 시간: 2022년 1월 31일 오후 5:52 코드 Algorithm/2798.py at main · Junroot/Algorithm 풀이 N이 100보다 작기 때문에 O(n^3)이어도 문제가 없다는 것을 알 수 있다. 모든 경우의 수를 다 구해본 뒤 M을 넘지 않는 최대값을 찾으면 된다.

편집 시간: 2022년 1월 31일 오후 5:59 코드 Algorithm/2751.py at main · Junroot/Algorithm 풀이 N이 최대 1,000,000 이기 때문에 최대 O(nlogn) 까지만 허용된다. python에서 기본적으로 제공해주는 정렬 함수는 머지 소트이므로 사용할 수 있다.

편집 시간: 2022년 2월 12일 오후 9:54 코드 Algorithm/2630.py at main · Junroot/Algorithm 풀이 네 구역으로 나누어서 각 구역에 대한 흰색과 파란색 색종이의 개수를 반환하는 분할 정복을 하면된다. 만약 현재 전체구역이 같은 색이면 이게 한개의 색종이가 된다.

편집 시간: 2022년 4월 2일 오후 5:07 코드 Algorithm/2623.py at main · Junroot/Algorithm 풀이 단순 위상 정렬문제다. 위상 정렬을 사용해서 순서를 결정하고, 모든 노드를 한번씩 방문하기 전에 끝난다면, 순환이 발생한 것이다.

편집 시간: 2022년 1월 31일 오후 6:06 코드 Algorithm/2609.py at main · Junroot/Algorithm 풀이 유클리드 호제법을 사용하면 쉽게 해결할 수 있다.

편집 시간: 2022년 2월 9일 오후 6:29 코드 Algorithm/2606.py at main · Junroot/Algorithm 풀이 bfs또는 dfs로 연결되어 있는 컴퓨터를 확인하면 된다.