1. 트리 1-1. 문제 트리 T는 아래 그림 1과 같은 구조를 가지고 있으며 원은 ‘정점’이라 하고, 정점과 정점을 연결하는 선을 ‘에지’라 한다. 특히 가장 위에 위치한 정점을 ‘루트’라 하는데 오직 하나만 있다. N개의 정점들은 숫자 1부터 N으로 표현하고 루트는 항상 1이다. 두 정점 v와 w를 연결하는 경로는 정점들의 순서리스트 (v0,...

1. 오큰수 1-1. 문제 크기가 N인 수열 A = A1, A2, …, AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(...

1. 잃어버린 괄호 1-1. 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 1-2. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~...

1. 브루트포스란? 브루트포스 알고리즘은 brute(무식한)과 force(힘)의 합성어로 뜻 그대로 무식하게 모든 경우의 수를 다 확인하는 알고리즘이다. 브루트포스는 해가 존재할 것으로 예상되는 모든 영역을 전부 탐색하는 방법이므로 시간 복잡도가 높은 편에 속합니다. 2. 약수 구하기 브루트 포스 알고리즘을 이용해서 약수를 구할 수 있습니다. ...

1. 이진 탐색이란? 이진 탐색은 정렬된 데이터들 중 특정한 데이터를 빠르게 찾아낼 수 있는 알고리즘입니다. 이진 탐색을 하기 위해선 무조건 데이터가 정렬되어 있어야 한다는 조건이 있습니다. 2. 이진 탐색의 원리 오름차순으로 정렬된 데이터는 특정 데이터를 기준으로 그 데이터보다 값이 큰 데이터는 오른쪽에 있고, 작은 데이터는 왼쪽에 있을 것...

1. 그리디 알고리즘이란? 그리디 알고리즘은 최적의 해를 얻기 위해서, 발생하는 각각의 선택지 중, 그 순간에 최적이라고 생각하는 선택지를 선택하는 알고리즘입니다. 2. 그리디 알고리즘의 특징 그리디 알고리즘은 각각의 선택지에서 최적이라고 생각하는 것을 고르지만, 항상 결과가 최적이라고 장담할 수는 없다는 특징이 있습니다. 위 그림을 보면 ...

1. 피보나치 수열이란? 피보나치 수열은 앞에 있는 2개의 항을 더해서 다음 항을 만들어내는 유명한 수열입니다. 피보나치 수열엔 몇가지 규칙이 있는데 그 중 하나는 첫 번째 항과 두 번째 항은 0과 1이어야 한다는 점입니다. 2. 재귀함수를 이용한 피보나치 수열 프로그램에서 피보나치 수열의 항을 구하는 방법은 아주 다양합니다. 그 중에선 재귀...

1. 다익스트라 알고리즘의 특징 다익스트라 알고리즘은 그래프에서 두 노드 사이의 최단 거리를 찾는 알고리즘으로, 노드 사이를 잇는 간선이 가중치를 가집니다. 2. 다익스트라 알고리즘 설명 다익스트라는 모든 노드를 방문해서 그 노드까지 이동하는데 필요한 최소 거리를 계속 갱신하는 방식으로 작동합니다. 3. 최단 거리 출력 코드 #include ...

1. 소수를 판별하는 가장 빠른 방법 소수를 판별하는 가장 빠른 방법은 시간 복잡도가 O(log N) 입니다. 판별하려는 수의 제곱근까지만 반복하여 소수를 반별하는 방법으로, 모든 수의 약수는 제곱근을 기준으로 짝지어진다는 특징을 이용한 알고리즘입니다. 2. 구현 #include <iostream> #include <cmath&g...

1. BFS 탐색이란? BFS 탐색은 그래프의 탐색 방식 중 하나로 넓이 우선 탐색이라고도 불립니다. 그래프는 노드에서 다음 노드로 넘어갈 때 분기가 생기곤 합니다. 깊이 우선 탐색은 생기는 모든 분기들을 큐에 넣고 다 방문한다는 특징이 있습니다. 2. BFS 탐색의 특징 자기 자신을 다시 호출하는 순환 알고리즘의 형태를 가지고 있습니다. ...