[OSAM] 2019 국방부오픈소스아카데미 집체교육에 도전하다! - 1-2. 코딩테스트 풀이 및 후기
글의 저작권 문제가 있는 경우, 바로 내리도록 하겠습니다.
uhug@naver.com 으로 메일 부탁드립니다.
문제는 잘 풀어보셨나요? 저는 최근에 백준으로 훈련하고, 다시 문제를 풀어보니 55분 정도 걸려서 4문제를 다 풀었습니다.
그 때 당시에는 많이 어려웠는데 다시 풀어보니 그다지 어려웠던 문제들은 아니였던 것 같습니다. (진작 공부 좀 해둘걸..)
이번 글에서는 저번 글에서 올려드렸던 문제를 풀이해보도록 하겠습니다!
저는 C언어와 Javascript(node.js)로 풀어보았는데 설명은 C언어를 기준으로 설명해보도록 하겠습니다.
만약 이전 글에서 문제를 보지 않으셨다면, 확인하고 오시길 바랍니다!!
1. 공정한 심사
아주아주 간단한 최댓값, 최솟값을 찾는 문제입니다.
우선 문제에서 12개의 자연수 입력값을 받은 후에 이들 중 최댓값과 최솟값을 찾아내고
{ 받은 숫자들을 모두 더한 값 - ( 최댓값 + 최솟값 ) } / 10
위에 계산식을 돌리면 바로 정답이 나옵니다.
최댓값, 최솟값 찾기
max := -1
for (1...12)
input := 사용자_입력값
if (max < input)
max := input
위의 Pseudocode를 보면, max 변수를 가장 최솟값으로 설정합니다.
그 후에 입력된 값들을 비교하면서 입력된 값이 max값보다 큰 경우, max값을 입력받은 값으로 바꾸도록 합니다.
이런 식으로 반복문을 전부 돌게 되면, max값에는 결국 입력받은 값 중 가장 큰 값이 저장되겠지요.
min값도 비슷한 방식으로 코드를 작성하면 됩니다.
만약 사용자 입력 범위가 정수 전체인 경우에 최댓값, 최솟값을 어떻게 찾을 수 있을까요?
기준값을 설정하기 어려운 경우라면, 사용자의 첫 번째 입력값을 최댓값, 최솟값으로 초기화를 하면 됩니다!
맨 처음 받은 수를 기준으로 설정하면, 뒤에 어떠한 수가 오든, 맨 처음 입력값보다 크거나 작거나 같거나, 셋 중 하나임이 분명하기 때문이죠!
Pseudocode로 표현하면 아래와 같겠습니다.
input := 사용자_입력값
max := input
min := input
for(2...12)
...(이하 동일)
평균을 구하는 부분은.. 굳이 설명하지 않아도 되겠지요..?
주의할 점
- C언어로 풀 때, 문제에 소숫점 2자리까지 표현해다라는 조건이 있으므로 타입 및 출력형식에 유의할 것!
2. 행운권 추첨
이 문제는 입력되는 수들 중에 중복되는 수를 제외한 수를 출력하는 문제입니다.
다시 말하자면, 반복되는 수를 찾는 것이 이 문제에서의 핵심이라 할 수 있습니다.
이 문제를 풀 때, 저는 두 가지 방법을 생각해보았습니다.
사용자의 입력을 배열로 받은 후, 반복되는 수를 찾아 제거한 후에 출력한다.
배열의 인덱스를 활용한다; 입력받는 수의 배열 인덱스에 +1을 하여 값이 1인 아이템만 출력한다.
우선 예시로, 사용자가 1, 2, 2, 5, 3, 7, 1, 2를 입력했다고 가정해봅시다.
먼저 1번의 방법으로 풀게 될 경우, 사용자의 입력이 정렬되어 있지 않기 때문에 완전탐색으로 반복되는 수를 찾아야 합니다.
즉, 위의 예시로 예를 들었을 때, 맨 앞에 1을 기준으로 잡고, 그 뒤에 2, 2, 3, 5, 7, 1, 2 를 하나씩 비교하며 1을 제거하는 것입니다.
그러나, 이런 방식으로 찾게 되면 시간복잡도가 O(n2)가 나오고,
이런 식으로 찾는다고 한다면 결과값이 5, 3, 7 이 나오게 되는데, 정답은 3, 5, 7 이므로 다시 정렬해주어야 한다는 문제가 있습니다.
그렇다고 미리 정렬을 하고, 이진탐색으로 찾아내서 결과를 도출해도 되겠지만…
이보다 더 빠르고 쉬운 방법이 2번이므로 1번은 패쓰하겠습니다
2번 방법의 경우, 우선 문제 조건을 확인해야 합니다. 문제 조건에서 자연수의 조건은 1부터 99,999입니다. 즉, 배열로 99,999칸을 설정할 수 있냐 없냐의 문제인데, 이 정도 공간은 충분히 설정할 수 있다고 판단했습니다.
그럼 여기서, 메모리 공간을 너무 쓸데없이 많이 차지해서 효율이 떨어지는 것이 아니냐고 생각하실 수도 있겠습니다만,,
알고리즘 문제 풀이에서는 메모리 조건이 없는 한, 효율보다는 빠른 실행속도, 빠르게 푸는 것이 중요합니다. 즉, 메모리는 고민할 필요 없이 넉넉하게 잡아둬도 크게 문제가 되지 않는다는 것이죠!
자, 그럼 위의 예제를 2번 문제 방법대로 푼다고 가정해봅시다!
우선, 99,999칸을 할당한 배열을 0으로 초기화합니다.
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
여기서 입력받는 수의 배열 인덱스에 +1을 한다 이 부분을 한 결과로
2, 3, 1, 0, 1, 0, 1, 0, 0, 0, ...
위와 같은 배열이 나올 것입니다.
설명하자면, 1이 2번, 3이 3번 … 이런 식으로 배열에 정보를 담는다는 것입니다.
시간복잡도는 O(n)이 되어 매우 빠르게 검색을 마무리할 수 있겠죠?
여기서 값이 1인 인덱스만 출력한다면, 3, 5, 7 이 출력됩니다. 따로 정렬할 필요도 없게되는 것이죠.
3. UI Event
이 문제는 처음 봤을 때 겁부터 먹어서 해결방법을 바로 생각해내지 못해서 시간만 잡아먹었던 슬픈추억을 가진 문제입니다..
사실, 문제를 읽어보시면 크게 어려운 문제는 아닙니다. 단순히 2차원 배열을 활용하는 문제로 볼 수 있겠습니다.
우선, 화면의 좌표 최댓값이 그리 크지 않기 때문에 화면의 좌표를 구성하는 2차원 배열을 문제 조건에 맞게 설정하였습니다.
int screen[1000][1000] = {{0, }, };
C언어로 본다면, 위처럼 초기화하면 되겠지요?
그리고 버튼의 위치 및 크기를 입력받는데, 버튼번호를 2차원 배열에 색칠한다는 느낌으로 문제를 풀었습니다.
예시로 보여드린다면, 첫 번째 버튼으로 1 5 1 5를 입력했을 때
0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0
0 1 1 1 1 1 0 0 0
0 1 1 1 1 1 0 0 0
0 1 1 1 1 1 0 0 0
0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
위 처럼 될 것이고, 그 다음 버튼으로 3 8 3 8를 입력했을 때
0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0
0 1 1 1 1 1 0 0 0
0 1 1 2 2 2 2 2 2
0 1 1 2 2 2 2 2 2
0 1 1 2 2 2 2 2 2
0 0 0 2 2 2 2 2 2
0 0 0 2 2 2 2 2 2
0 0 0 2 2 2 2 2 2
이렇게 될 것입니다. 버튼번호가 높을 수록, 나중에 그려지는 것이므로 이전 버튼 위에 나타난다고 문제에 적혀있기 때문에 기존에 배열에 있던 버튼번호를 덮어씌어버리면 되겠습니다.
이렇게 버튼 정보를 담은 2차원 배열이 완성되면, 그 다음에는 사용자가 입력한 좌표의 값을 그냥 출력하면 끝나는 문제입니다.
4. 흔한 제목 찾기
아무래도 마지막 문제이다보니 1, 2, 3번보다는 조금 난이도가 있는 문제로 출제된 것 같습니다…만
풀어보셨다면 이 문제도 그리 어려운 문제는 아닙니다.
(물론 저는 이 문제를 풀다가 멘붕이 와버려 모든걸 망쳐버렸지만..)
우선, 사용자가 입력한 알파벳 문자열을 입력받은 후에
미리 준비해둔 26칸짜리 배열에 사용자가 입력한 시작, 끝 지점 사이에 알파벳을 알파벳의 순서를 인덱스로 하여 +1을 했습니다.
즉, 특정 구간 안에 알파벳의 숫자를 배열의 인덱스를 활용하여 기록하였다는 것입니다. 2번 문제와 비슷하죠?
특정 구간에 알파벳 개수 정보가 담긴 26칸짜리 배열에서 가장 큰 값을 가진 인덱스 값이 이 문제의 정답이 되겠습니다.
물론, 출력할 때는 다시 알파벳으로 변환하여 출력해야겠지요?
C언어에서 알파벳의 순서를 구할 때, 알파벳이_담긴_변수-'A'로 순서를 구했습니다. 아스키코드를 활용한 것인데요, A는 65이므로 특정 알파벳에서 A를 빼게 된다면 알파벳의 순서를 구할 수 있게 됩니다.
'A'-'A' == 0, 'B'-'A' == 1, 'C'-'A' == 2 … 이런 식이 되는 것이죠.
주의할 점
- C언어로 풀 시,
gets()사용법과 입력버퍼에 대한 개념을 알고 있다면 쉽게 풀 수 있습니다
마무리를 지으면서..
문제를 풀어보니 어떠신가요? 당황하지 않는다면 생각보다 무지 어려운 문제는 없지 않나요..?
평소에 백준에서 (solved.ac 기준) 브론즈 문제를 모두 무난히 푸실 수 있다면 크게 막히는 문제는 없을 것이라 생각합니다!
역시.. 알고리즘은 투자한 시간 대비 실력이 나오는 것 같네요 ㅠㅜ
2020년에도 집체교육과정을 선발할텐데 이번 글이 도움이 되시길 바랍니다!
그럼 다음 글에서 집체교육 후기를 본격적으로 써보도록 하겠습니다 :D
이전 글: [OSAM] 2019 국방부오픈소스아카데미 집체교육에 도전하다! - 1-1.
다음 글: [OSAM] 2019 국방부오픈소스아카데미 집체교육에 도전하다! - 2.