본문 바로가기

C++

[C++/ACM] 820 Internet Bandwidth 문제: http://uva.onlinejudge.org/ external external/8/820.html 예전에는 손도 못대던 문제가 그래프 관련 문제였다. 하지만, 의외로 많은 문제들을 그래프로 풀 수 있고 재미있는 문제들도 많다. 그래서 요새는 어떤 문제가 주어지면 혹시나 그래프로 그래프로 풀 수 있는게 아닌가부터 생각한다. 이번 문제는 문제만 읽어봐도 Maximum flow 문제라는 것을 알고리즘을 공부해본 사람은 누구.. 더보기
[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.. 더보기
[C++] 전화 번호 문자열 변환 (Telephone Words) 문제) 전화기의 몇몇 번호에는 알파벳이 할당되어 있다. 전화 번호가 주어지면 가능한 알파벳 조합을 모두 출력하라. 단, 0, 1번에는 알파벳이 할당되어 있지 않고, 2~8번에 각 3개씩 알파벳이 할당되어 있다고 하자. 단 Q, Z는 할당되어 있지 않다. 일종의 순열 출력 문제라고 할 수 있다. 예를 들어 번호가 123번이면 1AD, 1AE, 1AF, 1BD, 1BE, 1BF, 1CD, 1CE, 1CF와 같이 9가지가 나온다. 기본적으로 재귀(rec.. 더보기
[CS] 연결 리스트 뒤집기 (Reverse Linked List) 테크니컬 면접 문제의 단골인 연결 리스트(Linked List). 그 중에서도 가장 많이 나온다는 뒤집기 문제이다.  기본적인 연결 리스트를 구현 할 줄 알아야 겠다. C/C++을 이용한다고 할 때, struct 혹은 class로 먼저 node를 정의한다. 필요한 기본 함수로는 insert, delete, print( traverse traverse) 정도가 되겠다. delete는 뒤집기에는 필요하지 않으므로 생략한다.&nbs.. 더보기
[CS] 퀵 정렬 (Quick Sort) 학부 1학년 때 컴퓨터 개론 시간에 C를 배웠던 것 같다. 당시 전혀 학과 공부를 신경쓰지 않던 나는 수업을 통해 배우는 게 별로 없었다. 아직도 C조차 제대로 모르는 이유는 여기에서 기인한다. 어쨌든, 그 때 마지막 과제던가? 퀵 정렬을 C로 짜오라는 과제가 있었던 것 같다. 당시에 퀵 정렬이라하면 최고 수준의 프로그래밍 실력이 있어야 할 수 있다고 생각했다. 마치, 1학년 당시 '학점이 3.0을 넘는 사람은 인간이 아니다'라고 믿었던 것처럼 어.. 더보기
[CS] 반복되지 않는 첫번째 문자를 찾아라 이번에는 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.. 더보기
[CS] 16진수를 10진수로 바꾸어보자 이번에는 16진수(hexadecimal)를 10진수로 변환해주는 함수를 보자. 아래 코드와 같이 구현하면 처리가 되는데, 값이 너무 커지면 값이 보장되지 않는다. int는 4bytes이고 32bits이다. 16진수로는 4bytes가 한 문자(0,1, ...., A)의 값을 가지므로 총 8자리의 16진수까지만 (unsigned) int로 변환이 가능하다. #include <iostream> using namespace std; unsig.. 더보기