예나 지금이나

https://www.acmicpc.net/problem/9663   풀이 과정 백트래킹의 대표적인 문제입니다. 백트래킹은 DFS 또는 BFS를 사용하여 기본적으로 완전탐색을 기반으로 합니다. 다만, 해가 되지 않을 것으로 판단되는 경우에는 더 이상 탐색을 진행하지 않고 다음 탐색을 이어갑니다.  N-Queen의 문제로 예를 들자면, 첫 번째 행에 퀸을 놓았다면 더 이상 첫 번째 행에 다른 퀸들을 놓을 수 없습니다. 서로 공격 대상이 되기 때문입니다. 그렇기 때문에 첫 번째 행에 다른 퀸들을 놓을 수 있는 경우의 수는 탐색하지 않는 것입니다. 이렇게 문제의 해가 되지 않는 경우의 경우 유망하지 않다고 하며, 해가 될 가능성이 있는 경우 유망하다(Promising)고 합니다. 유망하지 않은 노드를 쳐내는 ..

https://www.acmicpc.net/problem/1931     풀이 과정 이 문제를 처음 봤을 때 그리디 알고리즘을 적용해서 풀어야겠다 생각했지만 문제 접근 자체가 쉽지 않았습니다. 가장 먼저 생각한 방법은 회의시간이 가장 짧은 순서대로 회의를 배정하는 방식이었습니다.그리고 bool 값을 지닌 리스트를 가장 늦게 끝나는 회의 시간의 길이만큼 False로 초기화하고, 회의시간의 숫자를 인덱스로 사용하여 True로 바꿔주는 것입니다. [3, 5]의 회의가 배정이 됐다면 [False, False, True, True, True, ...] 이런 식으로 배정된 회의와 겹치지 않게 문제를 해결하려고 했습니다만..문제에서 주어진 조건이 회의 시간의 범위는 약 21억까지입니다. 만약에 가장 늦게 끝나는 회의..

https://www.acmicpc.net/problem/2178    (1, 1) 지점에서 (N, M)의 위치로 가기 위한 최단거리를 구하는 문제입니다.  출발 지점이 주어졌고, 목표 지점이 주어졌습니다. 그래프 탐색 알고리즘을 적용해 볼 수 있겠습니다. 물론 최단경로를 찾는 문제이기 때문에 다익스트라 알고리즘과 같은 최단경로 알고리즘을 사용해도 되겠습니다.그래프 탐색 알고리즘의 종류에는 BFS와 DFS가 있는데 이 문제는 BFS를 사용해서 풀어야합니다.DFS는 최단거리를 보장해주지 못하기 때문입니다. 그에 비해 BFS는 시작지점과 도착지점의 최단거리를 보장합니다. from collections import deque# 상하좌우 방향dx = [0, 0, -1, 1]dy = [1, -1, 0, 0]def..

https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 $-1$ 출력한다. www.acmicpc.net 풀이 과정 터렛의 위치가 (0, 0)이고 적까지의 거리가 3이라고 가정했을 때, 적이 있을 수 있는 위치는 어디일까요? (3, 0)이 될 수도 있고, (-3, 0)이 될 수도 있고, (0, 3)이 될 수도 있습니다. 즉, 원점 (0, 0)으로부터 반지름이 3인 원을 그렸을 때 원이 지나는 좌표들이 적이 있을 수 있는 위치입니다. 터렛이 둘이니까 두 원이 교차하는 지점에 적이 있을 수 있겠죠. 이 문제는 두 원의 교점의 개수를 구하는 문제입니다. 여..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그www.acmicpc.net     풀이 과정 가지고 있는 랜선을 잘라서 N개를 만들기 위한 최댓값을 찾는 문제입니다. 가장 쉽게 생각할 수 있는 방법은 1부터 1씩 더해가면서 최댓값을 찾는 방법입니다. 하지만 랜선의 길이의 범위가 2³¹-1보다 작거나 같은 자연수입니다. 1씩 더해가면서 찾는 방법을 선택한다면 시간복잡도는 O(N)으로 최악의 경우에 2³¹-1(약 21억) 번의 검사를 수행해야 하고,..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일www.acmicpc.net       풀이 과정 그래프 이론을 배운 상태이며, 이 문제를 그래프 탐색으로 풀어야겠다고 생각이 들었으면 구현 자체는 크게 어려운 문제는 아니라고 생각합니다. 그래프 탐색 알고리즘을 사용할 때 DFS를 쓸 것인지, BFS를 쓸 것인지만 결정하면 됩니다. 하지만 이 문제에서 DFS는 적합하지 않습니다. 저희는 노드를 탐색하는 것이 목표가 아니라, 시작 지점에서 도착 지점까지..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사www.acmicpc.net      풀이 과정 이 문제를 풀기 위해서는 기본적으로 DFS와 BFS 알고리즘을 알아야합니다.DFS란 그래프의 깊이 우선 탐색 알고리즘이고, BFS란 그래프의 너비 우선 탐색 알고리즘을 의미합니다. DFS(깊이 우선 탐색)은 루트 노드에서부터 탐색을 시작해서 하나의 분기가 끝날때까지 타고 내려가서 탐색을 수행한 다음, 탐색이 끝나면 다음 분기로 넘어가서 탐색을 ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.www.acmicpc.net       풀이 과정 제가 저 문제를 처음 접했을 때 들었던 생각 중 하나는  3으로 나누어 떨어지면 가장 먼저 3으로 나눈다.3으로 나누어 떨어지지 않고, 2로 나누어 떨어지면 2로 나눈다.2과 3 모두 나누어 떨어지지 않으면 1을 뺀다.이렇게 생각하고 풀이를 하려고 했는데 예제 입력에 보이듯이 10을 입력하면 3이 나와야 합니다.제가 생각한 풀이로는 10 -> 5 -> 4 -> 3 -> 1의 순서를 거쳐서 4번 만에 1에 도달하는 것으로 답이 나오게 됩니다.하지만 연산을 최소로 사용하려면 10 -> 9 -> 3..