2013/08/13 12:43

선풍기 사망설은 그저 괴담일 뿐인가? 성큼칼럼

선풍기 틀어놓고 자다가 죽는다는 이야기는 그저 미신일 뿐이라는 이야기가 참 많이 돌고 있습니다만, 위험성은 분명 존재합니다.
미 환경보호국에서 이상고온현상시의 각종 지침들을 발표한 자료가 있는데 선풍기를 언급한 부분을 번역해보았습니다.

한줄 요약하자면 방안 온도가 체온보다 높을 때에는 선풍기를 쓰는 것이 위험하다는 겁니다.

이어지는 내용

2012/09/13 15:37

코딩 인터뷰 완전 분석 215쪽 문제 18.10 풀이

  <- 이 책에 나오는 문제라고 합니다.

문제 출처는 다음 링크입니다.
http://www.insightbook.co.kr/post/3917 

『코딩 인터뷰 완전 분석』215쪽 고난이도 연습문제 18.10

사전에 등장하고 길이가 같은 두 단어가 주어졌을 때, 한 번에 글자 하나만 바꾸어 한 단어를 다른 단어로 변환하는 프로그램을 작성하라. 변환 과정에서 만들어지는 각 단어도 사전에 있는 단어여야 한다.

[실행 예]

input : DAMP, LIKE
output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

[사전 데이터]

네 글자 단어 - word4

다섯 글자 단어 - word5

 

[심화 문제 - 풀지 않아도 됩니다]

심화문제 1: 가장 적은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다.
심화문제 2: 가장 많은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다. 단, 변환 과정에서 같은 단어가 두 번 나오면 안됩니다.

 이 문제는 사전상의 각 단어를 노드, 변환가능한 단어쌍을 링크로 놓으면 그래프에서의 경로찾기 문제로 치환할 수 있습니다.  

여기서는 A* 알고리즘을 써서 구현했습니다. A*알고리즘에서는 현재 위치가 목표와 얼마나 가까운지 예측하는 게 필요한데, 글자 하나 다를 때 한 번만에 옮겨갈 수 있다고 보수적인 추정을 사용하면 시간을 약간 더 걸리지만 최소 경로를 찾아낼 수 있습니다. 

최대 경로, 즉 가장 많은 수의 단어를 쓰는 경우는 변환을 한 번 할 때 weight을 -1로 둬서 가장 많은 변환을 하도록 해 주면 찾을 수 있습니다. 

 실행결과:

(damp -> like):(5)[damp, dame, dime, dike, like]

(start -> final):(13)[start, stare, stave, seave, serve, serie, ferie, ferae, feral, fetal, fatal, fanal, final]

(china -> japan):(15)[china, chine, shine, seine, seise, sense, mense, manse, manie, matie, matin, satin, satan, sapan, japan]

(damp -> like):(2734)[]  <-- 결과는 longest.txt 에 올려놨습니다.

찾아보니 다른 분이 더 긴 longest 결과를 찾으셨네요 ^^; 제 건 부정확한 듯. 좀 더 고쳐보겠습니다. 


코드는 다음과 같습니다.

2012/09/05 19:17

코딩 인터뷰 완전 분석 210쪽 17.3 변형 문제 풀이

출처는 여기

문제

『코딩 인터뷰 완전 분석』210쪽 17.3 변형 문제

자연수 n을 입력받고, n!의 계산 결과 중 마지막에 붙은 연속된 0의 개수와 연속된 0 바로 앞에 나오는 숫자를 구하라.

[실행 예]

input n: 15
output: 3 8

[설명]

15!은 1307674368000이므로, 마지막에 연속된 0은 3개이고, 바로 앞의 숫자는 8이다.

* 조건 *

  1. n의 범위는 1 이상, 10000 이하입니다.
  2. 테스트 입력은 다음과 같습니다.
    20! = 2432902008176640000
    30! = 265252859812191058636308480000000
    40! = 815915283247897734345611269596115894272000000000
    50! = 30414093201713378043612608166064768844377641568960512000000000000
    100! = 93326215443944152681699238856266700490715968264381621468592963
    8952175999932299156089414639761565182862536979208272237582511852
    10916864000000000000000000000000
  3. 프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다.
  4.  정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요.
  5. (심화 문제) 연속된 0 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^
