코딩 맛집

* 탐색 그래프의 모든 노드들을 방문하는 일 ​ ​ * 탐색의 두 가지 방법 1. BFS : Breadth First Search, 너비 우선 탐색 2. DFS : Depth First Search, 깊이 우선 탐색 ​ ​ * BFS 동심원 형태로 인접한 노드들을 차례대로 탐색 하는 방법 입니다. 너비를 중심으로 탐색 하는 방법 입니다. 1. L0 = { S }, S는 출발 노드 2. L1 = L0 의 모든 이웃 노드들 3. L2 = L1의 이웃들 중 L0에 속하지 않는 노드들 ............. 4. Li = Li-1의 이웃들 중 Li-2에 속하지 않는 노드들 ​ ​ * 큐를 이용한 BFS 구현 1. check the start node; 2. insert the start node into th..

* 탐색 그래프의 모든 노드들을 방문하는 일 ​ * 대표적인 두 가지 방법 1. BFS : Breadth First Search, 너비 우선 탐색 2. DFS : Depth First Search, 깊이 우선 탐색 ​ * DFS 맹목적 탐색 방법의 하나로 출발 노드로 부터 다음 레벨의 자식 노드를 탐색하고 또 그 다음 자식 노드를 탐색 하는 방법 입니다. 깊이를 우선으로 탐색 하는 방법 입니다. 1. 출발 노드에서 시작 합니다. 2. 현재 노드를 visited로 mark 하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 갑니다. 3. 2번을 계속 반복 합니다. ​ ​ * DFS 동작 순서 위와 같은 그래프가 있을때 DFS로 탐색 한다면 아래 순서대로 노드를 방문 합니다. ① 출발노드1을..

* 특징 - 최악의 경우 시간 복잡도 O(nlogn) - Sorts in place - 추가 배열 불필요 - 이진 힙 자료 구조를 사용 ​ * 힙 1. Complete binary tree 이여야 한다. - full binary tree : 모든 레벨에 노드들이 꽉 차있는 형태 - complete binary tree : 마지막 레벨을 제외하면 완전히 꽉 차있고, 마지막 레벨에는 가장 오른쪽 부터 연속된 몇개의 노드가 비어있을 수 있음 ​ ​ 2. heap property를 만족 해야 한다. - max heap property : 부모는 자식보다 크거나 같다 - min heap property : 부모는 자식보다 작거나 같다 * Heap의 표현 - 힙은 일차원 배열로 표현 가능 : A[1 . . n] -..

비트 마스크(Bit Mask) 기법은 말 그대로 비트(Bit)를 마스킹하는 기술 입니다. 비트를 마스킹 한다는 것은 &(AND 연산자), | (OR 연산자) 등의 비트 연산을 활용하여 정수의 이진 비트를 처리하는 작업이라고 이해하 실 수 있습니다. 비트 마스크 기법은 항상 사용할 수 있는 것은 아니지만 특정한 경우에 사용하면 매우 효율적 일 수 있습니다. 비트 마스크의 대표적인 장점을 소개하면 다음과 같습니다. ​ 1. 메모리를 적게 사용할 수 있습니다. 2. 프로그램이 더욱 빠르게 동작 합니다. 3. 소스코드가 직관적으로 변경 됩니다. ​ 일반적으로 정수 7이 있을 때 이것을 비트 형태로 표현하면 다음과 같습니다. ​ 7 : 0000000 0000000 0000000 00000111 (2진수 비트, 3..

오늘은 문자열 찾기 알고리즘인 KMP(Knuth-Morris-Pratt) 알고리즘에 대해서 공부 하겠습니다. ​ ​ 1. 문자열 매칭(String Matching) 우리들이 흔히들 사용하는 브라우저에서 Ctrl + F(찾기) 기능에서 사용 하는 알고리즘 입니다. KMP 알고리즘은 "전체 문자열" 과 우리가 찾고자 하는 "패턴 문자열" 이 존재 할때 패턴 문자열을 효율적으로 찾을수 있는 알고리즘 입니다. ​ ​ 2. KMP 알고리즘 아이디어 먼저 KMP 알고리즘의 핵심 아이디어는 다음과 같은 상황에서 나왔습니다. 위와 같이 전체 문자열 "ababaca" 에서 패턴 문자열 "abac" 를 찾으려는 상황에서 패턴 문자열이 2칸을 건너뛰어 찾고자 하는 패턴 인지 검사 할수 있습니다. 그 이유는 1) 패턴 문자열..

