프로그래머스 월간 코드 챌린지 시즌2 후기

5.13일 19:30~22:30 3시간 동안 알고리즘 4문제를 푸는 챌린지다.

 

4월달, 5월달 두 번에 거쳐 진행했고 4문제를 풀면 미션 클리어로 이벤트 상품에 응모되며,

1등에겐 상금 20만원이 주어진다.

 

결론부터 말하자면 나는 4문제 중 한 문제만 통과하였다.

시작한 지 1시간 만에 4문제 모두 통과한 1등이 나왔다는 메세지를 봐서 전의를 상실했다..

 

각설하고 출제 문제를 보자.

 

1. 약수의 개수와 덧셈

https://programmers.co.kr/learn/courses/30/lessons/77884

코딩테스트 연습 - 약수의 개수와 덧셈

x의 약수가 짝수 개이면 더하고, 홀수 개이면 빼는 문제다.

어려울 것 없이 호다닥 풀어서 통과. 여기까진 행복하다.

 

2. 2개 이하로 다른 비트

https://programmers.co.kr/learn/courses/30/lessons/77885

코딩테스트 연습 - 2개 이하로 다른 비트

F(x)= x보다 크면서 x와 비트가 1~2개 다른 수 중에 가장 작은 수를 구하는 문제다.

뭐지.. 뭔가 XOR연산을 이용하는 문제인가 싶었는데, 한참 고민하다가 모르겠어서 패스했다.

다시 풀어봐야겠지만, 풀이를 안 보면 못 풀것 같다.

 

p.s. xor연산은 없었다...

풀이 : https://ongveloper.tistory.com/59

 

 

3. 110 옮기기

https://programmers.co.kr/learn/courses/30/lessons/77886

코딩테스트 연습 - 110 옮기기

x= "111011011" 일 때, x안에 "110"을 옮겨서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 찾는 문제다. 

kmp 알고리즘의 실패 함수를 이용해서 110을 찾는 것까지만 하고,

110을 이동시켜 사전 순으로 가장 앞선 문자열을 찾는 것은 구현하지 못했다.

이것도 다시 생각해 보고 안되면 풀이를 봐야 할 것 같다.

 

p.s. kmp로 하면 시간초과... 110을 추출하는 데에 선형시간의 알고리즘을 필요로한다.

풀이 : https://ongveloper.tistory.com/60

 

4. 중력작용

https://programmers.co.kr/learn/courses/30/lessons/77887

코딩테스트 연습 - 중력 작용

1부터 n번까지의 번호를 갖는 n개의 노드를 갖는 트리에서,

 

1. u쿼리 - u번 노드를 포함한 하위 노드들의 값들을 출력

2. u,w쿼리 -u번 노드부터 부모 노드들의 값들을 아래로 한 칸씩 땡기며 루트 노드의 값은 w로 바꾼다.

 

두 가지 쿼리를 수행하는 문제다.

dfs로 u쿼리를 구현하였고,

edges(간선)을 거꾸로 타서 u,w쿼리도 구현하였으나, 시간 초과로 0점이다.

이후 시간을 줄이기 위해 전전긍긍하다가 시간이 끝났다.

코드를 저장해놨으니 이 문제는 최적화만 하면 통과할 거란 생각이 든다.

하지만 이 문제의 정답자수가 4명인 걸로 봐서, 코드를 갈아엎어야 할 수도..

 

 

알고리즘 공부를 시작한 지 어느덧 3개월

c++언어도 익숙해졌고, 

백준 문제를 풀 때 사용하는 visual studio와, 프로그래머스 ide도 어느 정도 익숙해졌다.

구현할 수 있는 알고리즘도 많아졌지만, 알고리즘의 원리를 제대로 알고 있어야 하는 응용문제들과,

구현 문제들엔 아직 약하다.

구현 문제들을 많이 풀어보고, 알고리즘의 원리를 파악해서 유연한 사고로 문제를 풀자!