태터데스크 관리자

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

태터데스크 메시지

저장하였습니다.

주어진 연결 리스트에서 일부분을 뒤집는 문제를 생각해보자. 연결 리스트에 [1, 2, 3, 4, 5]라는 값이 들어있고 2번째부터 4번째 사이를 뒤집는다고 하면, [1, 4, 3, 2, 5]가 된다. 연결 리스트 전체 뒤집기 문제보다 조금 더 생각할 거리가 있다.

전체 뒤집기와 다른 점은 뒤집기 경계에 있는 노드 정보를 기억해야 한다는 점이다. 뒤집기 부분 바로 직전 노드를 A라고 하고, 뒤집기 부분이 시작되는 노드를 B라고 하자. 그리고 뒤집기 부분이 끝나는 노드를 C라고 하자. 그러면 다음과 같이 처리해야 한다. 물론, 뒤집기 부분을 뒤집는 방법은 연결 리스트 전체 뒤집기와 같은 방법으로 처리해야 한다.

A.next = C
B.next = C.next

[1, 2, 3, 4, 5]의 예로 돌아가 보자. 뒤집기 부분은 [2, 3, 4]이다.  현재 노드가 가리키는 다음 노드가 현재 노드를 가리켰던 이전 노드가 되도록 하면 된다. (1) A노드는 1이므로 C노드인 4를 가리켜야 한다. (2) B노드는 2이므로 C노드의 next 노드인 5를 가리켜야 한다.

Before: 1[A] -> 2[B] -> 3 -> 4[C] -> 5
After: 1[A] -> 4[C] -> 3 -> 2[B] -> 5

개념은 위와 같다. 한 가지 주의해야 할 점은 뒤집기 부분이 첫 노드부터면 A노드가 실제로 존재하지 않고 head가 직접 C를 가리키게 해야 한다. 따라서 head가 C를 직접 가리키거나 A.next가 C가 되게 해야 한다. 이때 인자로 넘어온 head 값을 변경하기 위해서 포인터의 포인터를 사용해야 한다.

void reverseBetween(ListNode** head, int m, int n) {
	ListNode* cur = *head, *prev = *head, *start = NULL, **end = head;

	for (int i = 1; i < m; i++) {
		end = (ListNode**)&(cur->next);
		prev = cur;
		cur = cur->next;
	}
	start = cur;

	for (int i = m; i <= n; i++) {
		ListNode* nextnode = cur->next;
		cur->next = prev;
		prev = cur;
		cur = nextnode;		
	}
	start->next = cur;
	*end = prev;
}

풀기도 쉽지 않았는데, 설명하기는 더 어렵다.

정수 배열 N이 주어졌을 때 두 원소의 합이 특정한 값(T)이 되는 것을 찾는 방법에 대해 생각해보자. 예를 들면, N={-3, -5, 2, -2, 1}이고 T=-4라고 하자.

  1. 모든 경우를 따져보는 방법 - O(N^2)
  2. 해시 테이블을 사용하여 한 번만 읽으면서 찾는 방법 - O(N) (해시 테이블이 O(1)일 때)
  3. 배열을 가리키는 2개의 인덱스(혹은 포인터)를 사용하는 방법 - O(N)

이 글에서는 3번에 대해서 생각해보자. 먼저 정렬하면 N={-5, -3, -2, 1, 2}가 된다. 두 개의 인덱스(low, high)를 사용한다. low는 첫 번째 원소, high는 마지막 원소를 가리키는 인덱스를 저장한다. 각 인덱스가 가리키는 원소의 합(S)을 구해본다. 목푯값인 T와 비교하여 T<S이면 high 값을 감소시킨다. 원소의 합이 목표치보다 크기 때문에 합(S)을 줄여야 하기 때문이다. 마찬가지로, T>S이면 low 값을 증가시킨다. 원소의 합이 목표치보다 작으므로 합(S)을 키워야 하기 때문이다. 이러한 과정을 low<high를 만족하게 하는 동안 수행한다.

위의 예로 값을 구하는 과정을 살펴보면 아래와 같다.

N[low] N[high] S   
----------------------------------
-5     2       -3  (T<S, high--)
-5     1       -4  (T=S)

