https://school.programmers.co.kr/learn/courses/30/lessons/150367?language=python3 1. 문제 이해 입력으로 숫자(1 0101111 --> 0을 1개 붙여주어야 길이가 7 = 2^3 - 1이 된다.) 3. 얻어진 앞에 0이 붙은 이진수 문자열은 포화이진트리를 LUR 순으로 순회한 결과와 같다. -> 이진트리를 왼, 가운데, 오 순으로 순회 2. 문제 풀이 "이진트리 만드는 과정" 을 따라가면 앞에 0이 붙은 이진수 문자열을 얻을 수 있다. 해당 문자열로 이진트리가 만들어지는 지 여부는 재귀적으로 생각할 수 있다. 아래의 생각을 따라가보자. 0101111로 만들어진 트리는 루트 노드의 값(인덱스 3의 값)이 1이므로 해당 가지에서 양쪽에 모두 ..

dp 문제를 풀다보면 어느정도 패턴이 보이는 느낌이다. 이 문제는 두루마리에 겹치는 문자가 들어올 수 있기 때문에 (RGNR 처럼 R이 두번 등장할 수 있음) 천사의 다리와 악마의 다리의 문자가 두루마리에서의 몇번째로 등장하는 해당 알파벳인지도 저장하고 있어야한다. 즉, 하나의 돌다리에 도달한 경우에 가질 수 있는 상태는 아래 3가지가 있다. 1. 왼쪽으로부터 몇번째 돌다리인지 2. 현재 밟고있는 돌다리의 글자는 두루마리의 몇번째 글자인지 3. 천사의 다리인지 악마의 다리인지 위의 세 개의 정보를 토대로 3차원 dp배열을 정의하면 아래와 같다. dp[i][j][k] :k유형(악마의 다리 or 천사의 다리)의 다리의 i번째 위치에 j번째 두루마리 글자까지 밟고 온 경우의 수 그리고 각 다리에서의 행동은 해..

실버 2지만 반례를 찾아내기 개인적으로 굉장히 어려웠다. 큰 구성은 아래와 같다. -> 메세지를 읽지 않은 사람들을 담은 집합을 만든다. (초기화는 A를 제외한 모든 사람으로 해준다.) -> 톡 내용을 아래서 위로 훑으며 -> 송신자는 확실히 읽은 사람이기 때문에 집합에서 제거해준다. -> 읽은 사람 수가 0명이라면 모든 사람이 읽은 것으로 생각한다. 이렇게 하면 간단히 문제가 풀릴 것이라고 생각했지만, 나로써는 생각하기 어려운 반례 상황이 존재했다. 4 2 2 2 B 3 A 4 2 2 2 B 2 A 여기서 두 입력의 차이를 고려해주어야 "맞았습니다"를 받을 수 있다. 현재 초기화된 사람들 집합은 { B, C, D }이다. 톡 내용을 아래부터 훑으며 올..

1으로 시작하는 그룹의 개수를 구하는 것이 문제이지만, 이를 풀기 위해서 0으로 시작하는 그룹의 개수 또한 dp로 저장하며 계산에 활용했습니다. 찾아낸 패턴은 아래와 같습니다. 0으로 시작하는 이진수의 배열을 dp_0(n)이라 하고, 1로 시작하는 이진수의 배열을 dp_1(n)이라 하면 dp_0(n) = dp_0(n-2) + dp_1(n-2) + dp_0(n-1) dp_1(n) = dp_1(n-2) + dp_0(n-2) + dp_1(n-1) 여기서 + 연산은 파이썬에서의 문자열 concatenation 연산자로 사용했습니다. 0으로 시작하는 이진수 배열의 n번째 수의 그룹개수를 dp_0_group(n)이라 하고, 1으로 시작하는 이진수 배열의 n번째 수의 그룹개수를 dp_1_group(n)이라 하면 n이..

별로 어렵지 않은 구현문제였는데 아이디어를 떠올리는 데 시간이 조금 걸렸습니다. 종이를 R, U, D, L 방향으로 접는데 k번 접고 난 이후에는 변의 길이가 1인 정사각형이 남아있어야 하므로 좌우 방향 접는 횟수와 상하 방향 접는 횟수가 동일하다는 조건이 문제에 주어져 있습니다. 문제를 푸는 키 아이디어는 결과적으로 반복된다는 것입니다. 2*2 정사각형의 상하좌우의 뚫린 구멍이 모두 결정되고 나면 그러한 정사각형이 반복되는 구조입니다. 그러한 구조는 잘 생각해본다면 가장 마지막으로 접은 좌우 방향, 그리고 상하 방향으로 결정됩니다. 그리고 그 정보를 통해 우리는 2*2 정사각형의 구멍을 채울 수 있습니다. 예를 들어, R L L D U L R D D U 으로 접는다면, 가장 마지막으로 접은 좌우방향은 ..

queue를 사용하여 bfs 느낌으로 풀이를 시도했습니다. 자두의 위치, 움직인 횟수, 지나간 초 를 상태를 구성하는 요소들로 생각하고, 배열의 값은 그 상태에서 가질 수 있는 최대 자두개수를 저장하였다. --> 이 아이디어가 문제 푸는 핵심 아이디어입니다. 예를 들어 1번나무, 3번 움직임, 6초 지남 상황에서 지금까지 탐색한 최대 자두개수가 3이라고 할게요. 큐의 원소를 꺼내서 다음 상황을 보았는데 1번나무, 3번 움직임, 6초 지남이 등장하였고, 자두개수는 5가 된다고 하면 배열을 업데이트해주었습니다. 배열 업데이트와 동시에 큐에 삽입하고, answer에 현재 얻은 자두가 최대일 지 모르니 매번 더 큰값을 할당해주었습니다. 한가지 트릭은 비트 연산자를 사용하여 현재 자두의 위치와 자두가 떨어지는 위..