제가 보기엔 이 문제가 저번 문제보다는 훨씬 쉬워 보이네요 ㅎㅎ 출력이 단순하니 과정도 단순? ㅋㅋ

여러 숫자를 구할 수 있는 버전으로 작성했고, 정수 배열을 리턴하는 함수로 만들었습니다. 
배열의 첫번째 숫자가 0의 개수이고, 나머지는 0앞에 나오는 숫자들을 낮은 자리부터 차례로 붙여넣었습니다. 

내부적으로는 숫자 각각을 저장하는 원형 버퍼 배열을 생성해서 팩토리얼 계산을 수행했습니다. 
곱셈결과가 10이 넘으면 다음 자리수로 올리도록 되어 있고, 버퍼 사이즈보다 크면 버리도록 되어 있습니다.  
마지막 자리수가 0이면 버퍼의 시작 지점을 하나 올려서 10으로 나누기 한 효과를 내도록 했습니다. 

버퍼 사이즈를 얼마나 여유있게 해야 되느냐가 문제가 됩니다. 10의 두 약수 2와 5중 당연히 5가 덜 흔하므로,
5의 몇 제곱까지 곱해지느냐가 중요해서 log_5 n 으로 여유를 뒀습니다. 그 위쪽의 값들은 차츰 더 관심없는 
윗자리로 밀려나게 되므로 고려하지 않아도 됩니다.

결과:
n=2012 ::  [501, 8, 2, 9, 4, 4, 6, 9, 1, 0, 3, 2, 1, 1, 1, 8, 9, 1, 0, 4, 8]
n=10000 ::  [2499, 8, 0, 0, 9, 7, 5, 1, 0, 0, 8, 4, 9, 2, 0, 9, 3, 2, 8, 8, 7]
n=1000000 ::  [249998, 4, 4, 5, 2, 1, 4, 8, 5, 0, 5, 6, 7, 1, 6, 5, 2, 8, 5, 0, 1]

수정 9/6 ) 코드 좀 리팩토링해서 약간 짧고 간결하게 고쳤습니다. 


코드는 다음과 같습니다.

2012/09/03 17:36

문제로 풀어보는 알고리즘 149쪽 문제 3.c 풀이

알고리즘 코딩 이벤트 1주차 2번째 문제


두 번째 문제를 풀어보았습니다.

n이 16 이하라는 조건이 있습니다. 16이면 이미 100억개 이상의 분할이 나오죠. 
현실적으로 모든 경우를 다 찍어보는 건 불가능할 것 같네요.
 몇 가지 경우가 있는지 가짓수 세는 문제 정도가 더 적절하지 않았을까 싶습니다.

처음에는 Set으로 결과 전체를 리턴하도록 했었는데 숫자가 커지면 불가능할 듯 해서 
Iterator만 리턴해서 하나씩 찍어낼 수 있도록 수정했습니다. 
n=12인 케이스의 경우 총 4213597가지 경우가 있는데 전부 출력시킬 때 제 노트북에서 254.86초 걸렸으니
n=16 케이스를 다 찍으려면 컴퓨터를 일주일 쯤 돌려야 할 것 같네요. 

내부적으로 분할 방법을 표현할 때에는 각 집합에 ID를 부여하고 각각의 숫자마다 이 ID를 할당시켜서 표현하도록 했습니다.


코드는 여기!

2012/08/29 11:26

문제로 풀어보는 알고리즘 0.3 생각해보기 풀이

인사이트 북 이벤트 응모용 문제풀이. 그냥 가장 단순하게 했습니다 ㅋㅋ 언어는 Java입니다. 

public static<T> void swap(T[] array, int s, int t, int k) {

@SuppressWarnings("unchecked")
T[] buf = (T[])new Object[k];

System.arraycopy(array, t-k+1, buf, 0, k);
System.arraycopy(array, s, array, s+k, t-s-k+1);
System.arraycopy(buf, 0, array, s, k);

}

1 2 3 4 5 6 7 8 9 10 다음