조금 더 문제를 확장해서 두 원소의 합이 T에 가장 가까운 경우를 찾는다고 해보자. 이 경우에도 비슷한 방식으로 하는데, S와 T의 차의 절댓값이 최소가 되는 정보를 유지해야 한다. 절댓값이라는 개념이 들어가는데도 위와 같은 식으로 하는 게 처음에는 잘 이해가 안 되는데 결국 S가 T에 가까워지는 방향으로 가려면 T>S일 떄는 low++, T<S일 때는 high--을 해야 한다.

구글 코드 잼 연습 문제를 오랜만에 풀어보았다. 사실 작년 12월 초에 풀다가 잘 안 풀려서 2달 정도 손을 놓았다가 다시 풀었다. 알고 보면 굉장히 간단한 문제인데, 접근을 엉뚱하게 해서 풀이만 복잡해지고 제대로 된 결과를 구할 수 없었다.

문제를 간단하게 서술해보자. 서로 함께 있으면 문제를 일으키는 쌍에 대한 정보를 준다. 과연 문제가 없이 사람끼리 모이도록 전체 사람들을 두 그룹으로 나누는 것이 가능한가?

접근 방법은 다음과 같다. 각 사람을 vertex로 하고, 서로 문제를 일으키는 사람 간에 edge가 존재하는 그래프를 생각한다. 그리고 각 vertex를 둘 중 하나의 색으로 칠하는데, edge로 이어진 두 vertex는 서로 다른 색이어야 한다.

처음에는 모든 vertex에 색이 없다. 칠해지지 않은 한 vertex를 선택하고, 그 vertex를 시작으로 BFS를 통해 연결된 vertex를 조사한다. 이때 이 vertex는 1) 색이 없는 상태 2) 연결될 수 없는 같은 색이 있는 상태 3) 연결될 수 있는 다른 색이 있는 상태 중 하나이다. 1)의 경우에는 다른 색을 칠하고 그것과 연결된 vertex들을 조사하게 한다. 2)의 경우 두 그룹으로 나눌 수 없다는 결론을 낸다. 3)의 경우 이 vertex에 대한 조사는 중단한다. (이미 이것과 연결된 vertex에 대한 조사는 끝났기 때문) 

BFS 과정에서 찾아지는 vertex가 없으면, 칠해지지 않고 남아 있는 vertex로 앞의 작업을 반복한다. 문제없이 모든 vertex를 칠할 수 있으면 두 그룹으로 나눌 수 있다.


회사에서 간단한 UDP 소켓 프로그래밍을 할 일이 생겼다. 입사 후 1년 8개월 정도 되었는데 기껏해야 데모를 위한 웹 페이지를 만드는 정도였다. 지난달에 안드로이드 앱이 필요해 인터넷을 뒤지며 오랜만에 Java에 손을 적셨고, 이번에 이 프로그램을 짜면서 VC++에 발을 담갔다. 그런데 몇 가지 아주 기초적인 실수로 시간을 허비해서 적어본다.

struct data {
	int a;
	int b;
};
struct data d;
char msg[32];	// buffer

//////////////////////////////////////////////////////
// ... (this part is omitted) ...
// receive data from the network to the msg variable
//////////////////////////////////////////////////////

strcpy(&d, message);

네트워크로 받은 값이 d에 제대로 복사되지 않는다.[각주:1] strcpy는 한 byte씩 복사하다가 값이 0이면 문자열의 끝이라고 생각하고 더는 값을 복사하지 않는다. 물론, strncpy를 해도 같다. 따라서 아래와 같이 memcpy를 이용해야 한다.

memcpy(&d, message, sizeof(d));

기초적인 내용인데 몇십 분을 헤맸다. 너무 오랜만에 C로 코딩해서 감이 없다.

다음은 샘플 소스에 있던 msg, strlen(msg) 부분을 보고 생각 없이 copy&paste를 해서 발생한 일이다.

send(sock, (char*)&d, strlen((char*)&d), 0);

위와 같이 하면 8bytes를 보내는 것이 아니라 d를 문자열로 봐서 8bytes 미만이 될 수도 있다. 내 경우엔 1byte가 됐다. 결국, 첫 번째 오류와 같다.

send(sock, (char*)&d, sizeof(d), 0);