문제 N * N 체스판에서 퀸을 겹치지 않고 N개 넣을 수 있는 좌표를 구하라. 이 문제는 대표적인 BackTracking 문제 이다. 체스말을 첫 행부터 한행 씩 두어 보다가 막혀서 더 이상 진행을 할 수 없을 때 다시 돌아와 체스말을 둔다는 의미에서 BackTracking 문제 이다. 이와 같은 BackTracking 문제는 깊이 우선 탐색으로 문제를 해결 할 수 있다. ​ 먼저 sudo 코드를 작성 해보자. // sudo 코드 return-type queens( level ) { if non-promising (infeasible 한 경우) report failure and return; else if success report answer and return; else visit children ..

(사과, 딸기, 포도) 중 에서 선택 할수 있는 총 경우의 수는 어떻게 될까요? 아래 그림과 같이 선택 할수 있습니다. 선택하는 경우를 1, 선택 안하는 경우를 0 으로 표현 할수 있습니다. 이를 이용해서, 경우의수 문제(조합, Combination, DFS)를 비트 마스크를 이용해서 해결 할수 있을거 같습니다. 1. 비트 마스크 비트 마스크는 이진수로 표현하여, 비트 연산자(&(AND연산자), |(OR연산자), ^(XOR연산자))를 이용하여 각각의 이진수의 값을 마스킹(가리다) 하여, 원하는 연산을 할수 있는 것 입니다. 4(십진수) => {1, 0, 0}(이진수) 2(십진수) => {0, 1, 0}(이진수) 1(십진수) => {0, 0, 1}(이진수) 위와 같이 십진수를 이진수로 표현 할수 있습니다...

다이나믹 프로그래밍 1 '다이나믹 프로그래밍' 한글로 '동적 계획법' 이라는 알고리즘은 '리차드 벨만'이 만든 알고리즘 입니다. 리차드 벨만은 최단 경로를 찾는 '벨만 포드 알고리즘'도 만들었습니다. ​ ​ 1. 다이나 coding-food-court.tistory.com 위의 다이나믹 프로그래밍의 개념을 먼저 공부하고 아래의 문제를 다이나믹 프로그래밍을 이용해서 해결해 보겠습니다. 행렬 경로 문제 1. 정수들이 저장된 N * N 행렬이 있습니다. 2. 이 행렬의 좌상단 부터 우하단 까지 이동 합니다. 3. 오른쪽이나 아래쪽 방향으로만 이동 할 수 있습니다. 4. 어느 길로 가야 정수들의 합이 최소가 되도록 할 수 있을까요? 1. (i, j)에 도달하기 위해서는 (i, j-1) 혹은 (i-1, j)를 거..

'다이나믹 프로그래밍' 한글로 '동적 계획법' 이라는 알고리즘은 '리차드 벨만'이 만든 알고리즘 입니다. 리차드 벨만은 최단 경로를 찾는 '벨만 포드 알고리즘'도 만들었습니다. ​ ​ 1. 다이나믹 프로그래밍 이란? 데이터를 캐싱해 두고 이를 재사용 하므로써 중복된 연산을 피하기 위한 알고리즘 입니다. ​ ​ 2. 재귀 함수의 이슈 피보나치 수열은 다음과 같습니다. 정리하면 다음과 같은 조건식 입니다. 1. f(1) = f(2) = 1 [base case] 2. f(n) = f(n-1) + f(n-2) [general case] ​ ​ 3. 피보나치 수열 재귀함수로 구현 피보나치를 구현하는 가장 단순한 방법은 재귀 함수를 사용하는 방법 입니다. int fib(int n){ if(n == 1 || n ==..

1. Hash 알고리즘 예를 들어 43, 36, 44, 21, 25, 30, 22, 17 이라는 데이터를 가지고 있고, h(k) = k % 10 이라는 함수가 있습니다. 위 데이터를 h(k) 함수에 대입하여 얻은 값을 테이블에 인덱스로 사용하고, 해당 튜플에는 위 데이터를 저장해두는 방식 입니다. 여기서 h(k)는 hash 함수 라고 하고, 테이블은 hash 테이블 이라고 합니다. 예를 들어 43 데이터를 h(k) = k % 10 이라는 hash 함수에 대입 하면 43 % 10 = 3이 됩니다. 따라서 hash 테이블의 인덱스 3의 43을 저장 합니다. hash 함수는 데이터의 특성에 따라 달라 질수 있고, 개발자가 정의 내릴수 있습니다. 충돌이 적은 함수가 좋은 hash 함수 입니다. 동일한 데이터라면..