728x90 ALGORITHM35 [백준 11725] 트리의 부모 찾기 문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 루트 없는 트리가 주어지고 각각 노드의 부모노드가 무엇인지 출력하는 문제이다. 알고리즘 설계 이중 vector을 사용하여 간단한 트리를 만들어준다. queue에 1을 넣어 큐가 비어있지 않을떄 실행되는 while을 돌려준다. 큐에 있는 노드와 연결된 노드들의 부모 노드를 queue의 처음으로 정해주고, 연결된 노드들을 queue에 넣어준다. 이후 2번째 노드부터 부모노드가 무엇인지 출력한다. 코드 #include #include #include.. 2023. 10. 18. [백준 1068] 트리 문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 분석 노드의 개수가 입력 되고 그 개수에 맞춰 부모 노드가 누구인지 정해준다. 이후 없앨 노드가 입력되고 없앤 상태의 트리에서 리프노드가 몇개인지 세는 문제이다. 알고리즘 설계 이중 vector을 사용하여 간단한 트리를 만들어준다. 루트 노드에서 DFS를 돌린다. DFS에 매개변수로 들어간 수가 지운 노드라면 return해준다. 만약 자식 노드가 없거나, 자식이 하나인데 그 자식이.. 2023. 10. 18. [백준 1463] 1로 만들기 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 분석 수가 입력 되고 그 수가 3으로 나눠지면 3으로 나누고, 2로 나눠지면 2로 나누고, 안 나눠진다면 1을 뺴는 간단한 문제다. 알고리즘 설계 수가 2로 나눠지면 2를 나눈 값을 넣고, 3으로 나눠진다면 3으로 나누고, 다 아니라면 1을 뺸다. 코드 #include #include using namespace std; int main() { int index; queue q; cin >> index; q.push(make_pair(index, 0)); while (!q.empty()) { if (.. 2023. 10. 18. [백준 5525] IOIOI 문제 https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 문제 분석 우선 n과 m을 입력 받는다. n은 IOI문자열의 크기이다. n이 1이라면 IOI, 3이라면 IOIOIOI이다. m은 확인할 문자열의 크기이다. 받은 문자열에 n에서 입력 받은 크기의 문자가 몇개 있는지 세는 문제이다. 알고리즘 설계 입력 받을 수 있는 것을 모두 입력 받는다. 이후 for문을 돌려 0부터 m, 즉.. 2023. 10. 18. [백준 14940] 쉬운 최단거리 문제 https://www.acmicpc.net/problem/14940 문제 분석 지도의 크기가 우선 정해진다. 갈 수 없는 곳은 0, 갈 수 있는 곳은 1, 시작 위치는 2로 표시 된다. 2에서 시작하여 좌우양옆으로 방문한 순서를 출력해주는 문제이다. 여기서 갈 수 있는 곳 1인 곳인데 갈 수 없는 곳이라면 -1로 출력한다. 알고리즘 설계 우선 지도의 크기를 정해서 지도를 그린다. 시작 위치는 따로 관리하며 지도엔 0으로 표시한다. 갈 수 있는 곳은 -1로 표시하여 나중에 1번쨰로 도착한 곳과 헷갈리지 않도록 해준다. 이후 BFS를 사용하여 몇번쨰에 도착하였는지 map에 적어준 후 출력한다. 유의점 x축과 y을 착각하지 않고 적는 것이 중요하다. 코드 #include #include using nam.. 2023. 10. 18. [백준 16928] 뱀과 사다리 게임 문제 https://www.acmicpc.net/problem/16928 문제 분석 1이라는 위치에서 100이라는 위치로 이동하는 문제이다. 다만 주사위로 1~6칸을 갈 수 있으며, 사다리와 뱀이라는 변수가 존재한다. 사다리는 작은 수에서 큰 수로 올라가며, 뱀은 큰 수에서 작은 수로 내려오는 형태이다. 이 문제는 BFS로 풀 수 있다. 알고리즘 설계 방문을 확인할 vector 또는 배열, 사다리 및 뱀을 체크할 vector 또는 배열을 만든다. 이후 사다리와 뱀을 입력받아 연결 시켜준다. 1에서 시작하며 추가로 1 ~ 6을 더하여 계속 방문 확인할 배열과 queue에 넣어준다. 주사위 수에 사다리 또는 뱀이 있다면 움직여준다. 100에 도착하면 while에서 벗어나 몇번쨰에 방문하였는지 확인한다. 유의.. 2023. 10. 18. [백준 10026] 적록색약 문제 링크 https://www.acmicpc.net/problem/10026 문제 분석 R, G, B 총 3가지의 색상이 있고, 각각 구역이 나눠져 있다. 나눠진 구역이 총 몇개인지 세는 문제이다. 여기서 적록색약이 아닌 사람이 봤을땐 R, G, B 모두 나누어져 있지만, 적록색약인 사람이 본다면 R과 G는 하나의 구역으로 생각 하면 된다. 알고리즘 설계 이중 vector을 사용하여 판을 구성하고, 입력 받는다. 적록색약이 아닌 사람과 적록색약인 사람이 보는 함수를 따로 만들어준다. 이후 BFS을 사용하여 탐색해준다. 코드 #include #include #include using namespace std; int loop, first = 0, second = 0; vector map; int addX.. 2023. 10. 18. [백준 24479] 알고리즘 수업 - 깊이 우선 탐색 1 https://www.acmicpc.net/problem/24479 문제 분석 입력 받아 그래프를 만들고 DFS로 탐색을 하고, 탐색 순서를 기록하여 출력하는 형식에 문제이다. 이 문제는 DFS만 알고 있다면 딱히 문제 없이 풀 수 있을 것이라고 생각된다. 코드 #include #include #include using namespace std; vector graph; vector visited; int result[100001]; int cnt = 0; void DFS(int index); int main() { int n, m, r, input1, input2; cin >> n >> m >> r; graph.resize(n + 1); visited.resize(n + 1, false); while .. 2023. 8. 1. [백준 1260] DFS와 BFS https://www.acmicpc.net/problem/1260 문제 분석 입력을 받아 그래프를 만들고, DFS로 탐색 하였을때와 BFS로 탐색하였을때 각각 출력해주는 형태의 문제이다. 이 문제는 DFS와 BFS를 이해하고 있다면 문제 없을거라고 생각한다. 코드 #include #include #include using namespace std; void DFS(int index); void BFS(int index); vector graph; vector visited; int n, m, v; int main() { int input1, input2; cin >> n >> m >> v; graph.resize(n + 1); visited = vector(n + 1, false); while (m--).. 2023. 8. 1. [백준 11724] 연결 요소의 개수 https://www.acmicpc.net/problem/11724 문제 분석 간단한 DFS활용 문제이다. 입력을 받아 그래프를 만들고, 그래프를 이루고 있는 덩어리가 몇개인지 세는 형태의 문제이다. DFS를 이해했다면 무리 없이 풀 수 있는 문제라고 생각한다. 코드 #include #include using namespace std; static vector A; static vector visited; void DFS(int v); int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N, M; cin >> N >> M; A.resize(N+1); visited = vector(N+1, false).. 2023. 8. 1. [알고리즘 이론] DFS와 BFS 더보기* DFS와 BFS 이해 전 그래프에 대한 이론을 알고 있다면 도움이 될 것이다. DFS 깊이 우선 탐색(Depth-First Seartch)는 그래프 완전 탐색 기법 중 하나이다. DFS는 그래프의 시작 노드부터 시작하여 탐색할 분기를 정하고, 끝까지 탐색 후 다음 분기로 넘어가서 다시 탐색하여 모두 다 탐색하는 알고리즘이다. DFS는 Stack 또는 재귀함수를 이용하여 구현할 수 있으며 시간 복잡도는 O(노드 수 + 에지 수)이다. 재귀함수를 사용할떈 스택 오버플로를 조심하며 사용해야한다. 우선 이런 그래프가 있다고 가정해보자. 이 그래프를 인접 리스트로 표현한다면 아래처럼 표현 할 수 있다. 1) 1부터 시작한다고 가정하고 1을 Stack에 넣음과 동시에 1이 들어 왔다는 것을 체.. 2023. 8. 1. 이전 1 2 3 다음 728x90
