본문 바로가기

알고리즘

[C++/ACM] 820 Internet Bandwidth 문제: http://uva.onlinejudge.org/ external external/8/820.html 예전에는 손도 못대던 문제가 그래프 관련 문제였다. 하지만, 의외로 많은 문제들을 그래프로 풀 수 있고 재미있는 문제들도 많다. 그래서 요새는 어떤 문제가 주어지면 혹시나 그래프로 그래프로 풀 수 있는게 아닌가부터 생각한다. 이번 문제는 문제만 읽어봐도 Maximum flow 문제라는 것을 알고리즘을 공부해본 사람은 누구.. 더보기
[알고리즘] Interval Scheduling 알고리즘 수업을 들으면 Greedy 알고리즘의 첫 번째 예로 살펴보는 것이 바로 이 interval scheduling 문제이다. 작업 목록과 각 작업을 수행할 수 있는 시간 구간이 주어진다. 그리고 최대 몇 가지 작업을 할 수 있는지를 알아내는 문제이다. 실제로 선택되는 작업들이 유일하지 않을 수도 있다. 쉬운 예를 들어보자.    T1: 1시-3시 청소 T2: 2시-4시 숙제 T3: 3시-5시 낮잠 T.. 더보기
[C++] 문자열 배열에서 세번째로 긴 문자열 출력 문제) 주어진 문자열 배열에서 세번째로 긴 문자열 출력하라. 지난 번 폰 인터뷰에 나왔던 문제이고, 이전 포스팅인 '배열에서 두번째로 작은 수를 구하기'와 거의 유사하다. 다만, string class를 좀 제대로(?) 사용해보고자 다시 해봤다. #include <iostream> #include <string> using namespace std; void swap(string *a, string *b) { st.. 더보기
[2009.03.19] 두번째 폰 인터뷰 지난번에 망친 폰 인터뷰 때문에 연락도 오지 않을 줄 알았더니 연락이 오긴 왔다. 2명의 인터뷰어가 서로 정보를 공유하지 않고 2번을 본 후 의견을 조합해서 다음으로 진행할지 결정하는 모양이다. 지난번에 Non Technical 질문을 하도 개발새발 대답해서 이번에는 준비 좀 해놨더니, 바로 코딩하자고 한다. :( factorial 함수를 구현하라. 헐... 문자열 배열에서 3번째로 긴 문자열을 출력하는 함수를 구현하라. rotated sort.. 더보기
[C++] 부분 문자열 검사 (Substring) 문제) 문자열 A가 주어지고, 그것보다 짧은 문자열로 구성된 배열 T가 주어진다. 배열 T에 들어있는 각 문자열이 A의 부분 문자열인지를 검사한다. 물론, C++에서 제공하는 string 클래스의 find 함수를 사용하면 하고 말 것도 없다. 여기에서는 좀 더 효율적이라고 생각되는 방법을 디자인해보는 것이 목표이다.  예를 들어 A가 'apple'이라는 문자열이라고 하자. 이제, T의 임의의 문자열 t가 'appl.. 더보기
[C++] 전화 번호 문자열 변환 (Telephone Words) 문제) 전화기의 몇몇 번호에는 알파벳이 할당되어 있다. 전화 번호가 주어지면 가능한 알파벳 조합을 모두 출력하라. 단, 0, 1번에는 알파벳이 할당되어 있지 않고, 2~8번에 각 3개씩 알파벳이 할당되어 있다고 하자. 단 Q, Z는 할당되어 있지 않다. 일종의 순열 출력 문제라고 할 수 있다. 예를 들어 번호가 123번이면 1AD, 1AE, 1AF, 1BD, 1BE, 1BF, 1CD, 1CE, 1CF와 같이 9가지가 나온다. 기본적으로 재귀(rec.. 더보기
[C] 회전된 문자열인지 판별 Given two two strings, s1 and s2, write a program to check if s1 is a rotation of s2. But you can use strstr() only once. (abcdef = cdefab) 간단해 보이는데 방법이 잘 떠오르지 않았다. 침대에 엎드려서 생각해낸 방법으로 열심히 코딩을 한 후 답안을 확인해보니 2줄이면 끝난다.  내가 사용한 방법은 s1의 .. 더보기
[C] 문자열에서 반복되는 가장 긴 부분 문자열 Write a program to extract the longest repeated substring in a given string. 주어진 문자열에서 반복되는 가장 긴 문자열을 추출하자. 문자열의 길이를 n이라고 했을 때 가장 무식한 방법은 모든 가능한 문자열을 다 구해서 반복되는 문자열을 찾고 긴 문자열을 출력하면 된다. 비교 대상인 두 문자열의 시작점을 i, j라고하고 문자열의 길이를 k라고 하고,.. 더보기