이걸로 서버 프로그램이 잘못된 것이 아니냐며 관계자를 불렀다. '나는 프로그래머다'서 누가 말했듯, 자신에게 잘못이 없는지 생각하기보다 다른 사람이 잘못했을 것이라고 믿어버린 경우다. 나의 사소한 실수에 스스로 오그라들고 말았다.

프로그래밍도 감각을 잃으면 정말 사소한 곳에서 오류를 만들고 시간을 허비하게 된다. 틈틈이 프로그래밍을 게을리 말아야 겠다.

  1. 운이 좋아 d 내부의 a, b 값이 아주 크다면 제대로 값이 복사될 수도 있겠다. [본문으로]

'[아는게 힘이다] > [프로그래밍]' 카테고리의 다른 글

부분합(subsum) 문제 관련  (0) 2016.02.25
그래프 색칠하기  (0) 2016.02.15
[C] 몇 가지 코딩 실수  (2) 2012.05.14
[C++/ACM] 820 Internet Bandwidth  (0) 2010.05.16
[알고리즘] Interval Scheduling  (2) 2010.04.29
  1. broYobi 2012.05.15 23:29 신고

    난 오히려반대 였다
    이틀동안 서버쪽 모듈에내가잘못한거나 간과한거없는지 찾다가 결국 L7이 문제연다는거ㅋ
    그나저나 난요즘c가하고싶은데 그럴일이없네


예전에는 손도 못대던 문제가 그래프 관련 문제였다. 하지만, 의외로 많은 문제들을 그래프로 풀 수 있고 재미있는 문제들도 많다. 그래서 요새는 어떤 문제가 주어지면 혹시나
그래프로
그래프로 풀 수 있는게 아닌가부터 생각한다. 이번 문제는 문제만 읽어봐도 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번을 적용하도 않아도 되는 것이 맞는지, 아니면 우연히 맞은 것인지는 좀 더 생각해 봐야 한다.

소스 열기

알고리즘 수업을 들으면 Greedy 알고리즘의 첫 번째 예로 살펴보는 것이 바로 이 interval scheduling 문제이다. 작업 목록과 각 작업을 수행할 수 있는 시간 구간이 주어진다. 그리고 최대 몇 가지 작업을 할 수 있는지를 알아내는 문제이다. 실제로 선택되는 작업들이 유일하지 않을 수도 있다. 쉬운 예를 들어보자.
  
T1: 1시-3시 청소
T2: 2시-4시 숙제
T3: 3시-5시 낮잠
T4: 4시-8시 운동
T5: 7시-9시 TV시청
T6: 8시-9시 옆집가기

위의 각각의 작업은 주어진 시간을 꽉 채워 사용해야하고 그 때에만 가능하다고 하자. 최대 다양한 작업을 하기 위해서는 1시-3시에는 청소(T1), 3시-5시에는 낮잠(T3)을 자고, 7시-9시에 TV를 보면(T5) 된다. 다른 방법(T2, T4, T6)도 하나 있지만 어쨌든, 최대 3가지 작업을 할 수 있다. 작업이 몇 개 안되면 대충 눈으로 비교해보면 쉽게 알 수 있지만 일이 100가지, 1000가지가 된다고 해보자. 쉽게 풀 수 없다. 

물론 컴퓨터를 이용하면 사람보다는 좀 더 빠르게 풀 수 있을 것이다. 일단, 무식하게 생각해서 각 작업이 결과에 포함하거나 않거나 하면 되고, 모든 경우의 수 중에서 시간이 중복되는 작업이 없는 경우의 목록의 개수가 가장 큰 경우를 찾으면 된다. 작업의 종류가 n가지라면 최대 2n가지 종류가 나온다. 대략 n=100만 되어도, log2100=30.1이므로 1030이 넘는 경우의 수가 나온다. 좀 많다. 좀 더 효과적인 방법을 고안해 내는 게 알고리즘을 연구 혹은 공부하는 사람들이 밥 먹고 하는 일이다. 그 사람들이 무엇을 발견(?)했는지 살펴보자.

