태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.

예전에는 손도 못대던 문제가 그래프 관련 문제였다. 하지만, 의외로 많은 문제들을 그래프로 풀 수 있고 재미있는 문제들도 많다. 그래서 요새는 어떤 문제가 주어지면 혹시나
그래프로
그래프로 풀 수 있는게 아닌가부터 생각한다. 이번 문제는 문제만 읽어봐도 Maximum flow 문제라는 것을 알고리즘을 공부해본 사람은 누구나 알 수 있는 문제이다. 

학부 알고리즘 수준에서 NPC를 제외하면 제일 까다로운 부분이 아닐까 생각된다. 기초적인 부분을 제외하고 이론적으로 따지고 들면 따라가기도 꽤 어렵다. 어쨌든, 이 문제는 기본적인 Max flow 알고리즘을 따라가면서 풀면 쉽게(?) 풀린다. 가장 쉬운 Ford-Fulkerson 방식이다.

간략히 알고리즘을 살펴보자.
출발 노드(s)에서 끝 노드(t)까지 flow를 보낼 수 있는 path p를 찾아서 그 p를 이루는 edge들의 residual capacity (해당 edge로 더 보낼 수 있는 flow의 최대 크기)중에서 가장 작은 c_min를 먼저 구한다. BFS 혹은 DFS를 사용하여 해당 p가 존재하는지를 알 수 있다. p의 각 edge의 flow를 c_min만큼 증가(augment)시켜준다. 이러한 작업을 계속 하다보면 더 이상 s에서 t로 flow를 보낼 수 있는 길이 없게 되는데, 그 때 s에서 나가는 flow들의 합, 혹은 t로 들어가는 flow들의 합을 구하면 그게 Max flow가 된다.

처음에 당당히 WA(Wrong answer)를 받아서 왜 그런가 생각을 해봤다. 
  1. 먼저, 마침표(.)를 안 찍은 것을 발견했다. 또 다시 WA. 
  2. 이번에는 뭔가 구현상에 문제가 있는 것이 아닌가 생각을 했다. 교과서(CLRS)에는 anti-parallel edge만 존재한다고 가정한다. 따라서, 두 노드 사이에 edge가 어느 방향으로 있는지가 꽤 중요하다. augment하려는 edge가 존재하면 c_min만큼 flow를 증가시키지만, 해당 edge가 존재하지 않으면 반대 방향으로 flow를 증가, 즉, 원래 방향으로는 flow를 감소시켜야 한다. 하지만, 이 문제에서는 항상 bi-directional한 edge가 존재하므로 이 부분을 고려하지 않아도 된다고 생각했다. 그래서 다른 사람이 짠 소스를 살펴봤더니 a->b가 c_min만큼 증가되면, b->a는 c_min만큼 감소시켰다. 나도 그렇게 바꾸고 다시 제출했다. 그런데 역시 WA. 
  3. 이번에는 문제를 다시 읽어봤다. 각 test case마다 newline이 있어야 한단다. 추가했더니 AC(accepted)
  4. 다시 2번에서 고쳤던 부분을 원래대로 돌렸다. 역시 AC. 문제는 1, 3번이었다. 2번을 적용하도 않아도 되는 것이 맞는지, 아니면 우연히 맞은 것인지는 좀 더 생각해 봐야 한다.

소스 열기

문제) 주어진 문자열 배열에서 세번째로 긴 문자열 출력하라.

지난 번 폰 인터뷰에 나왔던 문제이고, 이전 포스팅인 '배열에서 두번째로 작은 수를 구하기'와 거의 유사하다. 다만, string class를 좀 제대로(?) 사용해보고자 다시 해봤다.

소스 보기

문제) 문자열 A가 주어지고, 그것보다 짧은 문자열로 구성된 배열 T가 주어진다. 배열 T에 들어있는 각 문자열이 A의 부분 문자열인지를 검사한다.

물론, C++에서 제공하는 string 클래스의 find 함수를 사용하면 하고 말 것도 없다. 여기에서는 좀 더 효율적이라고 생각되는 방법을 디자인해보는 것이 목표이다. 

