본문 바로가기

분류 전체보기

(246)
재귀적으로 문제 해결하기 (1) 재귀적으로 문제 해결하기(1) 재귀적으로 문제 해결하기.재귀적으로 문제를 푼다는 것은 무엇일까? 가장 대표적인 예인 피보나치 문제를 떠올려보자.피보나치 수열f(n+2) = f(n) + f(n+1) 를 만족하는 수열을 피보나치 수열이라고 한다. 수로 표현하면1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 과 같다.n을 입력받아 n번째 피보나치 수를 구하여라.이 문제를 아래와 같이 푼다면 재귀적으로 푼 것이다.long long fibo(int n){ if ( n == 1 || n == 2 ) return 1; else return fibo(n - 1) + fibo(n - 2); }쉽게말해, 함수 내에서 호출된 함수를 또 호출하는 것이 재귀이다.탈출조건이 있어야 한다.( 여기에선 n == ..
미래를 바꾼 아홉가지 알고리즘 1. 검색엔진 매칭과 랭킹 인덱싱 인덱싱 단어 위치 트릭 위치(근접성) 과 랭킹 메타워드 트릭 페이지 랭크 하이퍼링크 트릭 권위 트릭 무작위 서퍼 트릭 웹 스팸, 링크 기반 랭킹 알고리즘 2. 공개키 암호화 공유비밀 덧셈 트릭 디피-헬먼 키 페인트 혼합 트릭 공개키 알고리즘 개인 수, 공개 수 공개 - 개인수 (PPN) 3. 오류 정정 코드 검출과 정정 반복 트릭 리던던시 트릭 심벌 - 코드워드 (해밍 코드) 체크섬 트릭 핀포인트 트릭 (이차원 패리티) 4. 패턴인식과 인공지능 인접이웃 트릭 (KNN) 스무고개 트릭 (의사결정 나무) 인공 신경망 (ANN) 5. 데이터 압축 무손실 압축과 손실 압축 무손실 압축 런-렝스 인코딩 전과 같음 트릭 더 짧은 심벌 트릭 손실 압축 생략 트릭 JPEG 생략 기법 ..
큐 구현하기 만약에, 면접장에서 큐를 구현해보라는 말을 들으면 어떻게 해야할까? 이런 기본적인 자료구조를 바로 짜보라는 질문에 대비하여, 지금 다시 한번 복습해보자. 1. 배열로 구현하기 기본 자료구조를 먼저 정의해보자. 배열을 이용하여 queue의 사이즈를 정하여 선언한다. head, tail 그리고 queue의 현재사이즈를 담는 선언한다. #define QUEUE_CAPACITY 8 int queue[QUEUE_CAPACITY]; int head = 0; int tail = -1; int queue_size = 0; 이제 큐에 원소를 삽입, 삭제하는 함수를 짜보자. void enqueue(int n){ if ( queue_size == QUEUE_CAPACITY ){ printf("queue is full! \n..
개발 공부하며 티스토리하기 당신이 컴퓨터공학과 출신이거나 혹은 신입 개발자 취업 준비를 해왔다면, 수 많은 개발자 분들의 블로그를 보았을 것이다. 나 역시 그러했다. 세상엔 참 천재같으면서도 친절한 사람이 많더라. 알고싶은 것들에 대해 키워드만 넣어 구글링하면, 이미 공부하신 다른 분들의 지식, 그들의 고민과 노력에 대해서 알 수 있게 된다. 나는 단지 후발주자로서 많은 혜택 받고 산다. 이러한 생각과 느낌은 비단 나만 그런 것은 아닐 것이다. 처음에 한 두번은, 그냥 간단히 검색겸 혹은 전공 수업에서 이해 안되는 것들에 대해서 하나씩 검색해보다가, 어느 순간 이런 지식의 공유는 개발자들 사이의 독특한 문화임을 깨닫는다. 그리고 감사하면서도, 너무나 모자른 나 자신이지만 스멀스멀 하나씩 뭔가를 기록하고 공유하고싶은 생각이 들기 시..
연결리스트 구현하기 자료구조를 공부해본 사람은 누구나 연결리스트가 뭔지 알 것이다. 이를 복습차, 코드로 다시 구현해보자.1. 노드 정의먼저 연결리스트의 각 노드의 구조체를 정의해보자. 이는 교과서 처럼 다음과 같다.struct _node{ int key; struct _node *next; } note_t; typedef struct _node node_t;여기서는 int 라고 했는데, int 가 아니여도 좋다. 저 구조체 안에 추가적으로 넣고 싶은 변수를 더 넣어도 된다.next 라는 포인터를 통해 다음 노드와 연결된다.2. 노드 삽입연결리스트에 노드를 삽입한다는 것은 일반적으로 리스트 끝 노드에 노드를 추가하는 것이다.연결리스트는 또한 일반적으로 리스트 앞부분을 가리키는 포인터인 head와 끝을 가리키는 포인터인 ta..
팩토리얼 계산하기 1 * 2 * .. * n 과 같은 꼴을 팩토리얼이라 하고, 기호로 n! 이라고 한다. 예를 들면, 1 * 2 * 3 = 3! 이다. 일반적으로 팩토리얼을 구하는 방법은 다음 두 가지 방법이 있다. 1. 반복문으로 구하기 int factorial(int n){ int r, i; r = 1; for (i = 2 ; i