Good Program Good Programmer

【문제】

계단 수(n)와 한번에 오를 수 있는 최대 수(m)가 주어 졌을 때, 계단을 오를 수 있는 경우의 수를 구하시오.
(단, 0 < n < 100, 0 < m < n)

【예시】

• 계단 수 (n) : 3, 한번에 오를 수 있는 최대 수(m) : 3
• 최대 1칸 뛰어넘을 때 : ㅁ + ㅁ + ㅁ -> 1개
• 최대 2칸 뛰어넘을 때 : ㅁ + ㅁㅁ, ㅁㅁ + ㅁ -> 2개
• 최대 3칸 뛰어넘을 때 : ㅁㅁㅁ -> 1개

경우의 수 : 4

【입출력 예시】 

【문제 풀이】

이 문제를 풀기 위해선 알아야 할 사실이 있다. 

먼저 어떤 사람이 계단을 올라갈 때 0개의 계단을 오르는 방법과 1개의 계단을 오르는 방법은 모두 1개이다. 왜냐하면 0개는 안움직이면 되는 것이고 1개의 계단은 그냥 1개를 올라가면 되는 것이기 때문이다.

f(n,m)을 한번에 m보다 작은 자연수의 계단을 올라갈 수 있는 사람이 n개의 계단을 올라가는 방법의 수를 구하는 함수라고 했을 때 어떤 사람이 0개의 계단과 1개의 계단을 올라가는 방법의 수는 각각 1개이다.(단, n과 m은 자연수) 

이를 식으로 표현하면 f(0,m) == f(1,m) == 1(m은 0보다 큰 자연수)이 된다. 이 사실을 염두해 두고 풀이를 진행하겠다.

그렇다면 f(2,2)는 어떨까?

위 그림을 보면 2개의 계단이 있고 빨간색 사람은 1층에 초록색 사람은 0층이 서있다. 여기서 빨간색 사람은 2층까지 1계단만 올라가면 모든 계단을 등반하는 것이고 초록색 사람은 2개의 계단을 오르면 모든 계단을 등반하는 것이다.

그렇다면 이 두 사람이 서있는 위치에서의 f(n,m)은 어떻게 될까?

만약 올라야하는 계단의 수가 1이라면 빨간색 사람이 서있는 위치가 최종 도착점이 될 것이고 올라야하는 계단의 수가 0이라면 초록색 사람이 서있는 위치가 최종 도착점이 될 것이다.

그런데 빨간색 사람과 초록색 사람은 이미 1층과 0층이 각각 서있다. 즉, 최종 도착점이 1층일 때와 0층일 때 빨간색 사람과 초록색 사람은 이미 최종 도착점에 도달한 것이다.

즉 두 사람이 서있는 위치에서의 f(n,m)은 빨간색 사람은 f(1,m), 초록색 사람은 f(0,m)이 된 것이다. (최종 목표인 n이 각각 1과 0이기 때문에)

정리하자면 두 사람이 있는 위치에서 1칸 혹은 2칸만 올라가면 2칸의 계단을 모두 등반한것이 되니 두 사람의 위치까지 올라가는 경우의 수를 더하면 f(2,2)가 나오는데 두 사람의 위치까지 올라가는 경우의 수는 각각 f(1,m)과 f(0,m)이고 이는 우리가 제일 처음에 확인했듯이 1이기 때문에 f(2,2) = f(0,2) + f(1,2) = 1 + 1 = 2가 된다. 따라서 f(2,2)는 2가 된다.

여기서 우리가 중요시 해야하는 개념은 바로 1칸 혹은 2칸 올라가면 최종 목적지에 올라갈 수 있는 위치까지 올라갈 수 있는 경우의 수를 모두 더하면 우리가 최종적으로 올라가고자 하는 위치까지 가는 경우의 수를 알 수 있다는 점이다.

이 개념만 알고 있다면 n과 m이 몇이 오든간에 f(n,m)을 서브 항목으로 나눌 수 있다.

예를 들어서 그렇다면 f(3,3)은 값이 뭘까?

f(3,3)은 위 그림과 같이 세 사람이 서있는 위치로 표현할 수 있다.

이를 식으로 표현하면 다음과 같다.

f(3,3) = f(0,3) + f(1,3) + f(2,3) 

이 식들 보면 또 한가지 의문점이 들 수 있는데 만약 m이 n보다 크다면 그것은 무엇을 의미하는 것일까?

f(2,3)은 2개의 계단을 올라가지만 한 번에 3개의 계단을 올라갈 수 있는 경우의 수이다. 하지만 2개까지만 올라가면 되니 3개의 계단을 올라가는 경우의 수는 카운트하지 않는다. 따라서 f(2,3) == f(2,2)와 같다. f(0,3)과 f(1,3) 도 f(0,0)과 f(1,1)과 같다.

