devlog

출처 : https://www.acmicpc.net/problem/14891 풀이 방법구현 문제이므로 문제 파악이 중요했다.구현해야 할 부분을 함수별로 하나씩 나누어 구현했다.또한 케이스를 나누는 것에 집중했다. 크게 만약 각 돌리기 명령에서 시작인 경우와 아닌 경우로 나누었다.돌리기 시작인 톱니바퀴양 끝에 있는 경우1번 톱니면 오른쪽만 4번 톱니면 왼쪽만 체크한다.중간에 있는 경우양 쪽을 다 확인한다.돌리기 시작이지 않는 톱니바퀴왼쪽만 확인오른쪽만 확인위와 같은 경우로 나눌 수 있다. 구현해야 할 함수를 생각해 보자  1. 톱니 돌리는 함수먼저 톱니 돌리기 위해 나는 톱니바퀴의 제일 위(12시 방향) 인덱스를 저장해 시계방향으로의 회전은 인덱스에 -1 반 시계방향은 +1을 해주고 % 8 연산을 통해 관..

출처 : https://www.acmicpc.net/problem/14499 풀이 방법간단한 구현 문제이다.각 주사위에서 저장된 수를 저장하기 위해 배열을 사용했다.2, 4, 1, 3, 5, 6 순서로 저장했다.그리고 주사위가 굴려졌을 때 어떻게 주사위의 눈금이 변화되는지 생각해 각 함수를 작성했다. 여기서 중요한 포인트는 주사위가 밖으로 나갔을 때 무시해야 하는 것이다.이때 만약 주사위를 먼저 굴리고 주사위를 이동시킨 후 좌표를 체크하고 롤백하게 된다면 주사위의 상하좌우가 변하기 때문에주사위의 좌표를 체크를 먼저 하고 난 후 주사위가 밖으로 나가지 않은 경우 주사위를 굴려야 한다. N, M, y, x, cnt = map(int, input().split())board = []dice = [0, 0, 0..

출처 : https://www.acmicpc.net/problem/2096풀이 방법처음에는 일반적인 DP문제로 풀이하였다 max와 min은 함수만 다르게 사용하고 점화식은 똑같다.처음 풀이 방법dp[i][j] = i, j일 때 최대 포인트 ( 0 dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + point[i][0]dp[i][0] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2])) + point[i][1]dp[i][2] = max(dp[i-1][1], dp[i-1][2]) + point[i][2]최소일 때는 반대 이렇게 max일 때와 min일 때 반복문을 두 번 돌았다.이렇게 풀이하게 된다면 메모리 초과가 발생하게 된다. 그래서 윈도우를 활용해야하는..

출처 : https://www.acmicpc.net/problem/17404풀이 방법dp에서 문제를 dp[i][j]를 i번째에 j색을 선택했을 때 최소 비용으로 설정했다.  ( 0이렇게 설정 후 for 문을 1부터 N-1까지 돌며 각 경우에 대해 각 경우에 대해 dp[i][0]일 땐 dp[i-1][1], dp[i-1][2] 중 작은 값을 선택dp[i][1]일 땐 dp[i-1][0], dp[i-1][2] 중 작은 값을 선택dp[i][2]일 땐 dp[i-1][1], dp[i-1][0] 중 작은 값을 선택 후 자신의 돈 더하기위 과정을 해주면 된다. 여기서 추가적으로 고려해야할 점은 처음과 끝이 다르게 선택되어야 한다는 점이다.이를 위해 첫 선택을 강제하는 방법을 선택했다.for 0~2까지 돌며 현재 선택된 ..

출처: https://www.acmicpc.net/problem/2011 풀이 방법암호를 해독하는 방법에는 한 글자씩 하거나 두 글자를 묶는 경우 2가지 경우가 존재한다.DP알고리즘에서 dp[i]를 i번째 까지 가능한 경우의 수라고 가정한다면 만약 한 글자씩 끊어서 하는 경우라면 dp[i-1]의 경우의 수를 더해주면 된다. 만약 i-1번째 수와 i번 째 수를 묶는다고 가정하면 이때 경우의 수는 i-2번째 경우의 수와 같으므로 해당하는 경우의 수를 더해주면 된다.  dp의 인덱스를 i를 i번째 까지 가능한 수라고 한다면 dp[1]일 때 i-2는 -1 이 되므로 예상치 못한 결과가 나오게 된다. 그러므로 인덱스를 하나씩 +1 해서 i+1이 i번째 까지 가능한 경우의 수라고 했다. n = list(map(in..

