전체 글124

• 

  최소 신장 트리(MST) : 크루스칼(Kruskal) & 프림(Prim) 최소 신장 트리최소 신장 트리를 구하라라는 문장을 코딩테스트를 하면 많이 볼 수 있다.이 문장의 뜻은 간선에 비용이 있는 그래프에서 간선을 선택하여 모든 정점을 연결하였을 때, 비용의 합이 최소가 되도록 함을 의미한다.- 각 시점에서 최선의 선택을 하는 알고리즘인 그리디(Greedy) 알고리즘 부류입니다. 신장트리- 모든 정점을 연결하는 간선의 집합. 크루스칼(Kruskal) 알고리즘- 크루스칼을 이용하여 최소 신장 트리를 구하는 방법은 다음과 같습니다. 1) 간선을 오름차순으로 정렬한 다음2) 간선 하나씩 선택하며 폐로(사이클)이 생기는지 확인한 뒤,3) 생기지 않으면 간선 리스트에 추가를, 생기면 간선 리스트에 접근 금지를 한다.반복하다보면 모든 정점이 연결될 것입니다. ex) 최소 신장 트리를 만들.. CS 지식/자료구조_알고리즘 2025. 1. 15.

• 

  벨만-포드(Belman-Ford) 알고리즘 & 다익스트라(Dijkstra) 알고리즘 & A* 알고리즘 이렇게 3개의 알고리즘을 하나로 묶은 이유는, 모두 최단 경로를 찾는 알고리즘이기 때문입니다. 최단 경로 문제- 시작점, 끝점이 정해져있음.- 가중 그래프가 주어졌을 때, 최단 경로를 구해야 합니다.  벨만-포드(Belman-Ford) 알고리즘- 음수 비용이 있을 경우에도 사용 가능합니다.- 첫 위치를 0로, 나머지 위치를 ∞로 설정해 놓는다. ex) A에서 G로 갈때, 최단 경로를 구하시오.1) A를 0으로,  나머지를 ∞로 설정합니다.2) 간선(A-B)을 골라 거리를 구합니다. (B : 9, A: 0)2) 또 다른 간선(A-C)을 구해 최단 거리를 구합니다. (C: 2)3) 또 다른 간선(B-C)를 구해 최단 거리를 구합니다. (B : 8)4) 또 다른 간선(B-E), (B-D)을 구해 최단 거리를 .. CS 지식/자료구조_알고리즘 2025. 1. 14.

• 

  그래프(Graph) : 너비우선탐색(BFS) & 깊이우선탐색(DFS) 그래프- 그래프란 노드(Node)와 간선(Edge)로 이루어진 연결 구조입니다.- 노드는 점을 의미하고, 간선은 노드간 연결되어 있는 선을 의미합니다.  가중 그래프- 가중 그래프는 간선에 숫자를 부여해서 무게나 비용을 의미하게 만든 그래프입니다. 방향 그래프- 방향 그래프는 간선에 방향을 부여해서 특정 방향으로만 이동할 수 있는 그래프입니다.- 방향 그래프가 아닌 그래프는 양방향그래프라고 생각하면 됩니다.- 가중 그래프처럼 비용, 무게를 부여할 수 있습니다.  너비 우선 탐색 (Breadth First Search)- 시작점에서부터 목표점까지 갈 수 있는지 탐색하는 알고리즘입니다.- 시작점에서 가까운 곳 부터 방문하는 알고리즘입니다.- 선입선출 구조로 Queue(큐)를 주로 이용합니다. ex) A에서 .. CS 지식/자료구조_알고리즘 2025. 1. 13.

• 

  이진 탐색 (Binary Search) 탐색의 방법은 크게 두가지가 있는데, 선형 탐색과 이진 탐색이 있습니다.그 중 이진 탐색 방법에 대해 작성을 해봤습니다.  이진 탐색(Binary Search)- 정렬된 상태에서 사용할 수 있습니다.배열의 정 중앙값을 선택해 그 값보다 작으면 왼쪽 배열, 크면 오른쪽 배열에서 재귀를 돌려 결국 원하는 값을 탐색할 때 사용하는 방법입니다. ex) int[] arr = {1,2,3,4,5,6,7,8,9} 에서 이진 탐색으로 숫자 6을 찾아라.1) 중앙값인 5보다 원하는 값이 크기 때문에 우측 배열을 재귀로 돌아야 합니다. {6,7,8,9}2) 중앙값인 7보다 원하는 값이 작으니 좌측 배열을 재귀로 돌아야 합니다. {6}3) 중앙값인 6과 원하는 값인 6이 일치하기 때문에 종료된다.3번째 만에 원하는 값을 탐.. CS 지식/자료구조_알고리즘 2025. 1. 13.

• 

  BJ S2 1260 DFS와 BFS - Java [문제링크]https://www.acmicpc.net/problem/1260 [문제]그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.[입력]첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.[출력]첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 .. 알고리즘/DFS_BFS 2025. 1. 12.

• 

  힙 정렬(Heap Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) 이번에는 정렬 중에서도 시간 복잡도가 조금 더 빠른 정렬들을 가지고 왔습니다. 힙 정렬, 병합 정렬, 퀵 정렬이렇게 총 3가지 정렬을 설명 드리겠습니다. 힙 정렬(Heap Sort)- 아래의 링크에 있는 힙에 대해 공부하고 오면 이해하기 매우 편하십니다.https://naknak.tistory.com/123 힙(Heap)과 이진탐색트리(Binary Search Tree)힙(Heap)- 트리구조 중 하나로 우선순위 큐를 구현할 때 사용됩니다. (다익스트라에서도 사용됨.)- 우선순위 큐의 특징 : 데이터를 자유롭게 추가 가능, 꺼낼 때는 가장 작은 데이터를 꺼냅니다. -naknak.tistory.com  - 힙은 트리 형태의 구조로, 우선순위 큐를 구현하는데 주로 사용됩니다.- 보통의 힙은 꺼낼 때 가장 작.. CS 지식/자료구조_알고리즘 2025. 1. 12.