일단, 가장 먼저 끝날 수 있는 작업을 선택한다. 이제 그 작업이 끝나는 시간 이후에 시작할 수 있는 작업들 중에서 가장 먼저 끝날 수 있는 작업을 택한다. 또 다시, 그 작업이 끝나는 시간 이후에 시작되는 작업 중에서 가장 빨리 끝날 수 있는 일을 택한다. 이런 식으로 택하다보면 가장 많은 작업을 택할 수 있게 된다. 프로그래밍을 하자면, 현재 시점에서 가장 빨리 끝날 수 있는 작업을 찾기 위해서는 현재 시점에서 실행 가능한 작업 목록에서 작업 시작 시간을 기준으로 정렬을 먼저 한 후 찾으면 효율적이다. 

Greedy 알고리즘은 현재 시점에서 최선의 선택을 한 것이 결과적으로 문제 전체의 최선의 선택이 된다는 것이다. 그 때 그때 Local optimal을 선택하면 결국 global optimal을 찾을 수 있다는 말이다.

다음 문제는 위 문제보다 조금 더 복잡해 보이는 문제이다. 각 작업에 가중치(weight)를 줘보자. 경제학 용어를 쓰자면 효용이라고 하면 되려나?

T1: 1시-3시 청소 - 10
T2: 2시-4시 숙제 - 50
T3: 3시-5시 낮잠 - 20
T4: 4시-8시 운동 - 20
T5: 7시-9시 TV시청 - 10
T6: 8시-9시 옆집가기 - 10

효용가치가 높은 작업 해야 하는 것이 당연하고, 주어진 시간 내에 최대 효용을 얻는 행동을 하는 것이 경제적인 인간이 마땅히 해야 할 일이다. 따라서 위 문제는 최대 효용을 얻기 위하여 어떠한 작업들을 해야 하는지에 대한 문제가 된다. 앞의 문제는 이 문제에서 모든 작업의 효용이 같다고 전제하면 동일한 문제가 된다. 그렇다면, 이 문제를 앞과 동일한 방법으로 풀 수 있을까? 안 된다. 일단 앞의 풀이처럼 T1, T3, T5를 선택하면 효용이 총 10+20+10=40이지만, T2, T4, T6을 선택하기만 해도 효용이 총 50+20+10=80이 된다. 후자를 택하는 것이 더 효율적이지만 앞의 알고리즘은 전자를 택하므로 항상 옳은 결과를 가져온다고 볼 수 없다. 

또 알고리즘을 연구하신 분들의 도움을 받자. 이번에는 greedy 알고리즘이 아니라, 또 하나의 유명한 문제 해결 기법인 dynamic programming (동적 프로그래밍)을 사용해보자. 이번에는 끝나는 시간으로 오름차순 정렬을 한다. 이 작업들을 각각 T[i]라고 하자. v[i]를 첫 번째 작업에서 부터 i번째 작업까지를 고려할 때 얻을 수 있는 최대 효용이라고 해보자. i번째 작업의 효용은 w[i]라고 하자. 

일단, v[1]은 w[1]이 된다. 이제 v[1]에서 v[i-1]이 올바른 값을 가지고 있다고 가정하자. 이제 v[i] 값은 어떤 값이 될지 생각해보자. v[i]는 (1) i번째 작업이 시작하는 시간보다 해당 작업의 끝나는 시간이 더 빠른 작업까지를 고려했을 때의 최대 효용에 w[i]를 더한 값과, (2) 그냥 i-1번째 작업까지를 고려했을 때의 최대 효용 중에 큰 값을 갖게 된다. 

왜 그렇게 될까? (1)을 살펴보자. i번째 작업의 효용 w[i]를 포함시키기 위해서는 i번째 작업과 이전의 어떤 작업도 중복되어서는 안 된다. i<j인 경우 v[i]<=v[j]가 늘 성립하므로, 그러한 값 중에 가장 큰 작업을 찾아 w[i]를 더하면 i번째 작업을 포함하는 최대의 효용이 나온다. (2)의 경우 i를 포함하지 않는 경우를 생각하는 것이다. 그렇다면 최대 효용은 i-1번째 작업까지를 고려한 경우가 된다. w[i]를 더하기 전의 (1)과 (2)는 같을 수도 있다. i를 첫 번째 작업부터 마지막 작업까지 구하면, v[n]이 바로 우리가 원하는 결과가 된다.

알고리즘은
  1. 어떤 알고리즘을 써야하는지 알기 어렵고,
  2. 그 알고리즘이 왜 옳은지 알기 어렵고,
  3. 새로운 알고리즘을 만드는 것은 더 어렵다.
