https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 그래프 탐색 문제의 또다른 대표 형식인 길찾기 문제이다. 길찾기 문제의 경우 방향값을 미리 코드에 짜두고 for문으로 순회하는 방식의 기법을 항상 기억하고 있어야 한다. 그리고 이 문제의 경우 시작점이 정해져 있고, 도착점까지의 최단거리를 구해야 하기 때문에 한쪽으로 끝까지 들어가는 DFS보다 자신을 기준으로 한레벨씩 나아가는 BFS 방식이 적합하다. 따라서 이 문제의 코드를 짜기 전에 - 길찾기 문제 -> 좌표 활용 - 최단거..
https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 그래프 탐색 문제이다. 처음에는 아무 생각 없이 DFS 방식으로 접근했는데, 문제의 조건을 보니 BFS로 푸는게 가장 옳은 방법인것 같다. 자신의 기준으로 최대 2단계 레벨에 해당하는 친구들의 수를 세서 비교하는 문제라 한쪽으로 끝까지 파고 들어가는 DFS보단 레벨별로 훑어나가는 BFS의 방식이 딱 알맞다. 코드 구성은 BFS에서 최대 2번째 레벨까지만 탐색을 진행하고 카운트를 비교하는 방식. bfs..
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net DFS와 BFS를 둘 다 연습해볼 수 있는 문제이다. 간단한게 DFS와 BFS의 풀이방식을 살펴보면 - DFS(깊이 우선 탐색): 스택 or 재귀를 사용해서 구현 - BFS(너비 우선 탐색): 큐를 사용해서 구현 나는 보통 DFS에서 재귀를 사용해서 구현하는데 파이썬의 경우 최대 재귀 횟수가 1000번으로 고정되어 있기 때문에 대부분의..
Key 기준으로 정렬 sorted( dic.items() ) : 오름차순 정렬 , 정렬된 딕셔너리를 딕셔너리 리스트 형으로 반환 sorted( dic.keys() ) : 오름차순 정렬 , key값만 정렬해서 리스트로 반환 둘 다 sorted를 거치면 [] 안에 씌워져 나오게 된다. reverse = True를 추가하면 내림차순으로 변경됨! dic = {} dic['a'] = 1 dic['c'] = 2 dic['b'] = 4 dic['e'] = 3 print(dic) #{'a': 1, 'c': 2, 'b': 4, 'e': 3} print(sorted(dic.items())) #[('a', 1), ('b', 4), ('c', 2), ('e', 3)] print(sorted(dic.items(), revers..
https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 여러 책 이름들을 입력받는데 이 중 가장 많이 중복된 책의 이름을 출력하면 되는 문제이다. 중복되는 요소의 count -> C++에서는 map, 파이썬에서는 dictionary를 이용하면 된다. 여기서 한 가지 더 생각해야 하는 것은 count가 같은 책 이름들이 있을 때, 사전순으로 나열해 가장 앞에 오는 순서의 책 이름을 출력해 주어야 하는 것인데, 결국 map, 또는 dic을 써서 카..
https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net min-heap을 이용해 해결하면 된다. 절댓값이 작은 순서대로 정렬 되어야 하고 같은 값이 두개 이상이라면 이 중에서 원래 값이 더 작은(= 음수) 값을 먼저 출력해야 하므로 heapq의 min-heap에 (절댓값, 원래값)의 튜플 형태로 원소를 넣어 주면 퓨플의 순서대로 정렬을 할 수 있다. import sys import heapq input = sys.stdin.rea..
- 최소 힙(min-heap)의 구조 - 삽입/삭제: O(logN) import heapq로 사용 가능 push: heapq.heappush(hq, item) pop: heapq.heappop(hq) import heapq pq = [] heapq.heappush(pq, 6) heapq.heappush(pq, 12) heapq.heappop(pq) heapify - 리스트 x를 heap으로 변환 x = [4, 3, 1, 2, 5, 6] print(x) # [4, 3, 1, 2, 5, 6] heapq.heapify(x) print(x) # [1, 2, 4, 3, 5, 6] heapq를 사용하는 이유? from queue import PriorityQueue로 일반 우선순위 큐도 사용할 수 있다. 하지만 이..