Algorithm

💭 나의 접근 방법 123456789101112위와 같은 2차원 배열이 있을때 특정 2차원 배열의 합을 구하는 방법 6이 (x,y) 이고 12가 (i,j) 일때(x,y)에서 (i,j)위치까지의 지정된 수들의 합 공식12까지의 합: 1번4까지의 합: 2번9까지의 합: 3번1까지의 합: 4번$$ (1) - (2) - (3) + (4) $$따라서 2차원 배열의 합을 구하는 DP 테이블을 만들어준다.for i in range(1,N+1): for j in range(1,M+1): sum_arr[i][j] = arr[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1]합 테이블을 구하는 방법현재 값의 왼쪽까지의 합 + 현재까지의 ..

💭 나의 접근 방법5123 으로 이동해야하는 타자의 경우 5로 이동할 때 1을 고려해야 하기 때문에 왼쪽 오른쪽중 최선의 것을 고를수있는것이 불가능. 따라서 브루투포스는 불가따라서 앞에서 나온 경로값을 가지고 있어야한다. 누적비용→ DP숫자 하나씩 처리하며, 왼손으로 누를 경우와 오른손으로 누를 경우 이동비용을 모두 처리한다. 처리 후 갱신! 동일한 값이 있을 수 있기 때문에 최솟값으로 넣어준다. 🤔 이동 비용은 어떻게 처리할까?2차원 격자의 거리를 이용해 계산$dx=∣x1−x2∣$ : 행간의 차이$dy=∣y1−y2∣$ : 열간의 차이대각선 이동 비용$3 \times min(dx,dy)$상하좌우 이동 비용남은 행 이동: $dx-min(dx,dy)$남은 열 이동: $dy-min(dx,dy)$$2 \ti..

💭 나의 접근 방법 가능한 경우의 수를 나열하여 문제를 어떻게 선택할지 고민하였다. 정해진 범위내에 최선의 선택을 해야하기 때문에 백트래킹이 떠올랐다. N개의 문제들을 나열하고 특정 숫자에서는 합이 R을 초과하게 되는데 이부분 이 후 부터는 백트래킹을 이어하지 않고 중단시키려고 하였다. 그런데 문제를 보니 N이 15개로 제한되어있어서 끝까지 수행해도 되겠다 싶었고, 백트래킹의 기본 틀대로 문제를 풀었다. 💡 결과 # 16938 캠프준비 G5 import sys input = sys.stdin.readline N,L,R,X = map(int,input().split()) arr = map(int,input().split()) arr = sorted(arr) answer = 0 def backtrack(st..

💭 나의 접근 방법 이 문제를 풀기 이전에 트리의 지름 문제를 2개 풀고 이 문제를 접하게 되었다. 임의의 지점에서 가장 먼 지점 A / A에서 가장 먼 지점 B B의 거리가 트리의 지름이 된다. 내가 생각한 두번째 트리의 지름은 A 까지의 탐색의 DFS와 B까지의 탐색의 DFS의 max 값을 갱신해주어 문제를 풀려고 접근하였다. 이 접근방식은 고려되지 않은 지점에서 트리의 길이가 나올수 있기때문에 틀린 접근 방법이었다. 이 문제의 접근 방법은 1️⃣임의의 지점에서 가장 먼 지점 A / A에서 두번째로 먼 지점 B 2️⃣임의의 지점에서 두번째로 먼 지점 C / C에서 가장 먼 지점 D 방법으로 문제를 접근해야한다. 다만 이 문제의 예외사항이 있다. 예제 2번의 경우이다. 3 1 2 3 1 3 2 이 입력..

💭 접근 방법 graph에 인덱스 저장 (현재 위치를 BFS에서 뽑아야하기 때문에 인덱스를 저장한다. graph는 이동할 곳 경로를 저장하는 용도이다.) visited = [0] * 101 방문했는지 경로 BFS 시작 초기 인덱스를 deque에 넣고 꺼내 주사위 + 1~6까지의 경로를 파악한다. 방문하지 않은 경로 인경우 visited[이전경로] + 1을 해준다. 종료조건 : 앞으로 간 경로가 100인경우 종료한다. 코드로 보면 이해할수있습니다. 💡 결과 # 16928 뱀과사다리게임 G5 from collections import deque N,M = map(int,input().split()) graph = [i for i in range(101)] #인덱스 현재 위치를 저장! visited = [0]..

