Write a program to extract the longest repeated substring in a given string.

주어진 문자열에서 반복되는 가장 긴 문자열을 추출하자. 문자열의 길이를 n이라고 했을 때 가장 무식한 방법은 모든 가능한 문자열을 다 구해서 반복되는 문자열을 찾고 긴 문자열을 출력하면 된다. 비교 대상인 두 문자열의 시작점을 i, j라고하고 문자열의 길이를 k라고 하고, 비교할 수 있고 문자열을 비교하는 것 또한 k만큼 필요하므로 대략 O(n^4)이 나온다. 어쨌든, 좋지 않다.

이 문제에 접근하기 위해서 사용되는 것이 suffix array라는 것이다. 문자열에서의 각 시작점들의 인덱스를 값(element)으로 가지는 배열을 말한다. 말로 써놓으면 이해하기 어렵고 간단하게 예를 들면 'banana'라는 문자열이 있을 때 'banana'는 0번 인덱스부터 시작한 것이고, 'anana'는 1번 인덱스부터 시작한 것이다. 또한 'na'의 경우 4번 인덱스부터 시작한 것이다. 이러한 0, 1, 4 등의 값을 가지는 배열을 suffix array라고 한다.

a[] = {"banana", "anana", "nana", "ana", "na", "a"}

위와 같은 식으로 값을 가리키는 셈인데, 이것을 정렬하면

a[] = {"a", "ana", "anana", "banana", "na", "nana"}

와 같은 꼴이 된다. 이제 앞뒤 문자열만 비교하면 순서대로 몇 개의 문자가 일치하는지 쉽게 구할 수 있다. 이 경우 "ana"와 "anana"에서 3자리 문자열 "ana"가 가장 긴 반복되는 문자열이 된다. 이제 시간 복잡도는 O(n*nlogn)이 된다. n은 문자열 비교에서, nlogn은 정렬에서 온 수치이다.

소스 코드 상에서는 compare 함수에서 *(char**)a 를 사용하는 부분이 까다로왔다. 포인터에 대해서 좀 알게 되었나 싶었더니 여전히 잘 모르는 것 같다. 좀 더 알아봐야겠다. Programming Pearls에서 보고 감탄했는데, 알고랭이 좀 했다하는 애들은 중학생들도 아는 알고리즘이라는 것을 알고 나니 부끄럽다. -_-;


댓글을 달아 주세요

  • broYobi 2010.03.06 21:56  댓글주소  수정/삭제  댓글쓰기

    clever 하네

  • 아로운 2014.08.28 12:18  댓글주소  수정/삭제  댓글쓰기

    블로그를 참고하면서 공부하고 있는 1인입니다.
    좋은 컨텐츠를 제공해 주셔서 감사를 드립니다, 많은 도움이 되고 있어요.
    (char*)대신 *(char**)을 쓰는 이유를 알 수 있을까요?
    실제로 코딩해봤는데 strcmp에서 정렬이 안되더군요.

    • Favicon of https://blog.sbnet21.com BlogIcon 조나단봉 2015.11.18 04:18 신고  댓글주소  수정/삭제

      답변이 너무 늦었지만, 훗날을 위해 답변 달아봅니다.

      buf 배열은 대상 문자열(e.g., banana)을 담고 있고, sa 배열은 대상 문자열의 각 문자를 가리키는 포인터를 담고 있습니다. 예를 들면, sa[2]는 첫번째 "n"의 주소를 갖고 있습니다. 따라서 buf는 char* 타입이고, sa는 char** 타입입니다.

      *(char**)을 살펴보면 일단 (char**)는 const void* 타입을 캐스팅한 것인데, a가 sa의 원소(element)를 가리키는 포인터가 되어야 하므로, sa의 타입인 char**로 캐스팅합니다.

      앞에 있는 *는 역참조(dereferencing)를 하기 위한 것인데, 우리가 비교하려는 대상은 sa 배열의 값 자체가 아니라 그것이 참조하고 있는 문자열 자체이므로 *를 사용해서 비교되는 대상이 buf 배열에 있는 문자열의 일부가 되도록 하기 위해서입니다.

      비교 대상은 sa의 각 원소가 가리키고 있는 문자열인데, 정렬되어야 하는 값은 sa의 각 원소입니다.

  • Favicon of https://hexists.tistory.com BlogIcon hexists 2014.12.03 17:16 신고  댓글주소  수정/삭제  댓글쓰기

    정리해주신 글 보고 잘 이해했습니다. 감사합니다.

  • 2015.10.16 12:20  댓글주소  수정/삭제  댓글쓰기

    문자열 끊는 법을 몰랐는데, 이 글로 알게되었네요 감사합니다.

  • 공부 2017.08.21 00:56  댓글주소  수정/삭제  댓글쓰기

    공부중인 학생인데요, O(n*nlogn)이 아니라, O(nlogn+n) 아닌가여?
    따로 도니까...

    • Favicon of https://blog.sbnet21.com BlogIcon 조나단봉 2017.08.21 03:37 신고  댓글주소  수정/삭제

      본문에서 '문자열 비교에서 n'이라고 한 것은 sorting 내에서 2개의 문자열 간 비교를 말한 것입니다. sorting 후 인접 문자열 간의 비교가 아닙니다. 본문 문장에 오해의 소지가 조금 있었을 수도 있겠는데, 원래 의도는 이렇습니다.

      보통 sorting의 예에서는 element 개수가 dominant하고 각 element간의 비교는 O(1)입니다. (e.g., 문자열의 길이가 상수) 그런데 이 문제에서는 element 개수가 문자열의 길이와 같기 때문에 아래와 같이 계산해야 합니다.

      element 개수를 n이라 할 때 우리가 사용한 sorting에서 비교 횟수는 O(nlogn)라고 합시다.

      이 문제에서는 두 element를 비교하는 compare 함수도 O(n)가 됩니다.

      따라서 이 sorting에서 문자(char) 비교 횟수는 총 O(n*nlogn)이 됩니다.

      감사합니다.

