programmer life guidance 101

> 이진탐색트리(BST) Dynamic Set 집합이다. 여러개의 데이터의 집합인데, 그것들의 내용이 고정되지 않고, 생성과 삭제를 반복하면서 유동적인 집합이다. 아래와 같은 특징을 가진다. Dynamic Set, Dictionary 또는 Search Structure라고 불린다. 여러 개의 키(key)를 저장 다음과 같은 연산들을 지원하는 자료구조 INSERT - 새로운 키의 삽입 SEARCH - 키 탐색 DELETE - 키의 삭제 예: 심볼 테이블 일반적으로 구현할 때 배열 or 연결리스트를 사용한다. 각 동작에 있어서 다음과 같은 시간복잡도를 가진다. 정렬된 배열의 이진탐색 - O(logn) 정렬된 배열에서 원소를 insert, delete하면 나머지 원소들을 한칸식 shift - O(n) 정렬된 ..

> 트리와 이진트리 기본 트리(Tree) 계층적인 구조를 표현하기 위해 사용하는 자료구조 조직도 디렉토리와 서브디렉토리 구조 가계도 용어 루트(Root) 트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성된다. 맨 위의 노드를 루트라고 한다. 부모-자식(parent-child) 관계 각 노드들의 상하 관계를 부모-자식(parent-child)관계로 나타낸다. 형제 관계(sibling) 루트노드를 제외한 트리의 모든 노드들은 유일한 부모노드를 가진다. 부모가 동일한 노드들을 형제관계라고 부른다. 리프(leaf) 노드 자식이 없는 노드들을 leaf 노드라고 부른다. 리프노드가 아닌 노드들을 내부(internal)노드라고 부른다. 조상-자손(ancestor - descendant) 관계 부모..