• 

  버블 정렬(Bubble Sort) vs 선택정렬(Selection Sort) vs 삽입정렬(Insertion Sort) 버블 정렬과 선택정렬, 그리고 삽입정렬은 정렬 중 가장 기초적인 정렬들 입니다.우선 버블 정렬부터 살펴보겠습니다. 버블 정렬(Bubble Sort)- 오른쪽에서 정렬을 시작하여 왼쪽으로 가며, 본인의 값이 왼쪽의 값보다 작을 경우 위치를 변경해주는 정렬입니다.- 한 사이클이 지나면 맨 왼쪽의 값은 항상 가장 작은 값이 됩니다. 따라서 다음 사이클은 맨 좌측 값 하나를 제외하고 돌립니다. ex) int[] arr = { 3, 2, 1 }이고, 버블 정렬을 통해 정렬하라고 하면,1) 2와 1을 비교합니다. 2가 더 크므로 둘의 위치를 교체해줍니다. => {3, 1, 2}2) 3과 1을 비교합니다. 3이 더 크므로 둘의 위치를 교체해줍니다. => {1, 3, 2}3) 3과 2를 비교합니다. 3이 더 크므로 둘.. CS 지식/자료구조_알고리즘 2025. 1. 11.

• 

  힙(Heap)과 이진탐색트리(Binary Search Tree) 힙(Heap)- 트리구조 중 하나로 우선순위 큐를 구현할 때 사용됩니다. (다익스트라에서도 사용됨.)- 우선순위 큐의 특징 : 데이터를 자유롭게 추가 가능, 꺼낼 때는 가장 작은 데이터를 꺼냅니다. - 힙은 노드들로 구성되어 있습니다.각각의 노드들은 부모와 자식으로 이루어져 있고, 부모는 최대 2개의 자식 노드를 가질 수 있습니다.- 부모 노드의 데이터가 자식 노드의 데이터보다 항상 작아야합니다. ex) 새로운 수를 힙에 추가하는 예시.1) 새로운 숫자를 힙의 가장 끝에 추가합니다.2) 만약 부모 노드가 존재한다면, 부모 노드와 데이터를 비교 후 숫자가 더 작다면 그 둘의 위치를 바꿔줍니다.3) 계속 그렇게 해서, 더 이상 부모보다 작지 않을 경우, 정렬은 종료됩니다. ex) 숫자를 하나 꺼낼때의 예시... CS 지식/자료구조_알고리즘 2025. 1. 9.

• 

  스택(Stack)과 큐(Queue) 스택(Stack) - 스택은 데이터를 한 열로 저장합니다. 하지만 후입선출(Last In First Out) 구조로 나중에 들어간 것이 먼저 나오는 구조입니다.- 링 던지기 게임이 스택의 예시입니다. - 데이터의 추가는 push라고 불리며, 스택 내부에 데이터가 쌓입니다.- 데이터의 삭제는 pop이라 불리며, 스택에 가장 마지막에 들어갔던 데이터가 나오게 됩니다. ex) A만 들어가 있는 스택이 있다. 스택에 B, C를 넣어보자.1) 스택에 B를 push한다. (A-B)2) 스택에 C를 push한다. (A-B-C)3) 스택에서 pop을 한다. (A-B)4) 스택에서 pop을 한다. (A) 예시에서 처럼 가장 나중에 들어간 데이터가 가장 먼저 나오게 되는 구조가 바로 스택이다.스택이 가장 많이 활용되는 부.. CS 지식/자료구조_알고리즘 2025. 1. 8.

• 

  List(리스트)와 Array(배열) List(리스트)- 리스트는 데이터를 일직선으로 줄줄이 정렬한 데이터 구조입니다.장점 : 데이터의 추가, 삭제 쉬움단점 : 데이터 조회 느림 - 데이터들은 각각 포인터를 가지고, 이 포인터는 각각 데이터의 다음 데이터의 메모리 주소를 가리킵니다. - 리스트는 포인터를 이용하므로 메모리상에서 연결된 위치에 있을 필요가 없습니다. 따라서 분산되어 배치됩니다. - 데이터 추가 방법A와 B 데이터 사이에 C라는 데이터를 추가할 때, A의 포인터가 C의 메모리 주소를 가리키게 하고,C의 포인터가 B의 메모리 주소를 가리키게 하면 끝이다. - 데이터 삭제 방법A와 B와 C가 연결되어 있을 때, B를 제거하고자 한다.A의 포인터를 C의 메모리주소를 가리키면 해결된다. 따라서 List에서의 시간복잡도는 다음과 같다.데.. CS 지식/자료구조_알고리즘 2025. 1. 7.

• BJ G4 20040 사이클게임 - Java [문제링크]https://www.acmicpc.net/problem/20040[문제]사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다. C에 속한 임의의 선분의 한.. 알고리즘/유니온-파인드 2024. 10. 13.

• BJ S1 15651 N과M(3) - Java [문제링크]https://www.acmicpc.net/problem/15651[문제]자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.[입력]첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)[출력]한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.[예제 입력 1]3 1[예제 출력 1]123[예제 입력 2]4 2[예제 출력 2]1 11 21 31 42 12 22 32 43 13 23 33 44 14 24 34 4[설.. 알고리즘/백트래킹 2024. 10. 9.