1에서 10,000까지 정수 중에서 무작위 100개를 뽑아내어 출력하자. 

수학 문제 같은 접근이 맘에 들지 않는다면 실용적인 예로 바꿔 보자. 

음악 사이트에서 10,000개의 곡이 존재하는데 랜덤하게 100개의 곡을 뽑아 랜덤 듣기 서비스를 제공한다고 해보자. 물론 각 곡은 고유 인덱스를 가지며 반드시 1에서 10,000까지만의 연속된 정수라고 할 수도 없다. 예를 들면 34,483번 등의 곡도 존재할 수 있다. 어떻게 할 것인가? 

실제로 예전에 회사에 다닐 때 마주친 문제이다. 당시 회사에서는 음악 사이트 리뉴얼 중이었고, 랜덤 재생 버튼을 누르면 엄청나게 오랜 시간을 잡아 먹는 현상이 있었다. 코드를 보지는 않았지만, 모회사의 개발자 구하기 글의 첫번째 함수 비슷하게 구현하지 않았었을까 생각된다. 당시 이 소스를 작업하던 분이 배열 섞는데 시간이 너무 오래 걸린다고 좋은 방법을 알아봐 달라고 해서 배열을 섞는 함수를 찾아서 알려줬던 기억이 난다.[각주:1] 어쨌든, 이 문제를 접했을 때 이러한 접근이 당연했고 가장 적합한 처리 방법이었다.

요즘 테크니컬 면접을 준비하고, 알고리즘 수업도 듣다보니까 문제를 바라보는 관점이 조금 Y군처럼 바뀌었다. 이 문제를 접하자마자 어떻게 풀까 고민을 시작했고, 방법을 알아내었다.[각주:2] 이후 이 문제가 나왔던 위의 모회사의 개발자 구하기 글을 마져 읽어 내려가다 충격을 먹었다. 당연히 이렇게 푸는 설명이 있을 줄 알았는데, PHP상에서 배열을 섞어주는 shuffle 함수를 사용하는 것이 정답(?)으로 나와 있어서였다.

그냥, 책 제목으로 있는 '생각하는 프로그래머'와 '실용주의[각주:3] 프로그래머'라는 말이 떠올랐다. 흔히 학교에 있으면 '생각하는 프로그래머'가 되려고 노력하고, 회사에 있으면 '실용주의 프로그래머'가 되야할 것만 같다. 물론, 둘 다 잘해야 하지만 이 예를 보면 조금 아이러니한 느낌이 든다. 이상한 생각인가? ㅎㅎ 

뭔가 글을 잘 쓰지 못하는 게 티가 팍팍 나는
포스팅이다
포스팅이다. 
뭐, 결론은 한 가지 문제에 대한 두가지 접근 방식이 존재한다는 말이다. ^^;
  1. 시간은 기억은 미화시킨다. 과정이 정확하지는 않을 수 있다. [본문으로]
  2. 배열에 대상이 되는 수(1~10000)을 넣고, 랜덤 함수로 0~1 사이의 실수 값을 구해서 10000을 곱하여 나온 값을 index하는 값을 추출한다. 배열의 마지막 인자(e.g, 10000)를 그 index 값에 넣고 이제 다음 랜덤값에는 9999를 곱한다. 이런식으로... [본문으로]
  3. 책의 실제 내용과 관계없이 '실용주의'라는 단어의 의미만 가져다 썼음. [본문으로]

댓글을 달아 주세요

