해밍거리 + BFS 경로 역추적하기

2479번: 경로 찾기 이진 코드들이 주어질때, A 이진코드에서 B 이진코드로 가는 경로를 찾을려고 한다 이때 경로를 구성한 노드간 서로 인접한 코드끼리의 해밍거리가 1이어야한다 해밍거리는 길이가 같은 두 이진코드들에서 왼쪽부터 오른쪽으로 차례로 비교할 때 서로 다른 값을 가진 비트의 수이다 예를 들어 010과 110은 서로 다른 비트가 0번째 비트로 1개이므로 해밍 거리가 1이다 코드 번호 A,B가 주어질때 가장 짧은 해밍 경로를 찾는다 -------------------------------------------------------------------------------------------------------------------------------------------------- 두 코..

• format_list_bulleted DFS BFS 정복기
• · 2025. 2. 3.
• textsms

출발 조건이 까다로운 2차원 배열 목적지까지 이동하는 다이나믹 프로그래밍

14722번: 우유 도시 (0,0)에서 (n-1,n-1)까지 이동하면서 우유를 마시는데 맨 처음에는 딸기우유를 마신다 딸기우유를 마신 다음에 초코우유를 마신다 초코우유를 마신 다음에 바나나 우유를 마신다 바나나 우유를 마신 다음에 딸기 우유를 마신다 위 4가지 조건을 만족하면서 우유를 마시는데, (x,y)에는 딸기, 초코, 바나나 우유 셋 중 하나만 있다.  최대로 마실 수 있는 우유 개수는? ------------------------------------------------------------------------------------------------------------------------------------------------------ dp[i][j][k] = (j,i)에 있는데 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 1. 27.
• textsms

퍼져나갈 수 있는지를 묻고 있지만 도달할 수 있는지를 계산해야하는 BFS

19538번: 루머 최초 루머 유포자에서 시작해서 매분마다 주변인에게 루머를 퍼뜨리는데 해당 사람은 주변인의 절반 이상이 루머를 믿고 있다면 루머를 믿게 된다 충분한 시간이 지난 후 각 사람들이 처음 루머를 믿기 시작하는 시간을 모두 구한다 ------------------------------------------------------------------------------------------------------------------------------------------- 단순하게 생각해서 유포자부터 큐에 넣어서 BFS를 수행해가지고, 방문가능한 정점에 방문해서 해당 정점의 주변 정점들 중 루머를 믿고 있는 정점 수를 찾고 그 정점 수가 주변 정점들 수의 절반 이상이면 해당 정점은 루머를 ..

• format_list_bulleted DFS BFS 정복기
• · 2025. 1. 25.
• textsms

똑같은 원소를 연속해서 사용하지 않도록 최대한 쓰는 놀라운 그리디 알고리즘

25635번: 자유 이용권 i번째 놀이기구 이용권의 횟수가 A[i]로 주어진다 모든 놀이기구를 이용하고 싶은데 연속으로 같은 놀이기구를 사용하지 않는다 최대 몇번 사용가능한가? A = [1,1,3]이면 3번, 2번, 3번, 1번, 3번으로 5번 가능하다 처음에 생각하기에는 무조건 큰 값끼리 모아서 쌍으로 이용하면 된다고 생각을 했는데 A = [1,2,3,4,5]라고 한다면  5번 이용가능한거랑 4번 이용가능한거 모아서 5 4 5 4 5 4 5 4 이렇게 하면 8번 쓰는거고 5가 1번 남고 [1,2,3,0,1]에서  3,5 해서 3번이 2번 남고 [1,2,2,0,0]에서 3번 2번 가져와서 3,2,3,2 해서 [1,0,0,0,0] 해서 1번을 쓰면 된다는 식으로 n = int(input())A = list..

• format_list_bulleted 그리디 알고리즘
• · 2025. 1. 21.
• textsms

나머지 연산과 비둘기집 원리

1323번: 숫자 연결하기 어떤 수 n,k가 주어질때, n을 여러번 붙여써서 k로 나누어지는 경우가 있는지 알고 싶다 예를 들어 10은 1번 쓰면 10 2번 쓰면 1010 3번 쓰면 101010 이때, 최소로 붙여써서 k로 나누어 떨어지게 하고 싶을때 최솟값을 구한다면? ------------------------------------------------------------------------------------------------------------------------------------------------------ n을 여러번 붙여쓴다는 것은 예를 들어 10을 여러번 붙여쓴다면 1번 쓰는 경우 10, 2번 쓰는 경우 1010인데 1010 = 1000 + 10 = 10*10^2 + 1..

• format_list_bulleted 비둘기집 원리
• · 2025. 1. 19.
• textsms

플로이드 워셜 주의해야할 점(k > i > j 순서로 돌기)

2224번: 명제 증명 명제가 주어질때 참으로 가능한 명제들을 모두 출력하는 문제 p => p같은 전건과 후건이 같은 명제는 출력하지 말고 삼단논법에 의해서만 참이 될 수 있는 명제만 출력하는 문제 전건 후건으로 가능한 것은 알파벳 대소문자이고 총 52개여서 이를 노드 번호로 바꿔주고 from sys import stdinn = int(stdin.readline())node = {chr(i+65):i for i in range(26)}for i in range(26,52): node[chr(i+71)] = ichange = {v:k for k,v in node.items()}  A => b,  b => C이면 A노드에서 b노드로 갈 수 있다는 의미이고, b노드에서 C노드로 갈 수 있다는 의미..

• format_list_bulleted 최단거리 알고리즘
• · 2025. 1. 11.
• textsms