본문 바로가기

알고리즘(アルゴリズム）

Stack과 Queue에 대한 고찰!!! 필자는 Stack과 Queue가 어떠한 상황에서 사용하면 될지에 대한 생각을 해 보았다. Stack -> 어떠한 문제를 풀기 위해서 가장 마지막의 데이터를 먼저 풀고 점진적으로 가장 처음의 데이 터를 풀어야 할 떄! 위와 같은 방법을 사용하기 위해서는, Stack과 같은 Last In First Out과 같은 구조로 Stack에 쌓여 있는 데이터들이 단방향으로 보관되어야 할 필요가 있다. ex) 1. 재귀 함수(리프에서 시작하여 위로 올라오는 재귀함수)를 for문으로 고칠 떄! 2. DFS(); Queue -> 어떠한 문제를 풀기 위해서 장 처음의 데이터를 먼저 풀고 점진적으로 가장 마지막의 데이터를 풀어야 할 떄! 위와 같은 방법을 사용하기 위해서는, Queue와 같은 First In First Out.. 더보기
재귀함수 -> 반복문 : stack , queue 자료구조를 적극 활용하자!!! 재귀 함수는 실행 흐름이 Bottom - Up이다 이 말은 하위 문제들을 풀면서 최종값이 산출된다는 것이다. Stack는 Last In First Out, 즉 LIFO 구조이다. 구체적인 설명을 위해서 트리를 예시로 들어 보자. 그 트리는 피보나치 함수를 재귀 함수로 구현했을 떄의 실행 과정을 나타내고 있다고 하자. Fibonachi( 10 )을 구하기 위해서는 트리의 정점에서부터 아래로 내려간다. 그 이유는 Fibonachi( 10 )을 구하기 위해서는 하위 문제 , 즉 Fibonachi(1),(2),(3) 등을 풀어야 하기 때문이다. 즉, 상위 문제를 풀기 위해서는 가장 마지막의 하위 문제(가장 마지막에 push된 데이터)를 풀고, 점진적으로 가장 상위의 문제(가장 이전에 push된 데이터) 순의 실.. 더보기
고정된 데이터들의 탐색 vs 회전하는 데이터들의 탐색 고정된 데이터들의 탐색 [1,2,3,4,5]의 배열이 있다. 전제 1. 데이터들이 오름차순으로 정렬이 되어 있다. 2. 데이터들의 위치가 바뀌지 않고, 고정이 되어있다. -> 걍 이진 탐색(Binary Search)를 사용하면,O(logn)의 time complexity로 탐색하면 된다. 회전하는 데이터들의 탐색 [1,2,3,4,5] ---> [4,5,1,2,3] 전제 1. 초기에는 오름차순으로 이미 정렬이 돼 있는 상태이다. 2. 오른쪽으로 2칸 회전됨.( deque로 회전을 구현 가능) 이떄, 배열은 2가지 종류의 정렬된 배열로 분할 가능 : [4,5] , [1,2,3] 회전하는 데이터들의 탐색 알고리즘 step 1. start end를 이용하여 mid값을 구한다. step 2. (mid값 >= st.. 더보기
재귀 함수(recursive function)에 대한 메뉴얼 1. 일단은 재귀 함수로 알고리즘을 짜라! 2. 재귀 함수에 의해서 stack over flow가 일어날 가능성이 있는 경우, 반복문으로 고치자. 3. 만약 컴파일러가 tail call에 대한 optimization을 제공을 한다면, 꼬리 재귀 함수로 구현하는 것도 나쁘지 않음 ( 꼬리 재귀 함수의 코드는 반복문으로 바꾸기에 굉장히 직관적이고 좋다. 그러나 구현이 어려움 ㅠㅠ) 재귀 함수의 장점 1. 가독정 좋고, 코드가 짧음. 2. 함수의 stack frame 덕분에 각 함수 단계의 변수 상태가 저장된다. ( 일반 반복문에서는 개발자가 직접적으로 변수 상태를 저장해줘야 한다.) 3. 코드 검증도 쉬움. 재귀 함수의 단점 1. 실행 과정이 직관적이지 않기에, 실행 과정 단계에서의 분석이 어렵다. -> 이.. 더보기
재귀 함수(recursive function) with 꼬리 재귀(tail recursive) 꼬리 함수(tail call) int calculate(int[] data, int multiplier) { int [] tempData = new int[data.length] for(i=0;i.data.length;)i++{ tenodata[i] = data[i] * multiplier; } return accumlatie(tempdata); // 꼬리 호출 } calculate() 실행 중, accumulate(tempdata)가 실행되게 된다. 이 시점에서, caculate() 함수에 대한 stack frame과 더불어 accumulate(tempdata)에 대한 stack frame이 새로 생성이 된다. Q. 위 코드를 봤을 때, caculate() 함수에 대한 stack frame을 만드는 것.. 더보기
[Hash Table vs Hash Map vs 배열] vs Linked List 결론부터 말을 하자면, 단순한 데이터의 저장(&&삭제 && 탐색)은 배열과 Hash(해쉬 테이블, 해쉬 맵)을 사용하도록 하자!!! ( 연결 리스트는 데이터가 굉~~장히 많을 때 추천!! 그 이유는 아래에서 자세히 설명을 하겠다.) 데이터를 저장,삭제,저장할 떄 배열과 Hash(해쉬 테이블과 해쉬 맵)을 주로 사용하는 이유 1. 배열과 해쉬는 인덱스와 해쉬 함수를 사용하면 탐색 시, O(1)의 time complexity를 가지므로 매우 빠르다. ( 배열은 데이터들이 메모리 상에서 물리적으로 인접해 있기에, CASHING 측면에서도 매우 유리!) (실무에서는 데이터가 예를 들어, 1000만 개 이상 정도로, 데이터가 많을 때가 아니면 연결 리스트를 잘 사용x) 2. 배열과 해쉬는 코드 상에서 포인터 변수.. 더보기
C++ - 2개 이상의 Delimiter를 사용한 Parsing Template strtok() C언어 : #include C++ : #include string s; char* num; ..... void parsing_template() { num = strtok((char*)s.c_str(), "[,]"); while (num != NULL) { v.emplace_back(num); num = strtok(NULL, "[,]"); } } ( 위 파싱 코드를 템플릿 마냥 외우자) C++의 문자열 스타일(string)을 C언어 문자열 스타일(Char*)로 전환을 해 줘야 한다. 이때 사용되는 함수는 string :: c_str()이다. string cppStr = "CPPstring"; const char * cStr2 = cppStr.c_str(); string :: c_str(.. 더보기
conanical coin system 참고 문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net canonical coin system : 오름차순으로 정렬을 하였을 때, A_i = A_i-1의 배수 && A1 = 1인 coin system. 더보기

티스토리툴바