Algorithms
-
거품 정렬 (Bubble Sort)Algorithms/정렬 2022. 8. 23. 09:41
정의 거품 정렬은 1번째와 2번째, 2번째와 3번째, 3번째와 4번째, ... 와 같이 인접한 두 원소를 비교하여 정렬한다. 인접한 두 원소끼리 반복적으로 비교하는 모습이 마치 '거품'과 같다고 하여 거품 정렬이라고 이름이 붙여졌다. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로, 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외할 수 있다. 마찬가지로 2회전을 수행하고 나면 끝에서 두번째 자료까지는 정렬에서 제외된다. 설명 [5, 4, 3, 2, 1] 위 배열을 오름차순 정렬해보자. 1번째와 2번째를 비교한 후, 2번째 원소가 더 작을 경우 1번째 원소와 교체해 준다. [4, 5, 3, 2, 1] 이번에는 2번째와 3번째를 비교하여 교체해주자. [4, 3, 5, 2, 1] 같은 방식으로 마지..
-
삽입 정렬 (Insertion Sort)Algorithms/정렬 2022. 8. 22. 09:20
정의 2번째 원소부터 시작해서 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 값을 삽입하는 정렬 알고리즘이다. 선택 정렬 이 원소가 들어갈 자리를 정해두고 해당 자리에 들어올 원소를 찾는 정렬인 것과는 반대로, 삽입 정렬은 원소가 들어갈 자리를 정해두지 않고, 값을 먼저 결정한 다음 해당 값이 들어갈 자리를 앞에서 부터 찾는 알고리즘이다. 즉, 삽입 정렬에서 '삽입'은 값을 특정 자리에 삽입한다는 의미이고, 값이 들어갈 자리를 찾는 알고리즘이라고 생각하면 된다. 설명 [5, 4, 3, 2, 1] 위 배열을 오름차순 정렬해보자. 2번째 원소인 4부터 시작하여 앞 원소들과 대소 비교를 진행한다. 5는 4보다 큰 값이므로 2번째 자리의 원소를 5로 바꿔준다. [5, 5..
-
선택 정렬 (Selection Sort)Algorithms/정렬 2022. 8. 21. 16:14
정의 자리를 정해두고 해당 자리에 들어올 값을 선택하는 알고리즘이다. 선택 정렬의 '선택'은 들어올 값을 선택하는 것이라고 생각하자. 설명 [5, 4, 3, 2, 1] 위 배열을 오름차순 정렬해보자. 자리를 순회하며 해당 자리에 올 값을 찾아 넣는다. 값을 찾는 방법은 해당 자리에 위치해있던 값과 나머지 모든 값을 비교한다. 1. 첫번째 자리에 올 값 선택 오름차순 정렬이니, 첫번째 자리에는 1이 와야한다. 5를 제외한 나머지 모든 수 [4, 3, 2, 1] 을 순회하여 가장 작은 값인 1을 찾아 5와 바꾼다. [1, 4, 3, 2, 5] 2. 두번째 자리에 올 값 선택 두번째 자리에는 두번째로 큰 값인 2가 와야한다. 1과 4를 제외한 나머지 모든 수 [3, 2, 5] 을 순회하여 가장 작은 값이 2를..
-
백준 9663. N-Queen 문제Algorithms/ACM_ICPC 2022. 8. 21. 15:18
알고리즘 모든 경우를 전부 시도해 보아야 한다. 단, Queen을 놓을 수 없는 위치라고 판단되면 중지하고 다음 경우의 수를 시도해볼 수 있다. -> 백트래킹 접근방법 모든 경우의 수를 전부 확인해야 하는 문제이다 2차원 배열이 아닌 1차원 배열로 문제를 풀어내 구현의 난이도를 낮출 수 있다. 4x4 N-Queen 보드에 (0, 0), (1, 3), (2, 1), (3, 2) 위치에 Queen 을 놓는다고 할 때, 1차원 배열로 다음과 같이 표현 가능하다. 1차원 배열 : [0, 3, 1, 2] => 행은 index, 열은 값으로 표현 코드 import java.io.*; import java.util.*; public class Main { private static int N; private stat..
-
백준 10845번. 큐Algorithms/ACM_ICPC 2022. 8. 19. 14:42
문제 설명 자료구조 큐를 구현하는 문제이다. 접근 방법 - int[] 로 데이터를 저장하도록 구현하였다. - lastIndex 변수를 이용하여 값이 저장된 마지막 index를 추척하도록 구현하였다. 코드 import java.io.*; import java.util.*; public class Main10845 { private static int size; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); size = Integer.parseInt(br.readLine()); Queue queue = new Queue(..
-
깊이우선탐색(DFS, Depth First Search)Algorithms/그래프 2022. 4. 21. 10:05
개요 깊이우선탐색은 대표적인 그래프 탐색 알고리즘이다. 위와 같은 그래프를 탐색하고자 한다. 간선으로 연결된 노드를 더 이상 간선이 연결되지 않을 때 까지 탐색하는 방법을 깊이 우선 탐색이라 한다. 간선으로 연결된 모든 노드를 우선으로 탐색하고, 더 이상 해당 노드에 연결된 간선이 없을 경우 하위 노드에서 같은 방식으로 연결된 모든 노드를 탐색하는 것을 너비 우선 탐색이라고 한다. 너비 우선 탐색은 다음 글에서 살펴보기로 하고, 이번 글에서는 DFS 에 대해 자세히 알아보자. DFS (Depth First Search) 1.1 설명 1번 노드에서 시작한다. 연결된 간선이 있으니, 2번 노드부터 탐색한다. 2번 노드로 이동했다. 간선으로 연결된 3번 노드로 이동한다. 3번 노드로 이동했다. 간선으로 연결된..
-
백준 알고리즘, 2225 문제Algorithms/ACM_ICPC 2018. 8. 14. 15:53
풀이 0 ~ 20 까지 3 개를 더한다고 생각해보자. 1. 0 + ( 0 ~ 20 까지 2개를 더하는 방법의 수 ) 2. 1 + ( 0 ~ 19 까지 2개를 더하는 방법의 수 ) 3. 2 + ( 0 ~ 18 까지 2개를 더하는 방법의 수 ) ... 위 방법을 고안해냈다. DP 배열을 어떻게 표현할지 고민했다. DP[N][K] = 0 ~ N 까지 K 개를 더하는 방법의 수 이제 for 문으로 값을 만들어나가야 하는데, 위 방식에서 분홍색을 선택할 경우 3 중 for 문이 필요할 것이고 연두색 방법을 선택할 경우 2 중 for 문이면 해결이 된다. 코드 @github 에서 확인하기 /** * @site: https://www.acmicpc.net/problem/2225 * @github: https://gi..
-
백준 알고리즘, 9461 문제Algorithms/ACM_ICPC 2018. 8. 14. 13:35
풀이 가장 큰 변의 길이를 추가한다고 했으므로 P[N - 1 ] 은 반드시 들어간다. 추가로 더해지는 값은 P[9] 부터 규칙이 형성된다. P[9] = P[4] + P[8] P[10] = P[5] + P[9] P[11] = P[6] + P[10] ... 따라서 점화식은 P[N] = P[N - 5] + P[N - 1] 코드 @github 에서 보기 /** * @site: https://www.acmicpc.net/problem/9461 * @github: https://github.com/7772 * @auth: Landon Park * @date: 2018. 08. 14 */#include using namespace std; int main() { long P[101]; int i, T, N; cin ..