테크니컬 면접 문제의 단골인 연결 리스트(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 함수를 구현할 때에도 잘못 생각하면 무한 루프에 빠지게 되는데 주의해야 한다. 이전 노드, 현재 노드, 다음 노드를 테이블로 그려보고 적절히 값이 어떻게 바뀌어야 할지 생각해보면 할 수 있다.

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

댓글을 달아 주세요

  • broYobi 2010.03.01 23:12  댓글주소  수정/삭제  댓글쓰기

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

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

    • Favicon of https://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] 좀 이상하네. 어떻게 하면 되겠노?

  • 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 https://blog.sbnet21.com BlogIcon 조나단봉 2010.03.04 17:50 신고  댓글주소  수정/삭제

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

  • 서여빈 2011.07.19 10:43  댓글주소  수정/삭제  댓글쓰기

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

    • Favicon of https://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학년으로 돌아가면 즐겁게 다시 공부할 수 있을 것 같다. ㅎㅎ

댓글을 달아 주세요

이번 문제에서는 32bits 정수 n과 m이 주어지고 n의 인덱스 i, j가 주어진다. n의 i번째에서 j번째 사이의 bit들을 m의 bit들로 바꾸는 것이다. 예를 들어 n=11010이고 m=11인데, i=2이고 j=3이면 1[11]10이 된다. 물론 인덱스는 0에서 부터 시작하고 2^0을 나타내는 bit 위치가 index=0이다. (이런게 least significant bit인가?) 참고로 j>=i이다.

대략 알고렝이(알고리즘)를 보면 (a) n에서 m이 들어갈 위치를 0으로 만들어주고 (1[00]10), (b) m을 해당 위치만큼 좌측으로 shift해주고 ([11]00), 두 값을 or 연산 해주면 된다. 전자 (a)의 경우는 0이 되어야 할 자리에 1만 있는 값 ([11]00)을 만들고, 이를 모든 binary값으로 모든 자리가 1인 (~0) 값과 xor 연산을 해주고 (111~~11[00]11), 이를 다시 n 값과 and 연산을 하면 원하는 값이 나온다. (1[00]10).
#include <iostream>

using namespace std;

int insertMiddle(int n, int m, int i, int j) {
	int n1 = (((1 << (j - i + 1)) - 1) << i);
	int n2 = (n & (~0 ^ n1));
	int n3 = n2 | (m << i);
	
	return n3;	
}

int main() {
	cout << insertMiddle(26, 3, 2, 3) << endl;
	cout << insertMiddle(1024, 21, 2, 6) << endl;
}
원리도 간단하고 소스도 간단한데, 원리를 파악하고도 단지 이 3줄의 핵심 코드를 짜는데 (물론 한 줄로도 되겠지만) 1시간이 넘게 걸렸다. 예제 binary 값을 십진수로 바꿔서 함수의 인자로 넣는데 그 십진수를 잘못 계산해서 삽질하는 등등. 이 정도는 5분이면 짜내야 하는 것 아닌가 싶은데 정말 머리에 방법이 떠오르더라도 그걸 코드 한 줄로 옮기는 데 오류가 너무 많다.

정말 이런 쪽으로 머리가 나쁜 것 같단 생각이 든다. 예전부터 recursion이 머리로 이해가 안되고, dynamic programming이 이해가 안되던게 이런 쪽으로 머리가 너무너무 나빠서 그런가보다. 뭐, 다른 분야에 재능이 있을지도 모르겠지만, 내가 잘 해야하는/했으면 부분에서 이렇게 고생하며 자학(?)하게 되니 참 난감하다.

댓글을 달아 주세요

이번에는 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;
}

댓글을 달아 주세요

  • Favicon of http://zzun.net BlogIcon zzun 2010.02.19 16:25  댓글주소  수정/삭제  댓글쓰기

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

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

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

    • Favicon of https://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으로는 안될 것 같고.

      잘 모르겠다.

  • broYobi 2010.02.22 18:03  댓글주소  수정/삭제  댓글쓰기

    이론적인 것만 고려한다면

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

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

  • 2016.04.07 04:21  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

    • Favicon of https://blog.sbnet21.com BlogIcon 조나단봉 2016.04.07 12:06 신고  댓글주소  수정/삭제

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

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

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

    • 2016.04.07 13:10  댓글주소  수정/삭제

      비밀댓글입니다

  • 2016.04.07 23:54  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  • 2016.04.08 23:11  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

    • Favicon of https://blog.sbnet21.com BlogIcon 조나단봉 2016.04.09 04:20 신고  댓글주소  수정/삭제

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

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

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

  • 2016.04.09 04:37  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  • 코리온 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~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로 나온다는 사실이다. 저렇게 처리를 해주면 문제가 될 것은 없겠다만 뭔가 개운치 못하다.
Tag C++

댓글을 달아 주세요