본문 바로가기

[아는게 힘이다]/[프로그래밍]

연결 리스트(Linked List) 부분 뒤집기(reverse) 주어진 연결 리스트에서 일부분을 뒤집는 문제를 생각해보자. 연결 리스트에 [1, 2, 3, 4, 5]라는 값이 들어있고 2번째부터 4번째 사이를 뒤집는다고 하면, [1, 4, 3, 2, 5]가 된다. 연결 리스트 전체 뒤집기 문제보다 조금 더 생각할 거리가 있다. 전체 뒤집기와 다른 점은 뒤집기 경계에 있는 노드 정보를 기억해야 한다는 점이다. 뒤집기 부분 바로 직전 노드를 A라고 하고, 뒤집기 부분이 시작되는 노드를 B라고 하자. 그리.. 더보기
부분합(subsum) 문제 관련 정수 배열 N이 주어졌을 때 두 원소의 합이 특정한 값(T)이 되는 것을 찾는 방법에 대해 생각해보자. 예를 들면, N={-3, -5, 2, -2, 1}이고 T=-4라고 하자.모든 경우를 따져보는 방법 - O(N^2)해시 테이블을 사용하여 한 번만 읽으면서 찾는 방법 - O(N) (해시 테이블이 O(1)일 때)배열을 가리키는 2개의 인덱스(혹은 포인터)를 사용하는 방법 - O(N)이 글에서는 3번에 대해서 생각해보자. 먼저 정렬하면 N={-5, -3.. 더보기
그래프 색칠하기 구글 코드 잼 연습 문제를 오랜만에 풀어보았다. 사실 작년 12월 초에 풀다가 잘 안 풀려서 2달 정도 손을 놓았다가 다시 풀었다. 알고 보면 굉장히 간단한 문제인데, 접근을 엉뚱하게 해서 풀이만 복잡해지고 제대로 된 결과를 구할 수 없었다.문제 보기문제를 간단하게 서술해보자. 서로 함께 있으면 문제를 일으키는 쌍에 대한 정보를 준다. 과연 문제가 없이 사람끼리 모이도록 전체 사람들을 두 그룹으로 나누는 것이 가능한가?접근 방법은 다음과 같다. 각 .. 더보기
[C] 몇 가지 코딩 실수 회사에서 간단한 UDP 소켓 프로그래밍을 할 일이 생겼다. 입사 후 1년 8개월 정도 되었는데 기껏해야 데모를 위한 웹 페이지를 만드는 정도였다. 지난달에 안드로이드 앱이 필요해 인터넷을 뒤지며 오랜만에 Java에 손을 적셨고, 이번에 이 프로그램을 짜면서 VC++에 발을 담갔다. 그런데 몇 가지 아주 기초적인 실수로 시간을 허비해서 적어본다. struct data { int a; int b; }; struct data d; char msg[32.. 더보기
[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.. 더보기
[C++] 부분 문자열 검사 (Substring) 문제) 문자열 A가 주어지고, 그것보다 짧은 문자열로 구성된 배열 T가 주어진다. 배열 T에 들어있는 각 문자열이 A의 부분 문자열인지를 검사한다. 물론, C++에서 제공하는 string 클래스의 find 함수를 사용하면 하고 말 것도 없다. 여기에서는 좀 더 효율적이라고 생각되는 방법을 디자인해보는 것이 목표이다.  예를 들어 A가 'apple'이라는 문자열이라고 하자. 이제, T의 임의의 문자열 t가 'appl.. 더보기