일지 & 개발

문제 요약 알고리즘 분류: bfs, 구현, 시물레이션 난이도:Silver1 문제내용: 사가형이 가로, 세로 길이와 색칠한 범위가 주어진다. 색칠하지 않은 구역개수와 각 구역의 넓이를 오름차순으로 출력해라 사이트: https://www.acmicpc.net/problem/2583 . 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제풀이 이번 문제는 DFS,BFS 탐색 문제이다. DFS로 풀수있지만 BFS가 DFS보다 속도가 더 빨라서 이번 문제는 BFS로 푸는게 좋다. BFS 탐색 알고리..

문제 요약 알고리즘 분류: bfs, 구현, 시물레이션 난이도:Silver1 문제내용: 테스트 케이스 개수가 주어진다 각 테스트 케이스마다 한변의 정사각형 길이, 시작점, 도착점을 준다. 나이트가 시작점에 도착점까지 최소 이동을 구해라 사이트: https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제풀이 이번 문제는 BFS 탐색 문제이다. BFS 탐색 알고리즘에 관한 자세한 설명은 여기에서 확인 해보면 알 수 있다. 기존 BFS는 각 노드간의 탐색인데..

문제 요약 알고리즘 분류: bfs 난이도:Silver2 문제내용: 넓이 우선 탐색후 각 노드 마다 방문 순서(내림차순)를 출력해라 사이트: https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 문제풀이 이번 문제는 BFS 탐색 문제이다. BFS 탐색 알고리즘에 관한 자세한 설명은 여기에서 확인 해보면 알 수 있다. 아래 사이트에 정렬한 바꾸면 되기 때문에 따로 설명은 안하겠다...

문제 요약 알고리즘 분류: bfs 난이도:Silver2 문제내용: 넓이 우선 탐색후 각 노드 마다 방문 순서(오름차순)를 출력해라 사이트: https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 문제풀이 이번 문제는 BFS 탐색 문제이다. BFS 탐색 알고리즘에 관한 자세한 설명은 여기에서 확인 해보면 알 수 있다. 여기 bfs에 추가되는 요건은 2가지이다. 오름차순 정렬 방문..

문제 요약 알고리즘 분류:BFS, 시뮬레이션 난이도: Gold4 문제내용: 0은 길 1은 벽이다. 벽은 한번 부수고 이동가능하다. (0, 0) ~ (N, M)까지의 거리를 구해라 사이트: https://www.acmicpc.net/problem/14502 문제풀이 이번에는 문제 유형은 그래프 탐색중에 BFS탐색 알고리즘이다. BFS 탐색 알고리즘에 대한 설명은 여기에서 확인 해보면된다. 이번 문제는 가로세로 최대 길이가 8이라서 시간 복잡도에 제한은 없지만 구현난이도가 있어서 구현 하는 방법만 알면 쉽게 풀수 있다고 생각한다. 문제 접근방법 처음에 재귀 호출을 하는데 벽을 3개 만든다고 (0, 0)부터 시작해서 4가지 방향 탐색한후 백트레킹 방식으로 돌아올때 벽을 빼고 하면 안된다. 그 이유는 보면 (0..

문제 요약 알고리즘 분류: dfs 난이도: Silver2 문제내용: 아래와 같이 2가지 연산이 가능하다. ×2 1을 오른쪽추가한다. A, 에서 B까지 최소 몇번 연산가능한지 구해라. 사이트: https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제풀이 이번 문제는 dfs 응용하는 문제이다. dfs 대한설명은 여기에서 확인 해보면 된다. 문제 접근 방법 bfs를 응용하는 것인데 위 그림 처럼 queue에 현재 값을 연산후 B보다 작거나 같을때 queue에 저장하면 하고 현재 값 연산 횟수에 +1을 더하면 끝이다. from collections import deque A, B..

문제 요약 알고리즘 분류:BFS, 시뮬레이션 난이도: Gold3 문제내용: 0은 길 1은 벽이다. 벽은 한번 부수고 이동가능하다. (0, 0) ~ (N, M)까지의 거리를 구해라 사이트: https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제풀이 이번에는 문제 유형은 그래프 탐색중에 BFS탐색 알고리즘이다. BFS 탐색 알고리즘에 대한 설명은 여기에서 확인 해보면된다. import sys from collections i..

문제 요약 알고리즘 분류: BFS 난이도: Gold5 문제내용: 위치가 X일때 X - 1, X + 1 이동하면 1초 X * 2는 0초 걸린다. 현재위치 N일때 K까지 이동하는데 최소 시간을 구해라 사이트: https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제풀이 이번에는 문제 유형은 그래프 탐색 관련 문제이다. 다이스트라 알고리즘으로도 풀수 있는데 그보다 구현이 더 쉬운 BFS로 풀수 있다. BFS 알고리즘 관..