BOJ

📚 문제 링크: https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 💡 접근법 BFS를 이용하여 각 노드까지의 거리를 구하고, 이 중 최대 거리를 갖는 노드에서 다시 BFS를 수행한다. 이때 각 노드까지의 거리 중 최대 거리가 바로 트리의 지름이다. 즉, 이 문제의 아이디어는 "임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나다." 이다. BFS란? 시작 노드에서 출발해 시작 노드를 기준으..

📚 문제 링크: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 💡 접근법 미로에서 서로 인접한 칸으로만 이동하여 최단 거리를 구해야 하므로 BFS를 이용해야 한다. BFS란? 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다. 해당 문제의 키 포인트는 2가지이다. 1. 미로 문제에서 이동을 조작하고 싶을 때 x, y에 대한 변화량을 나타내는 dx, dy를 선언한다. 문제에서 정의한 움직임은 총 4가지로, 상, 하, 좌, 우이다. ..

📚 문제 링크: 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란? 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다. 💻 코드 1) 전체 코드 i..

📚 문제 링크: https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 💡 접근법 A -> B -> C -> D -> E 와 같이 그래프의 깊이가 5인 경우가 있는지 여부를 확인하는 문제이다. 따라서 DFS를 이용하여 해결한다. 추가로, 재귀에서 탈출할 경우 재탐색이 가능하도록 방문 리스트를 초기화해주어야 하므로 백트래킹 기법도 수행되어야 한다. DFS란? 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 💻 코드 1) 전체 코드 import sys sys..

📚 문제 링크: https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 💡 접근법 자릿수가 한 개인 소수(2, 3, 5, 7)부터 DFS 탐색을 시작한다. 소수에 10을 곱하고 0부터 9까지 더한 값이 소수인지 판별하는 과정을 반복한다. 이때 2의 배수를 더할 경우 무조건 소수가 아니므로 이를 제외하고 수행한다. DFS란? 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다..

📚 문제 링크: https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 💡 접근법 문제에서 말하는 연결 요소란 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 말한다. 따라서 DFS를 수행한 횟수를 계산하면 된다. DFS란? 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 💻 코드 1)..

📚 문제 링크: https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 💡 접근법 계수 정렬 알고리즘을 이용하여 구현하였다. 계수 정렬이란? 각 원소들 간의 비교 없이, 크기를 기준으로 개수를 세어 정렬하는 방법이다. 💻 코드 1) 전체 코드 import sys N = int(sys.stdin.readline()) count = [0] * 10001 for _ in range(N): count[int(sys.stdin.readline())] += 1 for i, c in..

📚 문제 링크: https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 💡 접근법 정렬된 리스트에서 적절한 삽입 위치를 찾아 현재값을 삽입하는 삽입 정렬 알고리즘을 이용하여 구현하였다. 삽입 정렬이란? 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방법이다. 💻 코드 1) 전체 코드 import sys N = int(sys.stdin.readline()) num_list = list(map(int, sys.stdin.readline().split..