목록알고리즘 (7)

[Alex] 데이터 장인의 블로그

[알고리즘] BFS - 문제풀이 (백준 - 1261번)

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 저번 BFS 문제에 이어서 대표적인 BFS 문제 풀이를 진행해보겠다. 문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이..
알고리즘 2022. 7. 10. 17:35
[알고리즘] BFS (너비 우선 탐색) / DFS (깊이 우선 탐색)

개념 이해 그래프 탐색 : 어떤것들이 연속해서 이어질 때, 모두 확인하는 방법. Graph : Vertex(어떤 것) + Edge(이어지는 것) [그래프 탐색 종류] BFS : 너비 우선 탐색 (Breadth-first search) 기준 노드(Vertex)에서 자식 노드(Vertex) 부터 탐색하는 방법. 즉, 주변에 분포해있는 노드부터 탐색하는 방법 (깊게 No, 넓게 Yes) 위의 그래프의 경우 탐색 차례 : 0 - 1 - 2 - 3 - 4 - 5 - 6 BFS = Queue 자료형과 맞음 DFS : 깊이 우선 탐색 (Depth-first search) 기준 노드(Vertex)에서 자식 노드(Vertex) -> 자식노드까지 탐색하는 방법. 즉, 자식의 자식까지(끝노드) 모두 탐색하는 방법 (깊게 Y..
알고리즘 2022. 7. 2. 18:36
[알고리즘] 5) 병합 정렬 알고리즘

병합 정렬 알고리즘도 대표적인 '분할 정복' 방법을 채택한 알고리즘. 퀵정렬과 동일하게 O(NlogN)의 시간복잡도를 가진다. 주어진 원소를 원소 하나만 남을 때까지 쪼갠 후에 다시 크기 순으로 재배열하면서 원래 크기의 배열로 합친다. 아래 리스트가 있다고 가정해보자. [6, 5, 3, 1, 8, 7, 2, 4] 각 원소마다 하나의 리스트가 생기도록 쪼갠 후에 역으로 두개씩 합치는 과정을 시작한다. [6] [5] [3] [1] [8] [7] [2] [4] 합칠때는 작은 숫자가 앞에 오도록 위치, 이후 각각 2개의 배열을 하나의 배열로 합치는 작업을 수행한다. [5, 6] [1, 3] [7, 8] [2, 4] 두개의 인자중 작은 인자부터 하나씩 비교하기 시작하면 작은 값부터 차례대로 배열을 정리할 수 있다..
알고리즘 2022. 6. 26. 15:15
[알고리즘] 4) 퀵 정렬 알고리즘

출처 [Heee's Development Blog] 퀵 정렬은 많은 프로그래밍이 기본으로 채택하는 정렬 알고리즘이다. (프로그래밍 언어 차원에서의 기본적으로 지원되는 정렬함수.) 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법. 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 과정 설명 [참고] 예를 들어 다음과 같은 데이터가 있다고 가정한다. [6, 5, 1, 4, 7, 2, 3] 이때 4라는 피벗값(기준)을 설정하여 피벗 값 기준으로 왼쪽으로는 (피벗보다) 작은 값, 오른쪽으로는 (피벗보다) 큰 값을 위..
알고리즘 2022. 6. 26. 15:13
[알고리즘] 3) 삽입 정렬 알고리즘

삽입 정렬 알고리즘 삽입 정렬은 리스트의 범위를 2 -> 3 -> 4개 씩 늘려나가면서 새롭게 추가된 인자를 기존 값들과 비교하는 알고리즘. 설명 1. 아래 인자들이 [2,1] 부터 차례대로 5, 4, 3 입력 받는다고 가정한다. [2, 1, 5, 4, 3] 2. 처음에 두 인자를 비교한 후에 정렬을 수행한다. [2, 1]: 2 > 1 => swap ^ ^ [1, 2] * * 3. 그 다음 기존의 정렬 범위에 한칸을 확장하여 세번째 값을 추가시키고 비교 진행한다. 5와 2를 비교하여 움직임이 없었다는 것은 1과의 비교도 진행할 필요가 없다는 것을 의미하므로 종료하고 다음 인자를 입력 받는다. [1, 2, 5]: 2 OK ^ ^ [1, 2, 5] * * * 4. 4를 입력받은 후에 스와핑을 진..
알고리즘 2022. 6. 26. 15:09
[알고리즘] 2) 버블 정렬 알고리즘

[출처 DaleSeo] 버블 정렬 알고리즘 버블 정렬은 선택 정렬과 유사한 정렬 방식이다. 선택 정렬은 '최소값'을 확정하고 난 후에 다음 비교로 넘어간 것에 반해 버블 정렬은 바로 직전, 직후 값들을 비교해 나가는 방식을 말한다. 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보낸다. 선택 정렬과 마찬가지로 구현은 쉽지만, 시간복잡도로 봤을 때는 효율적이지 않은 정렬 방식이다. 설명 1. 먼저 4와 3을 비교, 3이 더 작음으로 서로 스와핑한다. [4, 3, 5, 1, 2] ^ ^ 4 > 3 => Swap [3, 4, 5, 1, 2] 2. 이후 4와 5를 비교, 바꿀 필요가 없음을 확인. [3, 4, 5, 1, 2] ^ ^ 4 No Swap 3. 5와 1을 비교, 1이 더 작음으로 서로 스..
알고리즘 2022. 6. 26. 15:06
[알고리즘] 1) 선택 정렬 알고리즘

항상 알고리즘을 공부해야지 맘잡고 책과 영상을 시작하게 되면 맞이하는 과목(?)이 있다. 바로 정렬이다. 이번 기회에 블로그에 정리하면서 복습하려고 한다. 주로 Google 선생과 Youtube 선생의 소스에서 자료를 얻지만 대표적으로는 [동빈나] 선생님, https://www.daleseo.com/ 블로그 자료를 주로 참고하였다는 것을 미리 밝힌다. '정렬'의 개념은 우리가 흔히 말하는 '오름차순' 이나 '내림차순'으로 데이터를 정리하는 방법들을 정의한다. 선택 정렬 알고리즘 배열 내 여러 인자 값이나 데이터가 있다고 가정해보자. 첫번째 값을 '기준'으로 두고 두번째, 세번째 값과 비교를 진행한다. 이때 뒤(N번째)의 값이 '기준'되는 값보다 작다면, 기준값과 자리를 바꾼다. 이 개념을 도입하여 코드를..
알고리즘 2022. 6. 26. 15:01
Prev 1 Next