💭 나의 접근 방법 문제대로 접근하면 i행 j열에 1이면 j행을 찾아보는 방법으로 진행하려고 했다. 그래서 DFS방식이거나 BFS방식으로 생각해 볼 수 있다. 이 문제는 플로이드워셜로 풀 수 있다. 플로이드 워셜은 최단경로 문제에서 사용되는 방식으로 3중 반복문으로 사용된다. $$ D_{ab} = min(D_{ab},D_{ak}+D_{kb}) $$ a→b 와 a→k,k→b 를 비교 후 더 작은 값으로 갱신하는 방법으로 O(N^3) 시간복잡도를 가질 수 있기 때문에 노드의 개수가 적을 경우 (500개 이하일 경우)에 사용하는 것이 효율적이다. 이 문제에서는 최솟값으로 갱신하는것이 아닌 지나가는 경로를 모두 파악하는 것이므로 지나간 경우 1로 표시해 주면 된다. 💡 결과 # 11403 경로 찾기 S1 # #..

💭 나의 접근 방법 두 묶음의 합이 작은것 끼리의 합이니까 작은것부터 차례대로 합을 구하려고 접근하였다. but, 앞에서 부터 합이 뒤에 묶음보다 큰 경우 중복 덧셈을 하기 때문에 수가 커질수 있는 문제를 간과하였다. 반례) 4 20 30 40 45 -> 20+30 이 다음수 40보다 크기 때문에 50 + (50 + 40)을 하면 50이 중복 덧셈이 되기 때문에 안됨! 따라서, heappop, heappop 한 두개의 작은 값을 다시 힙 정렬에 넣어 작은수를 꺼낼수 있도록 구현해야한다. 💡 결과코드 import heapq import sys input = sys.stdin.readline N = int(input()) q = [] answer = 0 for _ in range(N): heapq.heapp..

💭 나의 접근 방법 DP 방식을 생각하지 못하고 n개의 스티커에서 다음 행 줄에서 선택할 스티커를 선택하는 방식으로 접근했다. 현재 위에 줄인경우 다음줄 아래 + 그 다음줄위 , 다다음줄 아래 중에 max인 값을 찾아서 다음 스티커로 이동할 곳을 선택해서 합을 구하는 방법으로 접근했다. 문제는 누적값을 처리하지 못하기 때문에 전체 탐색을 해서 비효율적인 접근이 되었다. 따라서, DP 를 이용해 문제를 접근해야한다. 스티커를 선택하는 방식에는 1. 한칸을 건너뛰는 경우 2. 지그재그로 가는 경우 두가지가 있다. 이 2가지를 처리하는 점화식을 만들어야한다. 한칸을 뛰는 경우는 스티커의 면을 고려했을때 현재 위에 있는 경우 전전 줄의 아래만 가능하다. 지그재그로 가는 경우는 현재 위에 있을 경우 전 줄 아래만..

💭 나의 접근 방법 M,N,x,y = M계산 값, N계산 값, x M나머지, y N나머지 1. x+(M*i) 를 반복해서 M으로 나눈값이 x 값인지 확인, y+(N*i) 를 반복해서 N으로 나눈값이 y 값인지 확인 2. 1부터 M,N의 최소공배수 값까지 전체탐색하여 구할수 있는지 확인 먼저 나는 2번의 방법으로 접근해보았다. # 6064 카잉달력 S1 # 틀렸습니다. + 1~ 전체 탐색은 시간 초과문제가 발생함 def gcd(a,b): while b > 0: a,b = b,a%b return a T = int(input()) for _ in range(T): M,N,x,y = map(int,input().split()) lcd = M*N//gcd(M,N) for i in range(1,lcd+1): if..

조합과 순열을 백트래킹을 이용해 구현할 수 있다. 파이썬에 라이브러리를 사용할 수 있지만 코딩테스트에 백트래킹 문제를 대비하기 위해서는 조합, 순열을 직접 구현해 보는 것이 도움이 될 것 같다. 1️⃣ 조합 def comb(arr,n): result = [] def backtrack(start,comb): # comb 리스트 if len(comb) == n: # 종료식 result.append(list(comb)) return for i in range(start,len(arr)): comb.append(arr[i]) backtrack(i+1,comb) comb.pop() # 마지막 인덱스를 꺼냄 backtrack(0,[]) return result print(comb([1,2,3,4],2)) 2️⃣ 순..