본문 바로가기

백준8

[백준] C++ 1991번 트리 순회 문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 접근 방법 트리를 순회하는 방법에 대한 문제이다. 먼저 트리를 구현하는 방법에는 여러 가지가 있는데 그중에서 map으로 트리를 구현하였다. map의 key에 부모 노드를 저장하고, pair에는 각각 왼쪽 자식과 오른쪽 자식을 저장하였다. 순회는 재귀로 진행하여 자식 노드가 없을 때 종료되게 하였다. 코드 #include #include using namespace std; int .. 2023. 2. 21.
[백준] C++ 1389번 케빈 베이컨의 6단계 법칙 문제 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 접근 방법 모든 사람들이 연결되어 있는 상황을 그래프로 표현해 보았다. 이때 두 사람 간의 이어지는 단계는 그래프에서의 두 정점의 최단 거리라고 볼 수 있다. 케빈 베이컨 게임은 모든 사람들 간의 최단 거리가 필요하므로 이때 적용할 수 있는 알고리즘은 플로이드 와샬 알고리즘이다. 코드 #include #include #include using .. 2023. 2. 12.
[백준] C++ 1260번 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 접근 방법 주어진 그래프에 대하여 dfs와 bfs의 수행 결과를 출력하는 간단한 문제이다. 그래프는 vector를 통해 구현하였고 시작점으로부터 dfs와 bfs를 수행하여 방문된 점을 출력하였다. 코드 #include #include #include #include using namespace std; int n, m, v, x, y; bool check.. 2023. 2. 8.
[백준] C++ 2257번 화학식량 문제 https://www.acmicpc.net/problem/2257 2257번: 화학식량 첫째 줄에 화학식이 주어진다. 화학식은 H, C, O, (, ), 2, 3, 4, 5, 6, 7, 8, 9만으로 이루어진 문자열이며, 그 길이는 100을 넘지 않는다. www.acmicpc.net 접근 방법 괄호로 무언가를 계산하는 문제의 해결방법 중에 하나는 스택을 이용하는 것이다. int를 원소로 하는 스택을 선언하여 문제를 접근하였다. H, C, O일 경우는 1, 12, 16을 push 하였다. '('가 입력으로 올 때에는 그냥 push를 하면 '('의 아스키코드인 40이 push가 되기 때문에 오류가 생길 수 있어 사용될 일이 없는 값인 -1로 push를 하였다. ')'가 입력으로 올 때는 '('가 나올 .. 2023. 2. 4.
[백준] C++ 1074번 Z 문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 접근 방법 주어진 배열을 좌표라 생각을 하면 4개의 사분면으로 나눌 수 있다. 어느 사분면에 따라 앞서 방문해야 할 칸의 개수가 달라진다. 좌표가 3사분면에 있다고 가정할 때, 1사분면과 2사분면의 모든 칸들을 방문하여야 한다. 앞서 방문해야 할 칸들의 값을 모두 더하고, 현재 좌표가 위치한 사분면을 기준으로 다시 4등분을 하여 n=1이 될 때까지 반복으로 수행하였다. 코드 #inc.. 2023. 2. 3.
[백준] C++ 17219번 비밀번호 찾기 문제 https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 접근 방법 map을 사용하여 사이트 주소와 비밀번호 쌍을 저장하였다. key를 사이트 주소로, value를 비밀번호로 저장하여 원하는 사이트 주소의 비밀번호를 찾을 수 있게 하였다. 코드 #include #include #include using namespace std; int n, m; string site, password; map text; int mai.. 2023. 2. 2.

티스토리툴바