본문 바로가기

Algorithm

 (140)
부품 찾기 유형 분석 및 구현 이 문제는 이진탐색 또는 계수 정렬을 통해 풀 수 있다. 조건은 다음과 같다. N = 최대 백만 정수의 범위는 백만이하이다. M = 최대 10만 예를 들어, 이 문제를 순차적 탐색으로 해결한다고 가정하면 시간 복잡도는 log(M*N)이다. N(앞에서부터 하나하나 확인해가면 찾으려는 값일 때, 끝냄) M(찾으려는 값 수) 최악의 경우 1조회의 연산이 필요하다. 하지만 이진탐색으로 해결시 우선 정렬이 필요한데, 파이썬의 정렬의 연산수는 NlogN이다. 이 후 이진탐색으로 해결시 M개의 데이터에 대해 총 MlogN이다. 결과적으로 시간 복잡도는 O((N+M)logN)이다. 굉장히 작아짐을 알 수 있다. "연산 계산시 조건에 맞추어 풀 수 없다는 것을 직감한다면 바로 이진탐색을 사용하자." ..
Binary Search - Concept 해당 문제는 "이것이 코딩 테스트이다" 책을 참고하여 제작하였습니다. 순차탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 시간복잡도 : O(N) 이진 탐색 - 정렬된 배열에 대해서 반으로 쪼개가며 확인하는 방법 - 시간복잡도 : O(logN) - 구현 방법 : 반복문 or 재귀 함수 유형 " 코드를 정리하고 최대 탐색범위와 시간복잡도를 고려할 때, 연산의 수가 2000만(파이썬 평균 연산 수)를 넘어간다면 이진탐색 또는 계수 정렬 등을 고려하자. " " 정렬되어있을 때 라는 말이 많이 나옴"
못생긴 수 유형 파악 및 구현 이 문제는 생각해내는게 좀 어려웠던 것 같다. 못생긴 수는 2, 3, 5의 조합들을 의미한다. 못생긴 수의 리스트를 보면 1, 2, 3, 2x2, 5, 2x3, 2x2x2, 3x3, 2x5 이런식으로 진행된다. 즉 초기 못생긴 수를 넣고 (2, 3, 5) 이미 들어간 못생긴 수에 2, 3, 5를 곱하는 방식으로 진행된다. 구현을 하기 위해서는 2 or 3 or 5가 다음에 곱해져야하는 리스트 인덱스를 담는 변수 -> i2, i3, i5 결과마다 가장 작은 것을 뽑아서 리스트에 넣기 전 결과를 표현하는 변수 -> next2, next3, next5가 필요하다. 코드 # 찾으려는 인덱스 n = int(input()) # 못생긴 수 초기화 ugly = [0]*(n+1) # 첫번째 못생긴 수..
병사 배치하기 유형 파악 및 구현 예를 들어, [15, 11, 4, 8, 5, 2, 4]가 있을 때, 오른쪽으로 갈수록 수를 크게 만들면서, 리스트 내의 요소가 가장 많은 경우를 구하는 것이다. 이는 전형적인 다이나믹 프로그래밍의 문제 중 하나인 '가장 긴 증가하는 부분 수열 문제'이다. [15, 11, 4, 8, 5, 2, 4] dp 리스트는 아래와 같은 방식으로 채워진다. 4 - [1] : 마지막 요소 뒤에는 아무 요소가 없다. -> dp(n-1) 2- [1] : 2의 뒤에는 2보다 작은 요소가 없다. -> dp(n-2) 5 - [2] : 5의 뒤에는 2 or 4를 넣을 수 있다. -> dp(n-3) = dp(n-2) + 1 or dp(n-1) + 1 8 - [3] : 8의 뒤에는 (5, 2) or (5, 4)를 ..
퇴사 유형파악 및 구현 이 문제는 아이디어는 떠올리기 쉬웠으나 구현이 어려웠던것 같다. 아이디어 - 우선, 뒤에서부터 하나하나 확인을 한다. - 만약 걸리는 시간때문에 퇴사전 이 일을 마무리 못하는 경우라면 패스한다. - 가능하다면 추가를 한다. - 다음의 경우로 마지막날 전날 인터뷰에 대해서 점검을 하는데 예를들어, 7일까지 일을할 것이고 7일은 1일소요, 500원, 6일은 2일소요 100원이라고 가정하자 6일날 일하게 되면 6,7일은 일을 못하고 다음일은 8일부터 가능하다. 따라서 7일날 일하는 경우 vs 6일날 버는 돈 + 8일 이후에 버는돈 을 비교해 큰값으로 값을 기록한다. 이 후, 그 전날 , 그 전날 이런식으로 나아간다. 전형적인 DP문제이다. 하지만 헷갈렸던 거는, 기록을 하는 dp리스트는 크기..
정수 삼각형 유형 분석 이 문제 또한 전에 풀었던 금광문제처럼 사고의 전환이 필요하다. 1열에서 2열로 더한다 라기 보단 2열을 기준으로 1열에서 최선의 선택을 해 더한다로 생각하는게 낫다. 다만, 헷갈렸던 점은 대각선을 더해야하는데, 2차원 배열로 나타내면 대각선 표현이 어렵다는 점이다. 그걸 주의해서 잘 풀어야 하는것 같다. 코드 n = int(input()) m = int(input()) graph = [] graph.append([m]) for i in range(1, n): graph.append(list(map(int, input().split()))) dy = [-1, 0] for x in range(1, n): for y in range(len(graph[x])): max_value = 0 for i ..
금광 문제 금광은 N,M 행열로 구성되어 있다. 첫번째 열부터 시작해 마지막 열까지 이동하는데, 방문한 행에 있는 금을 캘 수 있다. 오른쪽 위, 아래, 옆 중 하나를 선택해 이동가능하다. 최대한 많이 캔경우 금의 양은? 유형 파악 및 구현 금광 (x, y)는 (x-1, y-1) or (x, y-1), (x+1, y-1) 중 하나와 더해 가장 크게 만들어야 한다. 첫번째 열부터 시작하니 이동 경로마다 값을 구하기 보단 생각을 역전해서 두번째 열에 있는 금들은 첫번째 열의 어떤 금들과 더해져야 가장 커지는가?에 대해서 생각하면 좋다. 1행 2열은 1열의 금들 중 어떤 금이랑 합쳐져야 가장 커지는가? 2행 2열은 1열의 금들 중 어떤 금이랑 합쳐져야 가장 커지는가? ... 1행 4열은 3열의 금들 중 어떤 금이랑..
효율적인 화폐 구성 문제 주어진 코인을 이용해 문제에서 주어진 돈을 만들어라 유형 파악 및 구현 전형적인 DP문제인것 같다. 예를 들어 [2, 3]원을 활용해 5원을 만든다고 가정하자. 1원 만들 수 있는가? X 2원 만들 수 있는가? O -> 2%2 == 0 3원 만들 수 있는가? O -> 3%3 == 0 4원 만들 수 있는가? O -> 4%2 == 0 5원 만들 수 있는가? O -> 5%2 ==0 ? X -> 5%3 ==0 ? X -> (5-2)원은 만들 수 있는가? == 0? O -> 3원을 만드는 경우의 수 + 1 즉, 5원을 만들때, 2원이나 3원만으로는 만들 수 없다. 하지만 5-2 or 5-3원을 만들 수 있는지 체크 한 후 만들 수 있다면 그 값에 1을 더하면 된다. 코드 n = 3 result = 10 co..

티스토리툴바