알고리즘 스터디
[프로그래머스] 탐욕법 5. 섬 연결하기
문제 https://programmers.co.kr/learn/courses/30/lessons/42861?language=python3 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 최소신장트리 문제인 것 같아 검색해 보았다. MST 문제에는 크게 두 가지 방법의 해결책이 있는 듯 했다. 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복 Prim의 알고리즘의 시간 복잡도는 O(n^2) Kruskal 알고리즘의 시간 복잡도는 O(elog₂e) 그래프 내에 적은 숫자의 간선만을 가지는 ‘희소 그래프(Sparse Graph)’의 경우 Kruskal 알고리즘이 적합하고 그래프에 간선이 많이..
[프로그래머스] 그래프 2. 순위
문제 풀이 혼자 여러 방법으로 고민해보다가 아무래도 정답인 것 같은 방법이 생각나지 않아 검색해보았다. ( https://roomedia.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%88%9C%EC%9C%84-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B7%B8%EB%9E%98%ED%94%84-Floyd-Warshall-Level3 ) 플루이드 와샬 알고리즘을 적용하는 문제라고 하는 부분까지 보고 아래와 같이 로직을 생각해 보았다. 한 점에서 다른 점까지의 거리를 점을 기준으로 계산하는 알고리즘이다. O(n^3)이다. ( https://blog.naver.com/ndb796/221234427842 ..
[프로그래머스] 동적계획법 2. 정수 삼각형
문제 풀이 1. 각 노드까지의 최댓값을 저장 2. 맨 아래 줄까지 반복 3. 맨 아래 줄 중 가장 큰 값 반환 def solution(triangle): for i in range(len(triangle) - 1): for j in range(len(triangle[i+1])): if j == 0: # 각 줄의 첫 번째 노드인 경우 오른쪽 부모의 값만 더함 triangle[i+1][j] = triangle[i][j] + triangle[i+1][j] continue; if j == len(triangle[i+1]) - 1: # 각 줄의 마지막 노드인 경우 왼쪽 부모의 값만 더함 triangle[i+1][j] = triangle[i][j-1] + triangle[i+1][j] continue; #중간 노드..
[프로그래머스] 그래프 1. 가장 먼 노드
풀이 드디어 그래프‼️‼️ 어떻게 구현하는건지 하나도 기억 안 나서 먼저 검색을 좀 했다. 인접리스트 혹은 인접행렬을 사용하는 듯 했다. (https://hsc-tech.tistory.com/12) 인접리스트(graph) 1 -> 2 -> 3 2 -> 1 -> 4 -> 3 -> 5 3 -> 6 -> 2 -> 4 -> 1 4 -> 2 -> 3 5 -> 2 6 -> 3 visited 1 2 3 4 5 6 # 노드 번호 0 1 1 2 2 x # 노드에 방문하기까지의 간선 개수 q 6 # 노드 번호 2 # 노드에 방문하기까지의 간선 개수 인접리스트로 BFS를 구현하기로 했다. BFS 가 최단경로를 보장하기 때문이다. 헷갈려서 메모해봤다. 위의 메모는 6말고 모든 노드를 돌았을 때의 상태이다. 처음엔 노드의 번호..
[프로그래머스] 해시 2. 디스크 컨트롤러
https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 풀이 힙이 뭔지 그새 또 까먹어서 지난번 힙 문제를 보고왔다. 힙은 완전이진트리의 일종으로 최댓값, 최솟값을 추출하기 쉬운 자료구조였다. 포기한 방법들.. max(0, 요청 시간 - 현재 시간 curTime) + 소요 시간 을 key로 갖는 최소 heap을 만든다 -> 현재 시간이 계속 바뀌니 문제가 될 것 같아서 포기 힙을 만드는 대신 min으로 위의 과..
[프로그래머스] 해시 4. 베스트 앨범
풀이 먼저 딕셔너리에 키를 장르, 값을 {고유번호: 횟수}로 넣는다. 아래와 같이 장르별 횟수를 sum에 저장한다. [('pop', {4: 2500, 1: 600, 'sum': 3100}), ('classic', {3: 800, 0: 500, 2: 150, 'sum': 1450})] 장르별 두 개의 고유번호를 정답배열에 추가한다. 원래 sum은 딕셔너리에 추가하고 싶지 않았는데 파이썬 사용이 미숙해 되는대로 하다보니 넣게 되었다. def solution(genres, plays): answer = [] dics = {} for i, g in enumerate(genres): if g not in dics.keys(): dics[g] = {} dics[g][i] = plays[i] sorted_dic = ..
[프로그래머스] 동적계획법 1. N으로 표현
풀이 어렵다 ㅠ 레벨 3.., 처음 생각한 로직은 이렇다. numbers는 연산을 해서 나온 결과값을 키로 갖고 value로는 그 수가 나올 때까지 사용된 N의 개수이다. 첫 번째 반복문은 연산의 횟수로 최대 8번까지 돌아간다. 두 번째 반복문에선 이전 연산 결과값들에 N을 사칙연산한다. 그러니까 한 번 더 연산하고 numbers에 추가한다. number를 찾으면 반환한다. def solution(N, number): numbers = { N: 1 } num_of_n = 2 while True: for item in list(numbers): if item*N not in numbers: numbers[item*N] = num_of_n; if item+N not in numbers: numbers[ite..
[프로그래머스] 탐욕법 4. 구명보트
문제 풀이 1. 오름차순 정렬한다. 2. 제일 가벼운 사람과 제일 무거운 사람의 무게를 더해 리밋과 비교한다. 3. 만약 리밋을 초과하면 제일 무거운 사람은 누구와도 동승할 수 없음을 의미하기 때문에 혼자 보낸다. 리밋을 초과하지 않으면 둘을 같이 태워 보낸다. 4. 남은 사람들로 위의 과정을 반복한다. def solution(people, limit): answer = 0 first = 0 last = len(people) - 1 people.sort() while first