Computer Algorithms14 [바킹독 실전 알고리즘 0x0B] 재귀 알고리즘 설명 재귀: 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 다음과 같이 간단한 재귀 함수 코드를 생각해볼 수 있다. void func(int n){ if(n == 0) return; cout 2023. 2. 12. [바킹독 실전 알고리즘 0x0C] 백트래킹 알고리즘 설명 백트래킹: 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 백트래킹은 상당한 구현력을 필요로 하고, 실수하기도 쉽다. 따라서 많은 시간을 할애해 재귀의 개념을 익히고, 연습을 해야한다. 처음엔 어렵게 느껴지겠지만, 생각보다 응용의 폭이 넓지 않아 BFS와 비슷하게 기본적인 코드 뼈대를 익혀두면 훨씬 더 수월하게 풀이할 수 있다. 연습문제1 - N과 M BOJ 15649번) 백트래킹의 기본 코드는 대략적으로 익혀두는 것이 좋다. #include using namespace std; //전역 변수 int n, m; //입력 받는 값들 int arr[10]; //수열을 담을 배열 bool isused[10]; //특정 수가 쓰였는지를 나타내는 배열(상태를 저장하는 배열) //.. 2023. 2. 10. [바킹독 실전 알고리즘 0x0A] DFS 알고리즘 설명 DFS(Depth First Search): 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 예시 큐가 스택으로 바뀐 것을 제외하면 BFS와 거의 비슷하다. pseudo code) 1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남긴다. 2. 스택에서 원소를 꺼내 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행한다. 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입한다. 4. 스택이 빌 때까지 2번을 반복한다. 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. C++ code) #include using namespace std; #define X first #d.. 2023. 2. 5. [바킹독 실전 알고리즘 0x09] BFS 알고리즘 소개 BFS(Breath First Search): 너비 우선 탐색 예시 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 4. 큐가 빌 때까지 2번을 반복 처음 방문 했을 때만 방문 표시를 남기기 때문에 모든 칸이 큐에 1번씩 들어간다. 따라서 시간복잡도는 칸이 N개일 때 O(N)이다. 같은 원리로 행이 R개, 열이 C개인 2차원 평면을 BFS 탐색하면 시간복잡도는 O(RC)가 될 것이다. 이제 BFS 구현에 필요한 pair STL에 대해 알아보고자 한다. pair를 이용하면 두 자료형을 묶어.. 2023. 2. 3. [바킹독 실전 알고리즘 0x08] 스택의 활용(수식의 괄호 쌍) 이번 게시글에서는 스택을 사용해 수식의 괄호 쌍이 올바르게 짝지어져 있는지 판별하는 문제를 해결하고자 한다. 문제 해결을 위한 관찰 idea) 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각하자. 그리고 다음 그림을 보고 괄호 문제의 풀이법을 떠올려보자. 여는 괄호를 만나면 스택에 삽입하고, 닫는 괄호를 만나면 가장 최근에 들어온 여는 괄호를 삭제한다. 괄호가 담긴 문자열을 모두 읽었을 때, 스택에 남아있는 괄호가 없다면 모든 괄호가 짝을 이뤘다고 판단할 수 있다. 올바르지 않은 괄호 쌍을 가지는 경우는 다음과 같다: 1. 여는 괄호와 닫는 괄호의 짝이 맞지 않는 경우 2. 괄호 쌍의 수가 맞지 않는 경우 3. 닫는.. 2023. 2. 2. [바킹독 실전 알고리즘 0x07] 덱 정의와 성질 덱은 양 쪽 끝에서 삽입과 삭제가 모두 가능하다. 자료구조에서의 덱은 deque(double ended queue)이다. (deck아님) 원소의 삽입과 삭제를 O(1)의 시간복잡도를 가지고 구현할 수 있다. 가장 앞과 가장 뒤의 원소를 확인하는 데 O(1)의 시간복잡도가 소요된다. 가장 앞과 가장 뒤가 아닌 원소들의 확인/변경은 원칙적으로 불가능하다. 하지만 독특하게도 스택, 큐와 달리 STL deque에서는 인덱스로 원소에 접근할 수 있다. 기능과 구현 스택, 큐와 동일하게 배열과 연결리스트를 가지고 구현할 수 있다. 하지만 배열로 구현하는 것이 더 쉽기 때문에 이번 게시글에서는 배열로 구현하는 방법을 소개한다. const int MAX = 1000000; int data[2*MAX+1];.. 2023. 2. 1. [C++] Visual Studio에 <bits/stdc++.h> 헤더파일 추가하기 알고리즘 문제를 풀 때, 필요한 헤더 파일들을 매번 include 해주는 과정이 귀찮게 느껴질 수 있다. 자주 쓰이는 헤더 파일들을 담은 stdc++.h 파일을 다운로드 받은 후, 코드 컴파일러의 include 파일에 자동으로 포함되도록 하면 이 번거로움을 해결할 수 있다. stdc++.h 파일은 gcc 컴파일러에는 내장되어 있다. 따라서 대표적으로 gcc 컴파일러를 사용하는 Visual Studio Code의 경우, 이 파일을 따로 다운로드 받을 필요가 없다. 하지만 많은 사람들이 C++ 코딩을 할 때 사용하는 Visual Studio의 경우 msvc 컴파일러를 사용하기 때문에 stdc++.h 파일을 직접 다운로드 받아 include 폴더에 넣어야 한다. 다음은 stdc++.h 파일이다. stdc++... 2023. 2. 1. [바킹독 실전 알고리즘 0x06] 큐 정의와 성질 큐는 한쪽 끝에서 원소를 넣고, 다른쪽 끝에서 원소를 뺄 수 있는 자료구조이다.(FIFO) 큐에서 원소가 추가되는 곳을 rear, 즉 뒷쪽이라고 하고, 원소가 제거되는 곳을 front라고 한다. 원소의 추가나 제거를 할 때 O(1)의 시간복잡도가 필요하다. 가장 앞이나 가장 뒤 원소를 확인하려면 O(1)의 시간복잡도가 필요하다. 가장 앞이나 가장 뒤 원소를 제외한 원소들의 확인/변경은 원칙적으로 불가능하다. (앞 게시글의 스택과 비슷한 맥락) 기능과 구현 큐도 스택과 마찬가지로 배열 혹은 연결리스트를 사용해 구현이 가능하다. 배열로 구현하는 방법이 더 쉬워서 이번 게시글에서는 배열로 구현하는 것만 소개하려고 한다. const int MAX = 1000000; int data[MAX]; //원.. 2023. 2. 1. [바킹독 실전 알고리즘 0x05] 스택 정의와 성질 LIFO(선입선출) 구조이다. 특정 위치에서만 원소의 추가나 제거가 이루어진다. 이 성질 덕분에 원소의 추가나 제거는 O(1)이다. 제일 상단의 원소를 확인하는 시간복잡도는 O(1)이다. 제일 상단이 아닌 나머지 원소들의 확인이나 변경은 원칙적으로 불가능하다. 원칙적으로 불가능해서 배열의 성질을 사용해 나머지 원소들의 확인이 가능하도록 구현할 수는 있지만, 스택의 응용 사례에는 제일 상단의 원소만을 다룬다. 기능과 구현 스택은 배열 혹은 연결 리스트를 사용해 구현할 수 있다. 그리고 둘 중 배열을 이용하는 구현 방법이 더 쉽다. 배열을 사용해 스택을 구현하는 방법은 생각보다 간단한데, 원소들을 모두 담을 큰 배열 하나와 인덱스를 저장할 변수 하나만을 필요로 한다. const int MAX =.. 2023. 1. 31. 이전 1 2 다음