출처 : https://www.acmicpc.net/problem/1005 풀이 방법 위 문제는 그래프에서 작업의 우선순위가 정해져 있으므로, 위상 정렬을 사용해 해결할 수 있다.위상 정렬에 dp알고리즘을 추가하여 현재 노드를 완료하기 위한 시간을 계산할 수 있다. from collections import dequedef topological_sort(N, K, cTime, linked, degree, win_num): 위상정렬 dp = [0] * (N + 1) queue = deque() # 시작 점 초기화 for i in range(1, N + 1): if degree[i] == 0: queue.append(i) dp[i] =..

출처 : https://www.acmicpc.net/problem/15686 풀이 방법M개의 치킨 집을 선택하는 과정에서 순서에 상관없는 조합을 이용해야 한다.조합을 구하기 위해 백트레킹 dfs를 사용했다.아래의 코드에서 chosen 배열에 넣은 후 dfs를 수행하고 chosen배열에서 pop을 통해 백 트레킹을 수행했다. 치킨 거리 계산은 그냥 유클리드 계산으로 수행하면 된다. N, M = map(int, input().split()) ## N, M 입력받기city = []for i in range(N): ## city 입력 받기 city.append(input().split())house = []store = []chosen = []ans = 987654321for i in range(N): #..

출처 : https://www.acmicpc.net/problem/2252 풀이 방법위상 정렬 알고리즘을 통해 풀이할 수 있다.위상 정렬 알고리즘이란 그래프에서 우선순위가 있는 작업을 할 때 순서를 정해주는 알고리즘이다 답이 여러 개가 될 수 있다.조건으로 사이클이 없어야 한다. 또한 최우선순위인 시작 점이 존재해야한다.진입 점이 0인 점을 큐에 넣어서 시작점으로 지정한다.큐에서 하나를 pop 하고 이와 연결된 노드의 진입 점을 -1 한다.만약 2번에서 진입 점을 -1 한 노드의 진입점이 0이면 큐에 추가한다.위 2~3번 과정을 N번 반복하는데 만약 N번 반복하기 전에 큐에 empty가 되면 사이클이 존재하는 경우이다.코드from collections import dequeN, M = map(int, i..

출처 : https://www.acmicpc.net/problem/2565 풀이 방법전깃줄이 갖아 길게 안 꼬이는 경우를 찾으면 된다.와이어 A를 기준으로 연결된 쌍을 정렬한 뒤 B의 최장 증가 부분 수열을 구한 후 이를 원본 쌍에서 빼주면 된다. 1. 먼저 모든 연결된 쌍을 입력받는다.2. 와이어 A를 기준으로 정렬한다.3. 와이어 B를 저장하는 배열을 생성한다.4. 와이어 B를 탐색하며 만약 최장증가 부분 수열의 임시 배열인 lsb_arr의 마지막 원소보다 크다면 뒤에 추가한다.5. 크지 않다면 lsb_arr에서 현재 원소가 들어갈 인덱스를 이분탐색을 통해 구한 후 추가해 준다.6. lsb_arr의 길이를 구하면 이것이 최장 증가 부분 수열의 길이이다. N = int(input())wire = [] ..

출처 : https://www.acmicpc.net/problem/13418 풀이 방법union-find알고리즘을 통해 해결할 수 있다. 기존의 알고리즘과 다른 점은 0에서 1로 가는 간선은 무조건 포함되어야 한다는 점이다. 또 가장 힘든 경우와 가장 덜 힘든 경우를 계산하기 위해 mst알고리즘을 2번 사용했다.주의: mst알고리즘을 사용하기 전 parents를 초기화해주어야 한다.  N, M = map(int, input().split())edges = []parents = [ i for i in range(N+1)]a, b, c = map(int, input().split()) ## 0~1 엣지 무조건 추가되어야 할 edgefirst_weight = 1 - c ## 첫 번째 edge의 weight 오..