그리고 이는 우리가 전에 구했던 값들로 알 수 있다.

f(0,3)과 f(1,3)은 1, f(2,3)은 2이다.

따라서 f(3,3) = f(0,3) + f(1,3) + f(2,3) = 1 + 1 + 2 = 4가 된다.

마지막으로 다른 예를 한 번 들어보자

이번엔 n≠m인 경우를 살펴보자.

f(3,2)는 한 번에 2개의 계단을 올라갈 수 있는 사람이 최종적으로 3층 계단까지 도달하는 경우의 수이다.

이는 위 그림과 같이 표현할 수 있다. 빨간색 사람은 1칸만 올라가면, 초록색 사람은 2칸만 올라가면 최종 계단에 오를 수 있는 상태이다. 이 상태를 식으로 나타내면

f(3,2) = f(2,2) + f(1,2)가 된다. 즉, f(3,3)에서 f(0,3)이 빠진 값이 되며 이는 f(3,2)가 f(3,3)보다 1이 작다는 것을 유추할 수 있다.

위와 같은 정보들을 통하여 우리는 점화식을 유추해볼 수 있다.

f(n,m) = f(n-1,m) + f(n-2,m) + ... f(n-m,m)

그렇다면 우리가 필요한 정보는 모두 얻었으니 코드를 작성해보자.

코드는 매우 단순하다.

먼저 "n m"을 입력받아서 저장하고 계단함수에 인자를 전달한다.

인자를 받으면 계단 함수는 n이 1보다 작거나 같은지 검사하여 참이라면 1이라는 값을 리턴해준다.

n이 1이 아니라면 for문을 반복하면서 way라는 변수에 f(n-1,m), f(n-2,m), f(n-3,m) ... f(n-m,m)을 차례로 더해준 뒤 way를 리턴한다.

for문을 도는 도중 만약 i가 n보다 커진다면 n-i를 할 시 음수값이 반환되기 때문에 이러한 경우는 카운팅에서 제외시켜주기 위하여 break문을 써서 탈출하도록 하였다.

이게 끝이다.

【전체코드】

【느낀점】

처음에 이 문제를 풀기 위해서 직접 경우를 세는 방향으로 코딩을 했었다.

그랬는데 완전 뻘짓이었다. 이 문제의 핵심은 실제로 올라가는 방법을 구한다음 갯수를 세는 것이 아닌 재귀를 통하여 결과값을 더하여 해결하는 것이다.

그렇다면 만약 등반하는 모든 경우를 출력하라고 한다면 어떻게 해야할까?

또한 재귀를 통해 풀 수 있는 문제는 동적 프로그래밍을 통해서도 해결할 수 있는데 동적 프로그래밍을 코딩을 한다면 어떻게 짜야할까?

궁금하다.

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

해결 방법

이 문제의 경우도 앞선 문제와 크기 다르지 않다.

정렬하는 인자가 나이와 가입순으로 바뀌었을 뿐이지 지난 정렬문제에서 썼었던 다인자 정렬방식을 그대로 쓰면될 듯 하다.

문제는 이번엔 정렬 요소는 2개인데 나이값에 따라 따로 이름을 저장해야한다는 점이다.

필자는 이 문제를 풀 때 정렬 요소를 2개에서 1개로 줄였다.

무슨 말이냐면 나이 순으로 정렬하되 나이가 같으면 가입한 순으로 정렬을 하라고 되어있는데 이때 LinkedhashMap을 쓰면 가입한 순번을 따로 인자로 둘 필요없이 자연스레 가입한 순서대로 출력이 된다.

따라서 인자가 2개에서 1개로 줄었기 때문에 예전처럼 map을 써서 나이(key) - 이름(value)로 저장하면 시간도 빠르고 잘 정렬될 것이다.

그래서 프로그램의 동작과정은 다음과 같다.

1. 나이(key) - 이름(value) 형식의 map으로 값들을 입력받는다.

2. 나이(key)를 배열로 리턴한 뒤 정렬한다.

3. 정렬된 나이순대로 이름을 map에서 가져와서 문자열에 추가한다.

1. 

2. 

3.

테스트용 코드

위 코드는 저번 코드에서와 마찬가지로 words.txt에서 1개를 빼오고 1~200까지의 수 중 랜덤으로 1개를 골래서

"나이 단어" 순으로 n개의 문자열을 생성해주는 코드이다.

words.txt link : github.com/dwyl/english-words/blob/master/words.txt

