두런두런

이전내용 링크 완전탐색 정렬 문자열 배열,리스트 스택, 큐 해시 힙 DFS, BFS DP, 동적계획법 한동안 DP 알고리즘에 빠져 한달간을 DP 공부만 진행했었다. 이번 주제는 DP가 고안된 이유이자 가장 유명한 알고리즘인 분할 정복에 대해 공부 했다. 15. 분할 정복 가장 유명한 알고리즘이다. 주어진 문제를 둘 이상의 부분문제로 나눈다. 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다. 일반적인 재귀 호출과 다른점은 분할 방법에 따라 일반적인 재귀 호출보다 빠르게 동작한다는 점이다. 분할정복은 대부분 세가지의 구성 요소를 가지고 있다. 문제를 더 작은 문제로 분할하는 과정(divide) 작은 문제의 답들을 병합하는 과정(merge) 더이상 문제..

이전내용 링크 완전탐색 정렬 문자열 배열,리스트 스택, 큐 해시 힙 DFS, BFS 14. 동적 계획법 학교에서 알고리즘 수업때만해도 동적프로그래밍이라고 불렀다... 최적화 문제를 연구하는 수학 이론에서 왔으며, 전산학에서 사용하는 동적(Dynamic), 프로그래밍(Programming)과는 아무 관련이 없다고 한다. 따라서 Dynamic Progarmming을 동적 계획법이라고 번역한다. 큰 의미에서 분할 정복과 같은 접근 방식을 사용한다. 분할 정복과의 큰 차이점은 문제를 나눌때 DP에서는 부분문제가 두개 이상의 문제를 푸는데 사용된다. 여러번 계산이 필요한 부분을 부분문제로 나누어 이 문제의 답을 재활용하여 속도의 향상을 꾀한다. 이때, 문제의 답을 메모리에 저장하고 이 저장 장소를 캐시라고 부른다..

이전내용 링크 완전탐색 정렬 문자열 배열,리스트 스택,큐 해시 힙 탐색 기법으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있다. 12. 깊이우선탐색(DFS) 시작노드(혹은 루트노드) 에서 시작하여 탐색을 진행한다. 하나의 경로를 깊게 탐색한다. 깊이가 무한한 트리의 경우 잘못된 방향으로 탐색을 시작하면 무한루프에 빠질 수 있다(이를 방지하기 위해 깊이 제한을 두기도 한다) 깊이 제한까지 도달할때까지 목표 노드가 발견되지 않으면 부모 노드로 돌아와 재탐색을 진행한다(백트래킹) 스택 자료구조를 사용하여 다음 방문할 노드의 정보를 저장한다. 장점 저장공간의 수요가 비교적 적다 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 빠질 가능성이 있다. 구해진 해(경로)..

