코딩테스트
-
[Python] 프로그래머스 / 붕대 감기코딩테스트 2024. 8. 5. 15:13
문제 링크단순한 구현 문제이다. 정답 코드from collections import dequedef solution(bandage, health, attacks): # [5, 1, 5], 30, [[2, 10], [9, 15], [10, 5], [11, 5]] #시전 시간, 초당 회복량, 추가 회복량 T = deque(map(lambda x : x[0], attacks)) P = deque(map(lambda x : x[1], attacks)) fht = bandage[0] hps = bandage[1] sh = bandage[2] conti = 0 blood = health for t in range(1,..
-
[Python] 프로그래머스 / 네트워크코딩테스트 2024. 8. 5. 14:45
문제링크 Floyd-Warshall Dijkstra, Bellman-Ford와 함께 그래프에서 최적의 경로를 찾는 알고리즘으로는 Floyd-Warshall이 있다.이중 Bellman-Ford는 사실 거의 쓸 일이 없고, 보통은 Dijkstra를 이용할 때가 많다. 일단 시간복잡도도 O(n^2)로 낮은 편이기 때문이다. 그러나 모든 i to j에 대한 정보가 필요하다면, Dijkstra를 n번 돌려 O(n^3)을 구현하는 것보다, Floyd-Warshall로 한큐에 O(n^3)로 끝내는 게 더 간결한 코드이다. Floyd-Warshall 코드는 극도로 단순하다. k(경유지), i(출발지), j(종착지) 순으로 for문 돌리기만 하면 끝. 실전 코테에서 최적 경로 뿐만이 아니라 생각보다 다양한 용도로 Flo..
-
[Python] 프로그래머스 / 공원 산책코딩테스트 2024. 8. 3. 09:27
문제링크 정답 코드def solution(park, routes): n = len(park) m = len(park[0]) d = {'E' : (0, 1), 'W' : (0, -1), 'N' : (-1, 0), 'S' : (1, 0)} for i in range(n) : for j in range(m) : if park[i][j] == 'S' : x = i y = j break for route in routes : direction, distance = route.split() distance = int..
-
[Python] 프로그래머스 / 추억 점수코딩테스트 2024. 8. 3. 09:23
문제 링크 아이디어 1 : defaultdict활용일반적인 딕셔너리는 키가 존재하지 않을 때 에러를 발생시키지만, defaultdict로 하면 어떤 키를 호출하더라도 "기본값"을 반환하여 에러를 피할 수 있다. 다만 어떤 기본값을 반환할지 지정해줘야 한다. (int, list, set, labmda 등)가장 많이 쓰이는 것은 int, list인 것 같다.from collections import defaultdicta = defaultdict(list)a[2].append(3)print(a[2])# [3] lambda도 기본값으로 설정 가능하다:from collections import defaultdict# 기본값을 0으로 설정하는 lambda 함수 사용student_scores = defaultdic..
-
[Python] 프로그래머스 / 2018 KAKAO BLIND RECRUITMENT / [3차] 자동완성코딩테스트 2024. 6. 19. 23:08
문제 링크 트라이(Trie) 자료구조최근에야 검색창 자동완성 기능에 NLP가 활용되지만, 고전적으로는 트라이 자료구조가 활용된다. 여러 단어를 Tree 자료 구조로 관리하는 것이다. 이 문제에서 예시로 들고 있는, gone, guild를 예시로 들면 다음과 같다 : (root) | g / \ o u / \ n i / \ e l | d 더 자세한 설명은 이 블로그에서 상세히 작성해놓은 것이 있다. 정답 코드#트라이 자료구조 만들기class TrieNode: def __init__(self): self.children..
-
[Python] 백준 1261 : 알고스팟코딩테스트 2024. 6. 17. 23:02
어려워보이지만, 결국은 Dijkstra0은 빈칸, 1은 벽이다. 좌측 상단에서 우측 하단으로 이동할 때, 최소한의 벽을 파괴하고 도달해야 한다. 이 문제는 잘 살펴보면 Dijkstra 문제이다. (x좌표, y좌표, 뚫은벽 개수) tuple을 queue에 넣어 관리하면서 최소로 벽을 뚫어나가면 되는 것. 정답코드import heapqimport sysM, N = map(int, input().split())graph = []for i in range(N) : row = [] a = input() for j in range(M) : row.append(int(a[j])) graph.append(row)visited = [[False] * M for _ in range(N)]..
-
[Python] 백준 1197 : 최소 스패닝 트리코딩테스트 2024. 6. 17. 22:54
문제 링크 Kruskal 알고리즘 Kruskal 알고리즘 자체에 대한 설명은 여기로. 최소 스패닝 트리(MST) 문제에서, 코드로 구현하기 더 쉬운 것은 Prim 알고리즘이지만, 때때로 Kruskal 알고리즘이 필요할 때가 있다. Kruskal 알고리즘은 사실 사람 입장에서 더 쉬운 방법이라고 생각한다. 왜냐하면 "간선"을 고를 때, Cycle이 되는지 안 되는지 파악하는 코드가 꽤나 복잡하기 때문이다. 그렇기에 다음의 코드를 알아두면 좋다.#시작은, 모든 노드의 부모 노드는 자기 자신#0번 노드의 부모는 0, 1번 노드의 부모는 1...parent = list(range(V))#부모 노드를 찾는 코드#부모가 자기 자신이 아니라면 부모의 부모를 재귀적으로 찾는 것def find(parent, x): ..
-
[Python] 프로그래머스 / 이중우선순위큐코딩테스트 2024. 6. 17. 21:01
문제 링크heapq의 함정자료구조 시간에 다들 Max Heap과 Min Heap 구조에 대해 배웠을 것이다. Tree 구조를 이용해서 리스트에서 최소값이나 최대값을 찾는 시간을 O(logN)으로 줄인 획기적인 기법이다. 이를 파이썬에서 쉽게 사용할 수 있도록 지원해주는 라이브러리가 heapq이다. (Min Heap만 가능) 그런데, 코테에서 아무 생각 없이 heapq를 자주 사용하다보면, heapq를 그저 시간효율성이 좋은 sort()로 착각하기 쉽다는 것이다! 여기 예시가 있다.import heapqa = [21, 20, 8, 19, 1, 14, 6, 8, 30, 26]heapq.heapify(a)a#[1, 8, 6, 19, 20, 14, 8, 21, 30, 26] 위에서 보면, a[0]가 최소값이 것..