위 코드를 이용해 10만개의 문자열을 생성하고 우리가 작성한 코드에 넣어서 실행해보았더니

위와 같은 실행시간이 도출되었다.

소스코드

느낀점

만약 지금까지의 문제들을 착실히 풀어왔다면 그리 어렵지 않은 문제였다.

특히나 LinkedHashMap을 이용한 것이 신의 한수였다.

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

문제풀이

이전 글 좌표 정렬하기 느낀점에서 내가 짠 코드보다 더 나은 코드가 있어서 소개한적이 있었다.

그 코드는 List.sort(); 메소드에 new comparator 클래스를 선언하여 그 안에 있는 compare메소드를 오버라이드해서 새로운 규칙의 비교 메소드를 생성하는 형식을 람다로 축소하여 2개 이상의 인자에 대하여 정렬하는 방법을 소개한적 있었다.

그래서 이번 문제에서 그 코드를 응용하여 적용해보았는데 위와 같은 13개의 입력값에 대해선 문제없이 작동하는 걸 확인하였다. 아래가 그 코드이다.

위 코드는 테스트용 코드로 20000개의 랜덤한 단어들을 문자열로 입력받아서 정렬을 수행하는 코드이다.

하지만 위 코드로 테스트를 진행했을 때 실행시간이 거의 2.5~3초 가까이 나왔다.

그래서 보기엔 더 심플하고 더 빠르게 될 것만 같았던 코드가 시간초과로 문제를 해결할 수 없자 살짝 뇌정지가 왔었다.

그래서 이전에 내가 썼던 방법대로 map을 이용하여 정렬하는 방식을 이용해야겠다는 생각이 들었다.

그래서 맵을 이용해서 2개의 인자를 정렬할 때는 다음과 같은 방식으로 진행한다.

1. 값을 입력받는다.

2. map에 해당 데이터를 입력한다. 이때 만약 같은 값이 있다면 넘어간다.

3. 입력받은 데이터의 key 배열을 정렬한다.

4. 각 key에 해당하는 value리스트를 정렬한다.

5. 각각의 key와 value들을 순서대로 출력한다.

1~2.

먼저 n을 입력받고 map을 만든 후 단어들을 입력받는다. 이때 해당key값이 없다면 새로운 list를 추가해준 뒤 값을 입력한다.

이때 해당 key값에 문자열 s가 있는지 확인하여 있다면 아무런 동작도 하지 않고 없다면 문자열을 추가한다.

이 코드가 내가 위에 썼었던 코드보다 빠르게 동작하는 이유는 위 코드는 값이 들어올 때마다 모든 리스트를 탐색하는 반면 이 코드는 입력된 값이 특정 key에 해당하는 리스트에서만 존재하는지 확인하기 때문에 실행시간이 현저하게 줄어들기 때문이다.

3.

4.

key값에 해당하는 리스트들을 정렬해준다. 여기서는 문자열만 비교하므로 특별히 new comparator클래스를 만들필요는 없다.

5.

그리고 모든 값들을 문자열에 추가한 뒤 해당 문자열을 리턴하면 끝난다.

테스트용 단어 생성기 코드

이 코드는 words.txt라는 텍스트 파일로부터 단어를 n개 만큼 랜덤으로 가져오는 메소드이다. 해당 텍스트 파일의 단어의 갯수가 466550개여서 466550크기의 배열을 생성하였다.

https://github.com/dwyl/english-words/blob/master/words.txt

위 경로에 가면 다운받을 수 있는 사전 파일이다.

wordSortUsingMap vs wordSortUsingList

wordSortUsingMap은 문제를 해결한 코드이고 wordSortUsingList는 시간 초과가 난 코드이다. 두 코드 간의 시간 차이를 비교해보겠다.

 테스트 코드는 위와 같고 그 결과는 다음과 같다.

거의 7배 가까이 차이가 나는 것을 볼 수 있다. 내가 잘못한 건지는 몰라도 sort메소드에 compare메소드를 오버라이드해서 정렬하는 방식은 조금 느리다는 것을 확인할 수 있었다.

물론 주요한 시간의 차이는 처음 값을 입력받을 때 중복값을 검사하는 과정에서 발생한다는 것을 감안해도 좀 심한 차이인 것 같다.

만약에 처음 중복값을 검사하지 않는다면 어떻게 될까해서 돌려보았더니 결과는 다음과 같았다.

여전히 7배 가까이 차이가 나는 것을 확인할 수 있었다.

소스코드

느낀점

일단 좋아보이는 코드가 진짜 다 좋은건 아니구나라는 것을 느꼈다.