![]()
금광 이동방향은 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 이다. 이를 현재 내 위치인 dp[i][j]에서 보면 왼쪽 위, 왼쪽, 왼쪽아래에서 내 위치로 오는 3 가지 경우가 있다는 의미이다 하지만 이렇게 i == 0 인 경우에는 왼쪽위에서 올 수 없으므로 left_top = 0 이다. 그렇지 않은 경우에는 left_top = dp[i-1][j-1] 이다. 다음의 경우는 3가지 방향 모두 유효하니까 경우를 더 나눌 필요 없이, left = dp[i][j-1] i == (n-1) 인 경우에도 왼쪽아래에서 오는 경우는 불가능 하므로 이 경우 left_bottom = 0이라고 처리해 준다. 그렇지 않은 경우는 left_bottom = dp[i+1][j-1] 이다. 그리고 이 값들 중에서 max 값과 dp[i][..
https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 이 문제는 이진탐색으로 해결할 수 있다 왜냐면 fro??? 이렇게 접두사가 있으면 단어들 리스트에서 fro 가 처음 나온 인덱스랑, 마지막으로 나온 인덱스를 각각 구해서 차이를 구하면 그것이 바로 fro???에 해당하는 단어들 개수가 된다 !! 단어 탐색의 시작은 a 부터 z까지이다. 숫자 뿐만 아니라 이렇게 단어 탐색도 이진탐색을 사용할 수 있다. 여기서 신선하다고 생각 ㅋㅋ 파이썬에는 bisect이라는 이진탐색을 쉽게 수행할 수 있도록 돕는 라이브러리가 있다 그런데 문제제는 접두사말고도 접미사 부분이 ? 인 경우가 있다 ex) tra?? ..
![]()
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 이 문제를 풀 때 핵심적인 아이디어는, 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 다이나믹 프로그래밍 알고리즘을 수행해야 한다는 것이다 ! 문제에서 주어진 예시 N = 7 인 경우에는 6일과 7일자의 상담을 수행하면 7을 넘기게 된다. 이와 같은 경우를 고려하기 위해서 뒤에서부터 DP를 수행하여 저장한다. 경우를 나누는 것은 두가지로, i번째 날의 상담을 수행했을 때 n을 넘는다면 이 경우는 불가능하니까 value를 0이라고 생각하여 dp 그래프에 0 값으로 처리를 한다. dp[i] = dp[i+1] # 단, 여기서 dp list의 맨 ..
https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 결국 BFS를 이동해서 로봇이 (n,n)에 도달할때까지의 최단거리를 구한다. 1. 벽을 하나 둘러싼 모양으로 확장된 보드를 만들어서 (1,1) ~ (n,n) 이라고 생각하기 쉽게 해준다. 2. 갈수있는 위치를 구하는 함수는 갈수 있는 위치의 리스트를 리턴한다. 3. 갈수 있는 위치는 queue에 넣고, 방문하면 visited에 넣는다. 일반적인 bfs로 , 큐가 빌 때까지 반복한다. 4. 갈..
문제에서 O(logN)으로 알고리즘을 설계하기를 요구했다 -> 선형탐색은 O(N) 이므로 부적합 데이터 셋이 오름차순으로 정렬되어 나오기 때문에 이진탐색을 선택함 mid 를 인덱스로 보고 array[mid] 값과 같으면 고정점이다 -> 이 값을 리턴 그렇지 않은 경우, array[mid] 실제 값이 더 크다면 반으로 뚝 자른 데이터들 중에서 오른쪽의 큰 값들을 탐색하면 된다. 더 작으면 왼쪽의 작은 값들을 탐색한다. 탐색 실패하면 None을 반환한다. n = int(input()) array = list(map(int, input())) def binary(array, start, end): if start > end: return None mid = (start + end) // 2 if array[m..
카드 정렬하기 !! 첫 시도: 가능한 순열 조합을 모두 계산하고 최솟값을 찾으려고 했으나 ㅋㅋㅋ 이 문제는 숨겨진 규칙이 있었으니.. 바로 가장 작은 카드 수 부터 더해가야 한다는 것이다. 그래서 heap 자료 구조를 이용하여 카드 들 중에서 카드 수가 작은 것을 빼내어 더하고, 이 더한값을 다시 heap에 넣어줘서 다시 더해지도록 한다 heapq 라이브러리 오랜만에 쓰는데 이 참에 파이썬 힙 자료구조 라이브러러 쓰는 방법도 확실하게 숙지해야겠따. import heapq n = int(input()) heap = [] for i in range(n): data = int(input()) heapq.heappush(heap,data) result = 0 while len(heap) != 1: one = h..
유형 : 구현 그치 딱 봐도 구현 문제이다.. 그런데 처음에 문제를 이해하는데 '균형 잡힌 괄호 문자열' 이랑 '올바른 괄호 문자열' 이 헷갈렸다 ㅋㅋㅋ 문제 풀이의 핵심은 무엇일까 재귀함수를 적절히 만들어 주어야 한다 !!!!! 당연한 소리지만 -_- 1. 균형 잡힌 괄호 문자열이 p의 어느 인덱스 까지인지 반환해주는 함수 구현 2. 현재 문자열이 올바르괄호 문자열인지 아닌지 구하는 함수 구현하기 3. 재귀 함수로 호출할 solution(p) 부분 구현하기 def balance(p): count = 0 for i in range(len(p)): if p[i] == '(': count += 1 else: count -= 1 if count == 0: return i def check(p): count =..
유형 : DFS/BFS 1. 바이러스의 종류는 1 ~ K 로, K 개이다. 이 문제를 풀 때 바이러스가 상 하 좌 우 로 번식한다고 하니 dfs / bfs로 이동하는걸 떠올렸다. 그런데 나는 처음에 풀 때 dfs라고 생각했다 그런데 계속 재귀 호출 에러가 났다. 이 문제는 bfs로 풀어야 한다. 왜...? 왜일까 bfs로 풀면 바이러스를 오름차순으로 정렬한다음에, 탐색할 수 있다 !!! 풀이를 정리해 보면 1. graph 를 생성 ! 정보를 받을 때 0초로 초기화 해서 저장한다. 이 문제의 특징은 s초가 지난 후의 x,y 좌표에 존재하는 바이러스 타입이 무엇인지 묻는 것이기 때문에 초 정보도 저장하는 것이 좋다. 2. 오름차순으로 바이러스 정렬 3. bfs 실행 # 경쟁적 전염 from collectio..
