Home

2016년 1월 4일 - 1월 8일

소프트웨어 역량 강화 특강 - 알고리즘 문제 풀이

---

Day 5 - 동적 계획법

5일차 강의노트

문제 1. 최장 공통 부분열(longest common subsequence)

####문제설명 보기

풀이 5-1A. 최장 공통 부분열의 길이만 찾아내는 방법

풀이 5-1B. 최장 공통 부분열을 출력하는 방법

문제 2. 서로 다른 부분열 (Distinct subsequences)

####문제설명 보기

문제 3. 여행(Adventures in Moving)

####문제설명 보기

문제 4. 신입생 관리(Herding Frosh)

####문제설명 보기

---

Day 4 - 신장트리, 최단경로, 그리고 탐욕기법

4일차 강의노트

문제 1. 최적의 보급망을 구축하라

####문제설명 보기

풀이 4-1A. 구현결과

문제 2. 가장 빠른 보급로를 찾아라

####문제설명 보기

풀이 4-2A. 구현결과 - 수업 이후에 풀이 업로드 예정

문제 3. 하노이 탑이 또 말썽이다!(Hanoi Tower Troubles Again!)

####문제설명 보기

풀이 4-3A. (기둥의 수가 적당히 적을 때) 구현결과

풀이 4-3B. (많은 기둥에도 동작하는 버전) 구현결과

문제 4. 주근깨(Freckles)

####문제설명 보기

풀이 4-4A. 구현결과

문제 5. 체스판 위의 개미 (Ant on a Chessboard)

####문제설명 보기

풀이 4-5A. 구현결과

---

Day 3 - 그래프와 트리, 탐욕기법

3일차 강의노트

문제 1. Heap을 구현해 보자.

풀이 3-1A. 구현결과

문제 2. Heap을 이용하여 정렬 작업을 수행하라.

풀이 3-2A. 구현결과

문제 3. 보급로를 확인하라

####문제설명 보기

풀이 3-3A. 구현결과 (dfs with stack)

풀이 3-3B. 구현결과 (bfs with queue)

문제 4. 서열 정리

####문제설명 보기

풀이 3-6A 풀이

---

Day 2 - 데이터의 정렬과 자료구조의 활용

2일차 강의노트

문제 1. 스택을 구현하라.

풀이 2-1A. 구조체를 이용한 스택 구현

풀이 2-1B. 클래스를 이용한 스택 구현

문제 2. 큐를 구현하라.

풀이 2-2A. 구조체를 이용한 큐 구현

풀이 2-2B. 클래스를 이용한 큐 구현

문제 3. 거품정렬을 구현하라.

풀이 2-3A. 구현결과

풀이 2-3B. 버블작업을 통한 구현

문제 4. 퀵정렬을 구현하라.

풀이 2-4A. 구현결과

문제 4-1 거품정렬과 퀵정렬의 비교

풀이 2-4-1A. 구현결과

풀이 2-4-1B. 정렬된 데이터에도 잘 동작하는 퀵정렬

문제 5. k-min을 구하라.

####문제설명 보기

풀이 2-5A. 구현결과

풀이 2-5B. 구현결과(Quick sort에 사용된 partition을 이용한 풀이)

문제 6. 비토와 친척들(Vito's Family) 새로 풀기

####문제설명 보기

풀이 2-6A. k-min을 이용한 풀이

문제 7. 빛, 더 많은 빛(Light, More Light)

####문제설명 보기

풀이 2-7A. 풀이

---

Day 1 - 문제 풀이의 이해

1일차 강의 노트

문제 1. 3n+1 문제

####문제설명 보기

풀이 1-1A. 반복문만 이용하기

풀이 1-1B. 함수 재귀호출 사용하기 (수열도 찍어 보기)

풀이 1-1C. 문제의 요구조건에 따라 함수 재귀호출 사용

문제 2. 누승(factorial) 문제의 재귀적 구현

풀이 1-2A. 누승 구하기

문제 3. 거듭제곱 구하기

풀이 1-3A. 순진한 풀이법

풀이 1-3B. 분할정복 기법으로 풀기

문제 4. 피보나치 수열 구하기

풀이 1-4A. 절대로 따라 해서는 안 되는 풀이법

풀이 1-4B. 제대로 된 풀이법

문제 5. 유쾌한 점퍼(Jolly Jumpers)

####문제설명 보기

풀이 1-5A. 배열 두 개로 구현하기

풀이 1-5B. 배열 한 개로 구현하기

풀이 1-5C. 메모리 낭비 없이 구현

문제 6. 암호깨기 II (Crypt Kicker II)

####문제설명 보기

풀이 1-6A. 암호 깨기 풀이

문제 7. 프로그래밍 챌린지: 비토와 친척들(Vito's Family)

####문제설명 보기

풀이 1-7A. 버블소트를 이용한 풀이

---

임시