나그네

27497번: 알파벳 블록 문제 https://www.acmicpc.net/problem/27497 27497번: 알파벳 블록 첫째 줄에 버튼을 누른 횟수 $N$이 주어진다. $(1 \leq N \leq 1\,000\,000)$ 둘째 줄부터 $N$개의 줄에는 버튼을 누른 순서대로 누른 버튼에 대한 정보를 주며 아래와 같은 형식으로 주어진다. 1 c : 문자열 www.acmicpc.net 풀이 덱의 기본적인 쿼리를 사용하는 문제다. 가장 마지막에 추가한 수가 덱의 앞인지 뒤인지 판단하기 위해 스택을 만들어 하나씩 pop 하며 판단했다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); deque ..

27496번: 발머의 피크 이론 문제 https://www.acmicpc.net/problem/27496 27496번: 발머의 피크 이론 각 시간에 따른 혈중 알코올 농도는 {0.045, 0.089, 0.133, 0.131, 0.127}이다. 따라서 지금으로부터 2시간 후와 3시간 후, 총 두 시간 동안 혈중 알코올 농도를 유지할 수 있다. www.acmicpc.net 풀이 대회 때 누적합으로 풀었다가 빼는 배열의 크기를 제한하기 어려웠다. 그래서 그냥 더하다면서 배열에 더한 값을 저장하고 시간이 지속 시간보다 커지면 차례대로 빼가면서 범위를 만족하는지 확인했다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin...

27495번: 만다라트 만들기 문제 https://www.acmicpc.net/problem/27495 27495번: 만다라트 만들기 1번째 줄에는 “#x. “를 출력한 다음, 사전순으로 가장 먼저 오는 중간 목표를 출력한다. 숫자가 알파벳보다 사전순으로 먼저 오고, 알파벳 대문자가 알파벳 소문자보다 사전순으로 먼저 온다. 2 www.acmicpc.net 풀이 배열에서 (1,1), (1,4), (1,7), (4,1), (4,7), (7,1), (7,4), (7,7) 8점의 좌표와 문자열을 문자열 사전순으로 정렬하고 좌표를 (x, y)라고 한다면 (x-1, y-1)부터 (x+1, y+1)까지 (x, y)를 제외한 값을 또다시 정렬해 차례대로 출력하면 된다. 출력 형식만 잘 지켜서 구현하면 된다. 코드 #i..

27494번: 2023년은 검은 토끼의 해 문제 https://www.acmicpc.net/problem/27494 27494번: 2023년은 검은 토끼의 해 흑묘 복권의 티켓 수 $N$이 주어진다. $(1 \leq N \leq 10\,000\,000)$ www.acmicpc.net 풀이 2023부터 N까지 차례대로 문자열로 바꾸어 어느 한 부분에 차례대로 2, 0, 2, 3이 존재하는지 확인하면 되는 문제다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, ans = 0; cin >> n; for (int i = 2023; i

4485번: 녹색 옷 입은 애가 젤다지? 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 2차원 배열에서 (0,0)에서 (N-1, N-1)까지 한 칸씩 이동하며 각 칸의 숫자의 합이 최소가 되도록 하는 문제다. 다익스트라 알고리즘을 2차원 배열로 만들어서 풀었다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 2차원 배열에서의 BFS처럼 dy, dx 배열을 만들어..

18223번: 민준이와 마산 그리고 건우 문제 https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 풀이 최단 경로 중에 민준이가 위치한 정점이 포함되는지 확인하는 문제다. 다익스트라 알고리즘으로 두 정점 간의 최단 경로를 구할 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 건우가 위치한 P 정점이 최단 경로 위에 있다면, (시작점부터..

17396번: 백도어 문제 https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 풀이 0번에서 N-1번까지 가는 최단 경로를 구하는 문제다. 몇 가지 예외만 처리해 주면 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 예외인 경우는 넥서스를 제외한 시야가 밝혀져 있는 정점은 지나갈 수 없다. 따라서 간선을 입력받을 때 해당 정점과 연결..

1963번: 소수 경로 문제 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 4자리 소수 A, B를 입력받고 A를 적절히 바꾸어 B를 만드는데 몇 번 만에 바꿀 수 있는지 구하는 문제다. 바꾸는 데는 규칙이 있다. 1. 한 번에 한 자리 수만 바꿀 수 있다. 2. 바뀐 수도 반드시 소수여야 한다. 소수인지 판단하기 위해 에라토스테네스의 체를 사용해 소수를 걸러준다. 그리고 bfs를 돌렸다. A를 방문처리하고 큐에 넣는다. 이때 큐는 pair를 원소..

2211번: 네트워크 복구 문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이 1번 정점의 슈퍼컴퓨터에서 모든 정점에 이어야 하므로 최소 시간에 연결이 돼야 하므로 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 문제에서 요구하는 것은 이어야 하는 간선의 수와 그 간선이다. 따라서 -1로 초기화되어 있는 prev 배열을 만..

10282번: 해킹 문제 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 의존성이 있는 컴퓨터에 바이러스가 전염되는 시간과 몇 대의 컴퓨터가 감염되었는지 구하는 문제다. 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] !! 신경 쓸 점이 두 가지 있다. 1. 테스트 케이스가 여러 개이므로 배열과 변수 초기화에 신경 써야 한다. 2. a가 b에 의존하고 있..