남에게 설명하지 못하는 것은 이해하지 못한 것과 같다.
설명을 하려고 노력하면, 그만큼 나의 이해도도 높아지리라 믿는다.
블로그를 그런 용도로 써봐야 겠다. ㅎㅎ
  1. masknecr 2011.08.30 16:24 신고

    interval scheduling problem 설명하신 부분에서 오류가 있는것 같아 글 남깁니다.

    weight가 없을시에 optimal solution은

    가장 먼저 시작할 수 있는 작업이 아니라 '가장 먼저 끝낼 수 있는 작업(earliest f-value)'입니다.. 물론 첫번째 작업을 선택한 이후에는, 첫번째 작업시간과 겹치지 않는 작업들중에서 가장 먼저 끝낼 수 있는 작업을 선택합니다.

    가장 먼저 시작하는 작업이 가장 늦게 끝나는 경우를 생각해보시길..

    • Favicon of http://blog.sbnet21.com BlogIcon 조나단봉 2011.09.01 16:48 신고

      네, 지적 감사합니다. 수정했습니다.

      바로 시작할 수 있는 작업을 하는 것은 optimal solution이 아닌 예였던 것 같은데 잘못 써 놓았네요.

      읽는 분이 계신 만큼 앞으로 더 주의해서 써야겠습니다.^^;

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

지난 번 폰 인터뷰에 나왔던 문제이고, 이전 포스팅인 '배열에서 두번째로 작은 수를 구하기'와 거의 유사하다. 다만, 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)을 사용하는 것도 생각해보자.

더보기


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의 맨 끝단어(s1[n])와 맨 앞단어(s1[0])를 붙여서 이 문자열(t)이 s2에 존재하는 위치를 먼저 구한다. t가 s2에 존재하면 t가 존재하는 위치 뒷부분, s2의 맨 앞에서 t가 존재하는 부분 직전까지의 문자열이 각각 s1에 존재하는지를 적절하게 체크한다. 다만, t가 s2에 존재하지 않는 경우 중에 s1=s2인 경우가 있으니까 주의하여 체크한다. 

 s[0]{ A }{ B }s[n] -> { B }s[n]s[0]{ A }

정답에서 사용한 방법은 s1+s1인 문자열을 만들고, s2가 그 안에 존재(strstr)하면 된다. 간단하다. 결과적으로는 s1을 순환하는 문자열로 생각한다는 점은 비슷했는데 내가 쓴 방법은 아주 지저분하고, 정답은 깔끔하다. 문제는 인터뷰를 할 때 나처럼 푼다면 짧은 시간 내에 오류 없이 소스를 완성 시키지 못할 것이 분명하기 때문에 정답과 같은 접근이 반드시 필요하다. 아흥!

소스보기

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에서 보고 감탄했는데, 알고랭이 좀 했다하는 애들은 중학생들도 아는 알고리즘이라는 것을 알고 나니 부끄럽다. -_-;

소스열기


  1. broYobi 2010.03.06 21:56 신고

    clever 하네

  2. 아로운 2014.08.28 12:18 신고

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

    • Favicon of http://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의 각 원소입니다.

  3. Favicon of http://hexists.tistory.com BlogIcon hexists 2014.12.03 17:16 신고

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

  4. 2015.10.16 12:20 신고

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

  5. 공부 2017.08.21 00:56 신고

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

    • Favicon of http://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. 책의 실제 내용과 관계없이 '실용주의'라는 단어의 의미만 가져다 썼음. [본문으로]
  1. broYobi 2010.03.05 08:17 신고

    자연스레... 실용주의적으로 되던데.. ㅋㅋ
    뭐.. 모든 일은 혼자 다 할 수 없으니껭..ㅋ

테크니컬 면접 문제의 단골인 연결 리스트(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 신고

    늦지 않았다 ㅋㅋ

이번 문제에서는 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이 이해가 안되던게 이런 쪽으로 머리가 너무너무 나빠서 그런가보다. 뭐, 다른 분야에 재능이 있을지도 모르겠지만, 내가 잘 해야하는/했으면 부분에서 이렇게 고생하며 자학(?)하게 되니 참 난감하다.
  1. broYobi 2010.02.22 17:00 신고

    그래도 넌 잘하는 거다.

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