Algorithm Problem/Python

[python] 백준 - 16953. A → B

🤔문제 해결 S1 | 그래프, BFS 난 DFS 알고리즘 분류에는 그래프와 BFS로 나와있는데 잘 모르겠고, DFS로 해결했다. 목표 숫자부터 두가지 경우로 나눠서 들어간다. 맨 끝의 숫자가 1이면 1을 버리고 재귀 맨 끝의 숫자가 1이 아닐 때 2로 나누어 떨어지면 2로 나누고 재귀 테스트 케이스 3번을 예시로 하겠다 ( 100, 40021 ) 40021: 맨 끝의 숫자가 1이므로 1을 버린다 40021 => 4002 체크하는 방법은 10으로 나눈 나머지, 버리는 방법은 10으로 나눈 몫 4002: 맨 끝의 숫자가 1이 아니고 2로 나누어 떨어지므로 2로 나눈다. 4002 => 2001 2001: 버린다. 2001 => 200 200: 나눈다. 200 => 100 100: 100 == A 이므로 그만!..

[python] SWEA - 1248. 공통조상

🤔문제 해결 D5 | 그래프 이진 트리를 만들어서 문제를 해결하자. 이런식으로 2차원 배열을 만든다. 길이가 3인 리스트가 V개인 2차원리스트 부모 노드들 찾기첫 노드 (여기서는 8 과 13) 에서 시작해서 부모 노드를 타고 쭉 올라간다. ( DFS ) 8 의 부모 노드는 [5, 3, 1] 13의 부모 노드는 [11, 6, 3, 1] 공통 부모 노드 찾기 앞에서부터 for문을 돌며 겹치는 친구 찾고 바로 나오기 (여기서는 3) 공통 부모 노드 크기 찾기 노드(여기서는 3)에서 자식 노드를 타고 쭉 내려가면서 개수를 세어준다(DFS) 💨 💻소스 코드 def find_parent(n, parent_list): if tree[n][2]: parent_list.append(tree[n][2]) find_pare..

[python] 프로그래머스 - 3 x n 타일링

🤔문제 해결 Lv4 | dp 2 x n 타일링 문제와 마찬가지로 dp 문제. 완전 탐색으로 초반 몇 가지 경우의 수를 구한다.(손이나 코드로...) 몇 가지 경우의 수를 가지고 점화식을 세운다. 나는 1번 부분을 하다가 수가 너무 커져 시간이 오래걸릴까봐... 다른데서 가져왔다 나같은 사람을 위해 이제 위의 경우의 수를 가지고 식을 세우면 된다. 규칙성은 무조건 있다 💨 💻소스 코드 def solution(n): answer = 0 dp = [0] * (n + 1) dp[0] = 1 # 아무것도 두지 않는 경우도 1가지 sub = 0 for i in range(2, n + 1, 2): dp[i] = dp[i - 2] * 3 + sub * 2 sub += dp[i - 2] answer = dp[n] % 1..

[python] 백준 - 9658. 돌 게임4

🤔문제 해결 S1 | 다이나믹 프로그래밍 이게임은 거의 선빵필승 구조이다. 특별한 경우만 빼고! 먼저 손쉽게 1~4개일 때의 경우를 구할 수 있다. 돌 1개: 선 - 후공 승 돌 2개: 선, 후 - 선공 승 돌 3개: 선, 후, 선 - 후공 승 돌 4개: 선선선, 후 - 선공 승 다음 5개부터는 점화식으로 구해보자. 돌이 5개일 때 상영이가 돌을 둘 수 있는 경우의 수는 1개, 3개, 4개이다 - 3가지 경우 먼저 상영이가 돌을 1개 뒀다고 하자 그럼 남은 돌은 4개이고 창근이는 선공이 된다. 위의 4가지 경우를 봤을 때 돌 4개에서는 선공이 무조건 이긴다. - 창근 승 다음 상영이가 돌을 3개 뒀다고 하자 남은 돌은 2개이고 창근이는 선공이 된다. 위의 4가지 경우를 봤을 때 돌 2개에서는 선공이 무조..

[python] 프로그래머스 - 지형 편집

🤔문제 해결 Lv4 | 이분탐색 or 완전탐색(?) 이분탐색으로 코드를 구현했더니 효율성에서 실패했다. 그래서 한층한층 값을 저장하고 다음 층의 값을 구할 때는 이전에 저장한 층의 값을 이용하기로 했다. 먼저 2차원 행렬을 일렬로 세운고 오름차순 정렬한다. [[4, 4, 3], [3, 2, 2], [2, 1, 0]] ➡ [0, 1, 2, 2, 2, 3, 3, 4, 4] 다음 제일 낮은 층( 여기서는 0 )으로 평평하게 만들 경우를 구한다. 지형을 빼는 작업만 하면 되므로 ( 전체지형 수 - 가장 낮은층의 지형 수 ) * Q(빼는 비용) 빨간 부분을 다 지우면 높이가 0인 평평한 지형을 만들 수 있다. 값은 21칸 * Q(지우는 값) = 63 이제 일렬로 세운 리스트를 하나하나 탐색한다. ( 맨앞은 했으니..

[python] 프로그래머스 - 숫자 블록

🤔문제 해결 Lv4 구간(begin ~ end)이 정해져 있으므로 전부를 구할 필요는 없다. 선택한 구간만 잘라서 여기에 어떤 숫자가 들어가야 할지를 알아보자. 규칙을 잘 살펴보면 I 의 약수 중( 1 제외) 가장 작은 수로 나눈 몫이 해당 인덱스의 값이 된다. 10을 보면 2,5,10 중 2로 나누면 값은 5이다. 9의 경우 3,9 중 3으로 나누면 값은 3이다. 7의 경우 소수이므로 7로 나누면 값은 1이다. 위의 방법으로 코드를 짜면 정확도 테스트는 아주 쉽게 통과한다. 💡중요 이제 효율성 테스트가 문제인데 시간초과도 아니고 실패 라고 한다.이유는 전체 도로의 길이는 10^9 이지만 블록의 숫자는 10^7 까지이다.몫이 10^7을 넘어가게 된다면 사실상 해당블록은 존재하지 않는다!!그러므로 몫이 1..