예를 들어 A가 'apple'이라는 문자열이라고 하자. 이제, T의 임의의 문자열 t가 'apple', 'pple', 'ple', 'le', 'e'의 prefix인지 확인하면 된다. t의 첫 글자가 'a', 'p', 'l', 'e' 중의 하나가 아니라면 더 이상 비교해 볼 필요도 없다. 만일 t의 첫 글자가 'p'이면, 두 번째 글자가 'p' 혹은 'l'인지를 확인한다. A 문자열을 가지고 다음과 같은 N-ary Tree를 그리면 된다. 나의 그래프 표현 방식이 이해가 될지는 모르겠다. 왼쪽에서 오른쪽으로 보면 된다.

A+a-p-p-l-e
 +p-p-l-e
 | +l-e
 +l-e
 +e

이진 검색 트리(Binary Search Tree)는 나름 구현하기 쉽지만, N-ary tree는 구현해 본적이 없다. 자식 노드가 여러 개인 것을 어떻게 표현해야 할까 싶다. 노드의 자식 노드에 대한 포인터를 연결 리스트(Linked List) 혹은 배열로 구현해도 될 것 같다. 이번에는 C++에서 제공하는 vector를 사용해보기로 했다. 

그런데, 문제가 생겼다. 구조체 내에 vector를 선언하고 계속 데이터를 push_back을 하다 보니 메모리 위치가 중복되는지 segmentation fault가 난다. 해당 node 구조체를 malloc으로 선언할 때 그 구조체 크기보다 훨씬 크게 선언해주면 segmentation fault가 나지 않는다. 문제는 알겠지만, 해결책은 아직 구하지 못했다. 문제가 되는 라인은 32번째 라인이다.

아직 C도 아닌 것이 C++도 아닌 오묘한 코드이다.

소스 열기

문제) 전화기의 몇몇 번호에는 알파벳이 할당되어 있다. 전화 번호가 주어지면 가능한 알파벳 조합을 모두 출력하라. 단, 0, 1번에는 알파벳이 할당되어 있지 않고, 2~8번에 각 3개씩 알파벳이 할당되어 있다고 하자. 단 Q, Z는 할당되어 있지 않다.

일종의 순열 출력 문제라고 할 수 있다. 예를 들어 번호가 123번이면 1AD, 1AE, 1AF, 1BD, 1BE, 1BF, 1CD, 1CE, 1CF와 같이 9가지가 나온다. 기본적으로 재귀(recursion)를 사용하는 것이 생각하기 쉽다. 여기에서는 재귀 이외에도 반복(iteration)을 사용하는 것도 생각해보자.

더보기


테크니컬 면접 문제의 단골인 연결 리스트(Linked List). 그 중에서도 가장 많이 나온다는 뒤집기 문제이다. 

기본적인 연결 리스트를 구현 할 줄 알아야 겠다. C/C++을 이용한다고 할 때, struct 혹은 class로 먼저 node를 정의한다. 필요한 기본 함수로는 insert, delete, print(
traverse
traverse) 정도가 되겠다. delete는 뒤집기에는 필요하지 않으므로 생략한다. 

C/C++로 구현하기 위해서는 포인터에 대해서 알아야 한다. 새 노드를 head가 가리키는 첫 노드로 삽입하는 insert를 구현하기 위해서는 포인터의 포인터(A pointer that points to a pointer)를 인자로 넘겨야 head가 가리키는 노드를 새 노드로 변경할 수 있다는 점에 주의해야 한다. 

리스트를 뒤집는 reverse 함수를 구현할 때에도 잘못 생각하면 무한 루프에 빠지게 되는데 주의해야 한다. 이전 노드, 현재 노드, 다음 노드를 테이블로 그려보고 적절히 값이 어떻게 바뀌어야 할지 생각해보면 할 수 있다.

그런데, 종이만 주고 이걸 구현하라고 하면 쉽게 완성하지는 못할 것 같다. 포인터가 아직 완전히 익숙하지 않아서 부분부분 오류를 낼 것 같다. 조금 더 다양한 것을 구현해보는 연습을 해야겠다. 

