문제풀기(63)
-
백준 1987번 (골드 4) : 알파벳
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net - 기본적인 생각은 처음부터 옳았으나, queue에 들어가는 아이들 중에서 중복이 있을 수 있다는 것을 전혀 생각하지 못하고 계속해서 deque를 이용해서 queue를 구현해서 사용했다. - 이 때문에 계속 시간 초과가 났고, 결국 set을 이용해서 queue를 구현하자 중복이 제거되어서 시간 초과가 해소되었다. import sys r,c = map(int, sys.stdin.readlin..
2021.08.09 -
백준 1260번 (실버 2) : DFS와 BFS
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net - 단순히 BFS, DFS를 구현할 수 있으면 된다. - 중요한 것은 간선이 여러개면 작은 정점부터 방문하기 때문에, DFS, BFS를 실행하기 전에 sort를 한번 해줘야 한다는 점이다. import sys from collections import deque n,m,v = map(int, sys.stdin.readline().rstrip().split())..
2021.08.09 -
백준 1463번 (실버 3) : 1로 만들기
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net import sys n = int(sys.stdin.readline().rstrip()) lists = [0]*(n+1) answer = 0 for i in range(1,n+1): if i*3 lists[i]+1): lists[i*3] = lists[i] + 1 if i*2 lists[i]+1): lists[i*2] = lists[i] + 1 if i+1 lists[i]+1): lists[i+1] = lists[i] + 1 print(lists[n]) - 0부터 n까지의 인덱스를 가지고 있는 lists를 만든..
2021.08.09 -
4. 정렬
1. 선택 정렬 (Selection Sort) - 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸고 .... => 정렬되지 않은 부분에서 가장 작은 것을 선택해서 정렬되지 않은 부분의 가장 앞의 원소와 바꾸는 것 - 시간 복잡도 : O(N^2) def selectionSort(array): for start_index in range(len(array)): minimum_index = start_index for now_index in range(start_index+1, len(array)): if array[now_index] < array[minimum_index]: minimum_index = now_index array[st..
2021.08.08 -
3. DFS/BFS
1. 그래프 (1) 인접 행렬 방식 - 2차원 배열로 그래프의 연결 관계를 표현하는 방식 INF = 999999999 graph = [ [0,7,5], #0번 노드는 0번 노드와 거리가 0, 1번 노드와 거리가 7, 2번 노드와 거리가 5 [7,0,INF], #1번 노드는 0번 노드와 거리가 7, 1번 노드와 거리가 0, 2번 노드와 연결되어있지 않음 [5,INF,0] #2번 노드는 0번과 거리가 5, 1번 노드와는 연결되어있지 않음, 2번 노드와 거리가 0 ] - 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비됨 (2) 인접 리스트 방식 - 리스트로 그래프의 연결 관계를 표현하는 방식 INF = 999999999 graph = [ [(1,7),(2,5)], #0번 노드는 1번 노드..
2021.08.04 -
2. 구현
- 흔히 '피지컬'을 보기 위한 문제라고 여겨지는 것 같다 - 메모리 제약 사항을 고려하자 - '완전 탐색' : 탐색해야 할 전체 데이터의 개수가 100만 개 이하일 때 사용하면 적절하다 1. 왕실의 나이트 (책 '이것이 코딩 테스트다' 中) 행복 왕국의 왕실 정원은 체스판과 같은 8 × 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 이처럼 8 × 8 ..
2021.07.28