Algorithm & Data Structure/이론7 순열(Permutation) (+Java 코드) 1. 순열(Permutation)이란 순열은 n개의 숫자 중에서 r개를 뽑아야 할 때 순서를 고려해서 뽑는 것을 말합니다. 순서에 따라 결과가 달라지기 때문에 같은 1,2,3 데이터를 사용하더라도 은 모두 다른 결과로 취급하게 됩니다. 2. 구현 방법 그렇다면 순열은 코드 상에서 어떻게 구현할 수 있을까요? (1) depth 변수 사용 depth 변수를 통해 깊이를 이동하며 데이터를 뽑는 방식입니다. depth 변수는 result 배열의 index를 의미하며 현재 뽑고자 하는 데이터의 위치라고 생각해 주시면 됩니다! depth가 0일 때에는 result[0]의 숫자를 결정합니다. visited 배열을 통해 아직 사용하지 않은 데이터가 있다면 그 데이터들은 모두 result[0]의 후보가 될 수 있습니다... Algorithm & Data Structure/이론 2024. 4. 22. 조합(Combination) (+Java 코드) 1. 조합(Combination)이란 조합은 n개의 숫자 중에서 r개를 뽑아야 할 때 순서를 고려하지 않고 뽑는 것을 말합니다. 2. 구현 방법 그렇다면 이 조합은 코드 상에서 어떻게 구현할 수 있을까요? 가장 중요한 포인트는 해당 인덱스의 숫자를 선택하냐, 안하냐의 두 가지가 경우가 존재한다는 것입니다! (1) 백트래킹 백트래킹을 사용해서 조합을 구현할 때에는 start 변수를 사용합니다. start 변수는 인덱스를 표현하는데요. arr[start]의 값을 선택하든지, 선택하지 않든지 두 가지 경우가 생기게 됩니다. 선택하면 visited[start] = true 가 되고 선택하지 않으면 visited[start] = false가 되며 선택한 경우에는 start를 +1 증가시켜서 다음 숫자를 고르면 됩.. Algorithm & Data Structure/이론 2024. 4. 22. 다익스트라(dijkstra) 알고리즘 (+Java 코드) 1. 다익스트라란? 다익스트라 알고리즘은 최단 거리를 구하는 알고리즘입니다. (1) 조건 다익스트라 알고리즘을 사용하여 문제를 풀기 위해서는 조건이 있습니다. 음수 가중치가 없어야 한다. 음수 가중치가 있는 그래프에서 최단 거리를 구하기 위해서는 벨만-포드 알고리즘을 사용하면 됩니다! 2. 다익스트라 알고리즘 방식 그렇다면 어떻게 그래프의 최단 거리를 구하는걸까요? 아직 방문하지 않은 정점 중 출발지로부터 가장 가까운 정점을 방문합니다. -> 우선순위 큐 해당 정점을 거쳐 갈 수 있는 정점의 거리가 이전 기록한 값보다 작으면 갱신합니다. (1)번 과정에서 출발지로부터 가장 가까운 정점을 방문해야 하기 때문에 구현할 때에는 우선순위 큐를 사용합니다. 예시를 통해 알아봅시다. (0) 예시 그래프 (1) 출발.. Algorithm & Data Structure/이론 2024. 4. 18. 이분 탐색 (+Java) 1. 이분 탐색이란 이분 탐색아란 오름차순으로 정렬된 수열에서 원하는 값을 찾는 탐색 알고리즘입니다. 여기서 포인트는 정렬된 수열에서 가능하다는 것입니다! 2. 이분 탐색 방법 정렬된 배열에서 값을 찾는다는 가정 하에 아래의 과정을 반복하면 됩니다! 배열의 가운데 요소의 인덱스를 pivot으로 정합니다. arr[pivot]의 값이 찾고자 하는 값과 같다면 탐색을 종료합니다. arr[pivot]의 값이 찾고자 하는 값보다 작다면 pivot ~ right 사이를 탐색합니다. arr[pivot]의 값이 찾고자 하는 값보다 크다면 left ~ pivot 사이를 탐색합니다. 3. 시간 복잡도 이분 탐색의 시간 복잡도는 O(logN)으로 기본적인 선형 탐색보다 훨씬 빠르게 탐색을 할 수 있습니다. 4. 이분 탐색 .. Algorithm & Data Structure/이론 2021. 12. 16. BFS와 DFS (+Java 코드) 1. 그래프란? 그래프란 다대다 연결관계를 표현할 수 있는, 여러 노드와 간선으로 연결된 자료구조를 의미합니다. 그래프는 여러 개의 정점(Vertex) 와 간선(Edge)로 이루어져 있습니다. G=(V, E)로 표기합니다. 정점(Vertex): 그래프의 구성요소 간선(Edge): 두 정점을 연결하는 선 차수(Degree): 정점 하나에 연결된 간선의 수 2. 그래프 탐색 그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 방문하는 것을 의미합니다. 그래프 탐색에는 크게 두 가지 방법이 있습니다. (1) BFS_너비우선탐색 BFS는 Breadth-First-Search의 약자로 너비 우선 탐색을 의미합니다. 너비 우선 탐색은 기준 노드에서 인접한 노드를 먼저 탐색하는 방법인데요. 시작 정점으.. Algorithm & Data Structure/이론 2021. 12. 16. 계수 정렬 (+Java 코드) 1. 카운팅 정렬이란 카운팅 정렬이란 단어 그대로 정렬 알고리즘 중 하나입니다. 그렇다면 앞에 붙은 카운팅은 무엇일까요? 무엇을 카운팅한다는 것일까요? 정답은 데이터의 값이 몇 번 등장했는지를 카운팅하는 것입니다. 대부분의 정렬은 데이터의 값을 직접 비교하여 정렬하는 경우가 많지만 데이터 값의 직접 비교는 시간 복잡도가 O(NlogN)보다 작아질 수 없다는 한계가 존재합니다. 그에 비해 카운팅 정렬은 O(N) 의 시간 복잡도를 자랑하는데요! 어떻게 가능한 것일까요? 2. 동작 방식 아래 그림과 같은 배열을 정렬하고 싶다고 가정하고 동작 방식을 설명하겠습니다. (1) 카운팅 배열 만들기 카운팅 정렬에는 기존 배열 외에도 카운팅 배열이 따로 필요합니다. 즉, 데이터가 얼마나 등장하는지를 배열 인덱스를 통해 .. Algorithm & Data Structure/이론 2021. 8. 9. 에라토스테네스의 체 (+Java 코드) 1. 에라토스테네스의 체란? 에라토스테네스의 체란 소수를 찾는 방법입니다. 해당 방법은 마치 체로 치듯이 수를 걸러낸다고 해서 에라토스테네스의 체 라고 부른다고 합니다. 2. 동작 방식 우리는 체에 집중해서 하나씩 소수가 아닌 수를 걸러낼 것 입니다. 즉, "소수를 찾고 해당 소수의 배수를 모두 지우면 소수만 남는다!" 입니다. 예를 들어, 100 이하의 자연수 중 소수를 모두 찾아보도록 하겠습니다. (1) 1 제거 우선 소수도, 합성수도 아닌 유일한 자연수인 1을 제거합니다. (2) 2를 제외한 2의 배수 제거 다음으로는 2를 제외한 2의 배수를 제거합니다. 무언가의 배수라는 것은 소수가 아니라는 것을 뜻하니까요! (3) 3을 제외한 3의 배수 제거 다음은 3을 제외한 3의 배수를 제거합니다. (4) .. Algorithm & Data Structure/이론 2021. 7. 27. 이전 1 다음