소스 보기

  1. broYobi 2010.03.01 23:12 신고

    요즘 재미있는게 많이 포스팅 되네..ㅋ

    (쓸데없이)reverse를 recursion으로 만들고 싶지 않나?? ㅎㅎ

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2010.03.02 04:43 신고

      recursion으로 만들자면, 구 연결 리스트에서 head 노드를 계속 떼어서 새로운 연결 리스트의 head 노드로 넣으면 되나? [NIL, 1->2->3->4], [1, 2->3->4], [1<-2, 3->4] 좀 이상하네. 어떻게 하면 되겠노?

  2. broYobi 2010.03.02 14:26 신고

    이건 어때?

    Node* reverse(Node *node){
    Node *newHead;
    if(node==NULL)
    return NULL;
    if(node->next == NULL)
    newHead=node;
    return node;
    }

    newHead = reverse(node->next);
    node->next->next = node;
    node->next = NULL;
    return newHead;
    }

    메인함수에서
    reverse(&head)를 head = reverse(head)로 바꾸고..

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2010.03.04 17:50 신고

      {가 하나 빠진듯. if (node == NULL || node->next == NULL) return node;로 앞부분을 다 뭉뚱그려도 될 듯. 어쨌든, 잘 했네. recursive가 좀 더 직관적이긴 하네.

  3. 서여빈 2011.07.19 10:43 신고

    우연히 보고서 한마디 적어봐요 ㅋ
    위의 방법도 있겠지만 이런 방법도 있겠네요~
    기존 연결리스트 A가 있고 다른 헤드 역할을하는 B라는 포인터가 있을때 A 연결리스트를 루프를 돌면서 선택되는 모든 노드를 무조건 B포인터의 다음 위치에 두는거죠. 그럼 B연결리스트는 A연결리스트의 역순으로 생성이 되고 마지막에 헤드값만 바꿔버리면 끝!

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2011.07.22 07:35 신고

      결국 new linked list를 하나 만드는데 (with a new head - B)
      원래 list에서 순서대로 traverse하면서
      B에다 insert_after_headnode를 계속한다는 거군요.

      의견 감사합니다.

학부 1학년 때 컴퓨터 개론 시간에 C를 배웠던 것 같다. 당시 전혀 학과 공부를 신경쓰지 않던 나는 수업을 통해 배우는 게 별로 없었다. 아직도 C조차 제대로 모르는 이유는 여기에서 기인한다. 어쨌든, 그 때 마지막 과제던가? 퀵 정렬을 C로 짜오라는 과제가 있었던 것 같다. 당시에 퀵 정렬이라하면 최고 수준의 프로그래밍 실력이 있어야 할 수 있다고 생각했다. 마치, 1학년 당시 '학점이 3.0을 넘는 사람은 인간이 아니다'라고 믿었던 것처럼 어이없는 믿음이였지만 말이다. 재귀(recursion)가 들어가면 일단 머리가 돌아가지 않았다. 

 퀵 정렬의 기본 개념을 보면, 주어진 수 중에 임의의 값(pivot)을 기준으로 그 값보다 작은 값과 큰 값으로 나눈 후 이 pivot 값을 가운데 놓은 후, 두 부분을 각각 다시 퀵 정렬한다. 머지 정렬(merge sort)와 비슷한데, 머지 정렬은 단수히 두 분으로 계속 나누다가 합쳐질 때 양쪽에서 작은 값들 부터 뽑아 내어 정렬한다. A={1,3,4}와 B={2,5,9}가 있으면 A,B,A,A,B,B 순으로 앞의 수를 뽑아 {1,2,3,4,5,9}로 만들어 준다. 둘 다 평균 O(nlgn)의 시간 복잡도를 가진다. T(n)=T(n/2)+O(n)을 풀어서 나오는 듯.
#include <iostream>

using namespace std;

void swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void quicksort(int *arr, int s, int e) {
	int p = s;

	if (s >= e) return;	

	for (int i = s; i < e; i++) {
		if (arr[e] >= arr[i]) {
			swap(arr[i], arr[p]);
			p++;
		}
	}
	swap(arr[p], arr[e]);

	quicksort(arr, s, p-1);
	quicksort(arr, p+1, e);	
}

int main() {
	int arr[] = {8,1,3,7,4,15,9,11};
	int arr2[] = {9,4,1,3,24124,12412,412,412, 3,1};

	quicksort(arr, 0, 7);

	for (int i = 0; i < 8; i++)
		cout << arr[i] << " ";
	cout << endl;

	quicksort(arr2, 0, 9);

	for (int i = 0; i < 10; i++)
		cout << arr2[i] << " ";
	cout << endl;
}
학부 1학년으로 돌아가면 즐겁게 다시 공부할 수 있을 것 같다. ㅎㅎ
  1. broYobi 2010.02.22 18:05 신고

    merge는 메모리를 많이 먹어용..

  2. Favicon of http://zzun.net BlogIcon zzun 2010.02.25 20:19 신고

    늦지 않았다 ㅋㅋ

이번에는 string에서 반복되지 않는 첫번째 문자를 찾아본다. 예를 들면 "appropriate"에서 o를 선택하면 되는 것이다. 문자열의 길이를 n이라고 하면 O(n)인데 실제로는 n을 최대 두번 읽는다. 더 좋은 방법은 없을까?
#include <iostream>

using namespace std;

char firstchar(string str) {
	char ch[128];
	char tmp;
	
	for (int i = 0; i < 128; i++)
		ch[i] = 0;
	
	int len = str.length();
	
	for (int i = 0; i < len; i++) {
		tmp = str.at(i);
		ch[tmp]++;
	}
	
	for (int i = 0; i < len; i++) {
		tmp = str.at(i);
		if (ch[tmp] == 1)
			return tmp;
	}
	return NULL;
}

main() {
	string str[] = {"Niceee", "babbyddas",
		"Gorooeadsjfabdfmadslfdlfa", "a", "aabb"};
	
	for (int i = 0; i < 5; i++)
		cout << firstchar(str[i]) << endl;
}
  1. Favicon of http://zzun.net BlogIcon zzun 2010.02.19 16:25 신고

    반복되지 않는 문자를 간단히 solo 라고 하면,

    루프를 한 번만 돌면서...
    1. 지금현재까지의 first solo
    2. 해당 solo가 탈락(중복)되었을 때의 next solo(배열)

    위 두 가지 정보를 유지/갱신하면서 돌면 될 것 같은데
    얼추 생각해봐도 코드가 매우 복잡할듯;

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2010.02.19 17:24 신고

      abacac의 경우 순서대로 a ab b bc bc a가 되어 a가 답이 되어야 하는데, 결국 이 solo 리스트에 현재 index의 문자가 있는지 매번 확인을 해야하니까 worst case가 O(n)이 되고, 전체는 O(n^2)이 되지 않나? 결국 걍 2n하는게 O(n)라서 더 나을 듯 한데. BST나 heap으로는 안될 것 같고.

      잘 모르겠다.

  2. broYobi 2010.02.22 18:03 신고

    이론적인 것만 고려한다면

    피보나치 힙을 (넣을 때, O(1), 뺄 때 O(log(n)) 사용하면 가능할 것 같네..

    하지만 실제로는 별 이익이 없네용....

  3. 2016.04.07 04:21

    비밀댓글입니다

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2016.04.07 12:06 신고

      aba가 입력이면 b가 출력돼야 하는데 올려주신 코드에서는 nonchar가 나오게 됩니다. :)

      제 코드에서... 만약 주어진 문자열(str)이 엄청나게 길고 문자의 종류(위에서는 128개로 가정)가 적다면, 문자열은 한 번 읽고 특정 문자열의 등장 여부를 담은 배열(ch) 값을 한 번 search하는 것으로 바꾸는 식으로 위 코드를 개선할 수 있습니다.

      6년 전에 쓴 글인데 공부에 도움이 되었다니 기쁘네요. 덕분에 저도 다시 한 번 살펴봤습니다.

    • 2016.04.07 13:10

      비밀댓글입니다

  4. 2016.04.07 23:54

    비밀댓글입니다

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2016.04.08 11:30 신고

      음.. aba에 대해서는 올바른 답인 b를 출력하는데, abbe를 넣으면 a가 아닌 e라는 오답을 출력하네요.

  5. 2016.04.08 23:11

    비밀댓글입니다

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2016.04.09 04:20 신고

      이번에는 abcdedcba를 넣으면 e가 나와야 하는데, nonchar가 나옵니다.

      이 문제를 if문으로 처리하는 접근은 좋지 않습니다. 몇 가지 입력에는 유효한 답을 내겠지만, 입력 문자열이 길어지면 반례가 반드시 존재할 수밖에 없습니다. 왜냐하면, 답이 될 수 있는 후보를 다 기억하고 있어야 하는데, 이를 기억하려면 메모리 공간이 최악의 경우 O(n)이 필요하다는 이야기이고, 한두 변수만 추가해서는 해결할 수 없습니다.

      제가 본문에 제시하고 댓글에서 개선한 counting 접근이 유효한 솔루션이라고 생각합니다. (다른 더 나은 방법이 있을지는 모르겠지만...)

  6. 2016.04.09 04:37

    비밀댓글입니다

  7. 코리온 2016.10.11 15:40 신고

    비밀댓글 좀 그러네요 ^^

    좋은 내용 잘 보고갑니다.

이번에는 16진수(hexadecimal)를 10진수로 변환해주는 함수를 보자. 아래 코드와 같이 구현하면 처리가 되는데, 값이 너무 커지면 값이 보장되지 않는다. int는 4bytes이고 32bits이다. 16진수로는 4bytes가 한 문자(0,1, ...., A)의 값을 가지므로 총 8자리의 16진수까지만 (unsigned) int로 변환이 가능하다.
#include <iostream>

using namespace std;

unsigned int htoi(string hex) {
	int len = hex.length();
	unsigned int val = 0;
	
	for (int i = 0; i < len; i++) {
		val <<= 4;
		char tmp1 = hex.at(i);
		int tmp2;
		
		if (tmp1 >= 'A')
			tmp2 = tmp1 - 'A' + 10;
		else
			tmp2 = tmp1 - '0';
		
		val += tmp2;
	}
	
	return val;
}

main() {
	cout << htoi("0") << endl;
	cout << htoi("3") << endl;
	cout << htoi("AB") << endl;
	cout << htoi("A3") << endl;
	cout << htoi("11") << endl;
	cout << htoi("AB13") << endl;
}
뭔가 좀 더 깔끔하게는 할 수 없을까? 또한, 16진수의 음수 표현은 어떻게 되는가?
주어진 integer array에서 두번째로 작은 수(second smallest)를 구하여 보자. 일단 n개의 원소를 가진 정렬되지 않은 배열에서 가장 작은 값을 찾기 위해서는 n개 모두를 한 번은 살펴보아야 한다. O(n). 단순 무식한 방법으로 n개를 모두 살펴보면서 가장 큰 수를 찾아 제거하고, 다시 한 번 n-1를 찾아서 가장 큰 수를 출력하면 된다. 전체를 정렬하고 찾으려면 O(nlgn)이 들기 때문에 오히려 더 비효율적이다. (comparison based sort - 비교 기반 정렬)

배열의 원소가 적어도 2개 이상이라는 전제 하에, 아래 소스는 모든 원소를 두 번 읽지는 않고 한 번만 읽고 두번째로 작은 원소를 출력한다. 다만, 두번째로 작은 수가 아니라 임의의 i번째의 경우 이 방법은 사용할 수 없다. 이럴 경우에는 randomized selection을 써야 O(n)에 가능하다.
#include <iostream>

using namespace std;

main() {
	int a[] = {3, 1, 10, 34, 5, 3};
	int len = sizeof(a)/sizeof(int);
	
	for (int i = 1; i < len; i++) {
		if (a[i] <= a[0]) {
			a[1] = a[0];
			a[0] = a[i];
		} else if (a[i] < a[1]) {
			a[1] = a[i];
		}
	}
	
	cout << a[1] << endl;
}
그런데, 뭔가 더 좋은 방법이 있지 않을까?
  1. Favicon of http://zzun.net BlogIcon zzun 2010.02.19 16:03 신고

    이거 i=2 부터 아니고 i=1 부터 해야하지 않나?; {2, 1, 100, 100, 100} 일때 1이 출력될 것 같은데..

  2. Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2010.02.19 16:56 신고

    그러게, 너무 index 하나라도 줄이려는 생각이 앞서다보니 헛짓거리를 했네. Thanks.

C++
대략 학부 1~2학년 시절에 고민했어야할 이야기인 것 같다만, 간단한 프로그램을 짜다가 문제에 봉착했다. 결과값으로 29945를 기대했지만, 실제로 값은 29944가 나왔다. 실수값 연산은 가끔 이런 일이 일어난다.

double v = 299.45;
cout << (int)(v*100.0) << endl;

0.05 단위의 값들(299.40, 299.45 등등)을 처리하다보니 제대로 값이 나오는 것도 있고, 안 나오는 것도 있다. 결국 이래저래 찾아본 결과 아래와 같은 해결책을 제시한다.

cout << (int)(v*100.0+0.5) << endl;

대략 값이 곱셈 후  29944.99999999...가 되어 int로 casting을 하면 버림 처리되어 29944가 된다. 이를 보정해주기 위해 0.5를 더한 후 casting 해준다. 다른 코드들을 보면 0.1을 더한 것도 있고 마음대로인 듯 하다. 문제는, 어떤 c++ 컴파일러에서는 그냥 29945로 나온다는 사실이다. 저렇게 처리를 해주면 문제가 될 것은 없겠다만 뭔가 개운치 못하다.

+ Recent posts