이전내용 링크 완전탐색 정렬 문자열 배열,리스트 스택,큐 해시 실생활에서는 우선순위에 따라 일을 처리해야 하는 상황이 있다. 이런 경우에 사용되는 자료구조는 우선순위 큐가 있다. 우선순위 큐의 단순한 구현은 모든 배열에 원소를 넣고, 꺼낼때마다 전체 순회 하면서 우선순위에 따라 원소를 추출하는 방법이다. 해당 경우 원소 추가에 O(1), 원소 추출에는 O(N)이 걸리게 된다. 우선순위 큐는 이진 트리로 구현할 수 있고 힙 트리로도 구현 할 수있다. 원소의 삽입 삭제에 O(logN)이 걸리게 되며 대부분의 언어에서 힙을 표준라이브러리로 제공한다. 11. 힙(Heap) 완전 이진트리로 구성되어있으며(책에서 엄밀히 말하면 binary heap이라고 설명하고있으며, 이진트리가 아닌 구조로 이루어진 경우도 있다고..

이전내용 링크 완전탐색 정렬 문자열 배열,리스트 스택,큐 10. 해시(해시 함수) 특정 자료에 빠르게 접근 하기 위한 함수 Key-Value 개념으로 Key 값을 통해 Value에 접근한다. 10-1. Direct Addressing Table 테이블에 Key값 을 인덱스로 저장하는 방법이다. 예로 Value 값이 100이라면 배열의 인덱스가 100인 위치에 Key 값을 저장하고 포인터로 데이터(Value)에 연결한다. 같은 값이 존재하지 않는다고 가정하면(같은 값을 가지는 경우 충돌,Collision 이 발생한다) 데이터의 탐색, 저장, 삭제, 갱신 모두 상수 시간 O(1)에 처리가 가능하다. 하지만 Key값의 크기만큼 배열이 할당 되기 때문에 데이터의 개수가 적고 값이 큰 경우에 메모리 낭비가 발생한..

이전내용 링크 완전탐색 정렬 문자열 배열,리스트 일렬로 늘어선 자료들을 표현하는 자료구조로 배열/리스트를 알아봤다. 일렬로 늘어선 자료를 특정 순서로 넣고 꺼내는 자료구조로 스택/큐가 존재한다. 스택/큐는 배열/리스트로 쉽게 구현 가능하지만 흔히 사용되는 자료구조이며 개발자 간의 원활한 의사소통을 위해서 이름이 붙었다고 한다. 7. 스택 한쪽 끝에서만 자료를 넣고 뺄 수 있다. 가장 늦게 들어간 자료가 가장 먼저 나오는 특성을 갖고 있다(후입선출, LIFO, Last In First Out) 컴퓨터 내부적으로 스택을 사용해 함수의 문맥(context)를 다룬다. 8. 큐 한쪽 끝에서 자료를 넣고 반대쪽에서 뺀다. 처음 들어간 자료가 먼저 나오는 특성을 갖고 있다(선입선출, FIFO, First In Fi..

이전내용 링크 완전탐색 정렬 문자열 5. 배열 & 동적배열 일렬로 늘어선 (같은 종류의)자료 여러개를 저장하기 위한 가장 기초적인 자료구조는 배열이다. 배열과 비슷한 자료구조로 연결 리스트가 존재한다. 배열은 처음 선언할때 크기를 지정해야 하며, 선언된 크기 이상의 자료를 넣을 수 없다. 이를 해결하기 위해 동적 배열이 존재 한다. 동적 배열은 배열을 이용한 별도의 자료 구조이며 대부분의 언어에서 문법이 아닌 표준 라이브러리에 포함 되어있다. 배열(동적배열) 은 다음과 같은 특징이 있다. 원소들이 메모리의 연속된 위치에 저장된다. 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다. 동적배열의 추가적인 특징은 다음과 같다. 배열의 크기를 변경하는 연산(resize)이 가능하다(해당 연..

이전내용 링크 완전탐색 정렬 4. 문자열 현대의 컴퓨터는 많은 양의 문자열 자료를 다루고 이를 처리하는것은 중요하다. 문자열 검색 문제는 주어진 문자열 H(건초, haystack)에서 문자열 N(바늘, needle)을 부분 문자열로 포함하는지 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제를 문자열 검색 문제라고 한다. (건초에서 바늘찾기) 예) H = "network", N = "net" 일때 H[0..2] = N 이므로 H는 N을 포함하고, H에서 N의 시작 위치는 0이 된다. 예) H = "ababa", N= "aba" 일때, H[0..2] = H[2..4] = N 이므로 H는 N을 포함하고, H에서 N의 시작위치는 0, 2 가 된다. 위 문제를 Brute Force하게 풀..

이전내용 링크 완전탐색 3. 정렬 데이터를 정렬 하는 방법이다. 비교정렬, 제자리 정렬, 온라인 정렬 로 구분된다. 비교정렬 : 원소들을 정렬할 때 원소들의 순서에만 의존하는 알고리즘들을 일컫는다. 제자리 정렬 : 원소의 개수에 비해 충분히 무시할 만한 저장공간을 더 사용하는 정렬 알고리즘을 의미한다. 온라인 정렬 : 모든 원소들이 처음부터 주어지지 않고 차례대로 들어오는 경우도 처리할 수 있는 정렬 알고리즘을 의미한다. 아래에는 여러 정렬 기법에 대해 위키백과를 참조하여 설명한다. 설명은 오름차순을 기준으로 한다. 3-1. 삽입 정렬 O(n^2) 3-2. 선택 정렬 O(n^2) 주어진 배열 중에 최소값을 찾는다. 최소값을 첫번째 요소의 값과 바꾼다. 처음 요소를 제외하고 나머지 배열에 대해 1~3 을 ..

취업준비를 하면서 알고리즘 공부의 필요성(코딩테스트)를 느꼈고, 연구실 후배들과 알고리즘 스터디를 진행했다. 0주차 계획 수립을 마치고 1주차 스터디를 진행한다. 이론 진행을 우선 하기로 의논되었고, 첫주에는 완전탐색, 정렬, 문자열에 대해 공부했다. 1. 완전탐색 가장 단순한 알고리즘이다. 무식하게 푼다(Brute Force) 라는 말이 있다. 해당 방법은 컴퓨터의 빠른 연산 속도를 이용해 경우의 수를 모두 나열하여 답을 찾는 방법이다. 예) 10명을 일렬로 줄 세울때, 사이가 나쁜 두 사람이 붙어있지 못하게 하는 경우 10명을 일렬로 세우는 모든 방법을 찾는다(10! 약 360만 가지) 그중 두사람이 붙어있는 경우를 제외한다. 책 '알고리즘 문제해결 전략' 에서는 이와같은 완전탐색 기법을 알고리즘의 ..