Algorithm/Baekjoon

🗂️ 문제 링크: https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 💡 접근법 그리디 알고리즘을 사용한다. 최소값을 구하기 위해서는 작은 수에서 큰 수를 빼야 한다. 따라서 덧셈으로 연속된 부분에 괄호를 쳐서 이를 계산한 후 빼는 방식으로 문제를 해결하면 된다. 이때 예외처리로 주의해야 할 부분이 있다. -로 입력값을 split하고 문제에서 주어진 테케를 시도할 경우 A = ['100', '40+50+74', '30+29', '45+43+1..

🗂️ 문제 링크: https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 💡 접근법 그리디 알고리즘을 이용하여 문제에 접근한다. 즉 현재 시점에서 최선의 선택을 하고 이 선택이 전체 문제를 해결할 수 있는지 확인한다. 문제에서 제시한 대로 최소 동전 개수를 구하기 위해서는 가장 가격이 큰 동전부터 차례대로 순회하면 된다. 😎 내 코드 import sys N, K = map(int, sys..

🗂️ 문제 링크: https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 😎 내 풀이 import sys N, M = map(int, sys.stdin.readline().split()) arr = [sys.stdin.readline().rstrip() for _ in range(N)] word_dict = {} for i in arr: # 단어의 길이가 M 이상인 단어만 단어장에 저장 if len(i) < M: continue if ..

📚 문제 링크: 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란? 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다..