> 멱집합 (Recursion 응용) PowerSet 어떤 집합의 모든 부분집합을 멱집합이라고 부른다. 임의의 집합 data = {a, b, c, d}의 모든 부분집합은 2^n =16개이다. Recursion을 이용하여 모든 부분집합 나열 {a, b, c, d, e, f}의 모든 부분집하을 나열하려면 먼저 a를 포함하지 않는 부분집합과 a를 포함하는 부분집합으로 나눌수 있다. 따라서 아래와 같이 표현할 수 있다. a를 포함하지 않는 부분집합 a를 제외한 {b, c, d, e, f}의 모든 부분집합들을 나열하고 a를 포함하는 부분집합 {b, c, d, e, f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다. => 이 두가지를 합치면 경우의 수가 2^n개가 되는 것이다. 그렇다면, {b, c, d, ..

> Counting Cells in a Blob (Recursion 응용) 입력으로 Binary 이미지가 주어진다. 각 픽셀은 background pixel(흰색)이거나 혹은 imagepixel(파란색)이다. 서로 연결된 image pixel들의 집합을 Blob이라고 부른다. 상하좌우 및 대각방향으로도 연결된것을 Blob으로 간주한다. 따라서 위 그림에서는 총 4개의 Blob이 존재한다. 특정 좌표가 속한 Blob의 크기 count 입력 N * N 크기의 2차원 그리드(grid) 하나의 좌표 (x, y) 출력 픽셀 (x, y)가 포함된 blob의 크기 (x, y)가 어떤 blob에도 속하지 않는 경우에는 0 Recursive Thinking 현재 픽셀이 속한 Blob의 크기를 카운트하려면 현재 픽셀이 i..

> 미로찾기(Recursion 응용) (n-1, n-1)의 좌표를 출구로 가정 흰색이 지날 수 있는 길, 파란색이 벽 입구에서 출구까지의 경로를 찾는 문제 Recursive Thinking 현재 위치에서 출구까지 가는 경로가 있으려면 현재 위치가 출구이거나(이미 내가 출구에 와 있거나). 혹은, 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가능경로가 있꺼나, 위의 경우를 Recursive하게 생각한다. 전체 문제를 해결하려고 하면 부분 문제의 해결이 이루어지면서 전체문제가 해결된다. => 위의 둘중에 하나가 성립해야 출구까지 가는 경로가 있다고 할 수 있다. 미로찾기(Decision Problem) - 답이 Yes or No 출발점에서 출구까지 가능 경로가 있느냐 없느냐?의 문제로 생각한다..

알고리즘을 위한 자바 IO codeplus - 프로그래밍 대회에서 사용하는 Java 참고 System.out System.out.println(); System.out.printf("%d", n) 실수형, 문자형 자료 출력 가능 Scanner next[자료형]을 이용해서 입력을 받을 수 있고, hasNext[자료형]을 이용해서 입력받을 수 있는 자료형이 있는지 구할 수 있다. 두 수 입력 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int a, b; a = scanner.nextInt(); b = scanner.nextInt(); System.out.println(a..

> N-Queens (Back tracking) (n = 8) 아래의 예(n=8)에서는 8x8 체스보드에 8개의 말을 놓는데 그 중에 어떤 말들도 동일한 행, 동일한 열, 동일한 대각선 상에 오지 않도록 n개의 말을 놓을 수 있는가에 대한 문제이다. 위의 방법대로 n개의 말을 놓으려면, 결국 조건을 만족하면서 하나의 행에 하나의 말이 와야한다. Back Tracking 내가 지나온 길을 다시 되돌아 가면서 문제를 해결한다 어떠한 결정들을 내려가다가, 결정이 막다른 길이다. 즉, 그 결정을 내려서는 안된다라는 것이 분명해지면, 가장 최근에 내렸던 결정을 번복한다. 이런식으로 문제를 해결한다. 상태 공간트리 1번말이 (1,1)에 위치했을 때, 그리고 그 때 2번말이 (2,1), (2,2), (2,3), (2..

> Locality의 관점에서 Quick sort가 Merge sort보다 빠른이유 Quick sort와 Merge sort는 nlogn의 시간복잡도를 가지는 대표적인 정렬 방법이다. 일반적으로 Quick sort가 Merge sort보다 크다. 그 이유는 Locality와 관련이 있다. Locality의 개념을 알아보고 왜 Quick sort가 더 빠른지 알아보도록 하자. Locality 지역성(Locality)은 CPU가 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복적으로 엑세스하는 경향을 말한다. 메모리 내의 정보를 균일하게 엑세스 하는게 아닌, 짧은 시간내에 특정 부분을 집중적으로 참조하는 특성이다. void f() { //간단한 작업을 수행 } void g() { int arr[1000]..

> Tail Call Recursion C++ 제가 이번에 설명할 것은 제가 검색하다가 발견한! Tail Call Recursion 이라는 새로운 재귀?적인 방법의 코딩입니다. 기존의 재귀함수와 비교하면서 설명하도록 하겠습니다. 1. 기존의 재귀함수 먼저 기존의 재귀함수를 보도록합니다. 여기서는 가장 대표적인 피보나치 수열을 이용한 재귀함수를 살펴보겠습니다. #include using namespace std; int f(int n){ if(n < 0) return 0; if(n < 2) return n; return f(n-1) + f(n-2); } int main(void){ cout

> 이진트리 1. 후위 순회(postorder) 이진 트리(binary tree)의 후위 순회 알고리즘이 사용될 수 있는 대표적인 예는 특정 디렉토리(directory)의 용량 계산이다. 단, 이진 트리이기 때문에 특정 디렉토리(=폴더)의 서브 디렉토리의 개수는 2개 이하로만 존재해야 한다. 삼진 트리(ternary tree)였다면 서브 디렉토리는 총 3개까지 존재할 수 있다. 1.1 디렉토리의 용량 계산 디렉토리의 용량 계산을 위해서는 어떤 알고리즘이 사용되야하는가를 먼저 고민해보자. 생각을 할 때 구체적인 상황을 두고 예시를 들어보면 이해가 빠르다. 현재 사용하는 컴퓨터에 datastructure 라는 디렉토리가 있다고 가정해보자. 이 datastructure 디렉토리 내부에는 stack, queue..

> N-gram 빅데이터 분석, 검색 엔진에서 많이 쓰인다. 구글은 책들을 스캔해서 N-gram viewer를 만들었는데 사람들의 언어 패턴을 시대별로 분석하기도 함. N-gram은 문자열에서 N개의 연속된 요소를 추출하는 방법. 만약 "hello"라는 문자열을 2-gram으로 추출하면 He, el, ll, lo 글자 단위 N-gram( 2gram ) #include #include int main(){ char text[30] = "Hello"; int length; length = strlen(text); for (int i=0; i

> 회문판별 회문은 유전자 염기서열 분석에서 많이 쓰인다 회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 말한다. #define _CRT_SECURE_NO_WARNINGS #include #include #include int main(){ char word[30]; // 단어 저장 배열 int length; // 문자열 길이 bool isPalindrome = true; // 회문 판별값을 저장할 변수, 초깃값 TRUE printf("단어 입력하세요: "); scanf("%s", word); length = strlen(word); // 0부터 문자열 길이의 절반만큼 반복 for(int i=0; i