https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 조건도 까다롭지 않고 배열의 입력값 범위도 최대 8이어서 시간복잡도 걱정 없이 부르트포스로 풀면 되겠다고 생각하였다. 문제 풀이에서도 딱히 걸리는건 없었고 최대한 시간와 메모리를 쓰면서 코드를 작성했다. 간단히 짚고 넘어갈 부분은 리스트의 얕은 복사와 깊은 복사 부분 정도인것 같다. 처음에 받은 배열을 계속 깊은 복사하면서 BFS를 시도한다. 주어진 지도에서 3개의 좌표에 벽을 세워야 하는데 이는 배열의..
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 겉으로 보면 간단해 보이지만 굉장히 시간초과가 많이 발생하는 문제였다. 처음부터 문제의 조건과 각 풀이방법별 예상 시간 복잡도를 계산해본 후 코드작성에 들어가야 헤매지 않을 수 있는 문제인것 같다. 먼저 문제의 설명과 예시를 보면 가장 먼저 생각나는게 BFS일테고, 각 좌표별로 BFS를 돌려 카운트를 세면 당연히 시간초과가 난다. N by M 행렬이고 N과 M은 각각 10^3..
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..