한동안 알고리즘 문제 풀이에 신경을 쓰지 못하여 부족한 DP에 대한 감을 잡으려고 고른 문제다.

https://www.acmicpc.net/problem/2294

DP 문제는 구현 자체가 어렵진 않지만 문제 해결법에 접근하는 과정이 다소 어려운 것 같다.

다른 알고리즘 같은 경우는 연습을 통해 익숙해진다면 DP는 아무리 연습해도 문제에 따라 쉽게 떠오르지 않는 알고리즘 같다.

문제 풀이

해당 문제의 소재는 다소 익숙한 원하는 금액을 지불하는 동전의 최소 개수다.

동전의 개수는 n개이고 가치의 합은 k이며 각각 1 <=n <=100, 1 <=k <=10000의 제한 조건을 갖는다.

같은 동전이 여러 번 주어질 수 있지만 가치의 합인 k를 dp 리스트로 잡고 각 인덱스마다 n번 반복하면 되므로 시간 복잡도는 O(n*k), 즉 최대 100만 번이라 딱히 고려하진 않아도 되는 조건이었다.

물론 필자는 효율성을 높이기 위해 Set로 형 변환했다가 다시 List로 형 변환했었다.

이렇게 Set로 형 변환하면 중복된 원소를 제거할 수 있다.

다만 이 문제에서 중요하게 고려해야 할 점은 가치의 합인 k로 만드는 것이 불가능할 수도 있단 점이다.

여태 경험했었던 동전 DP 문제는 애초에 불가능에 대한 조건은 없었기에 최소 개수만 구하는데 집중했었고 이번 문제도 처음에 똑같이 시도했다가 틀렸단 메시지를 받았다.

그 과정에서 문제를 다시 정확히 읽고 스스로 테스트 케이스를 만들어 오류를 잡아내는 연습도 필요한 것 같다.

각설하고 전체 코드를 통해 설명하도록 하겠다.

n,k=map(int,input().split())
coin=[]
for i in range(n):
    coin.append(int(input()))

coin=list(set(coin))
dp=[0 for i in range(k+1)]
for i in range(1,len(dp)):
    for j in range(len(coin)):
        if i-coin[j]==0:
            dp[i]=dp[i-coin[j]]+1
        elif i-coin[j]>0 and dp[i-coin[j]]!=0:
            if dp[i]==0:
                dp[i]=dp[i-coin[j]]+1
            elif dp[i-coin[j]]+1<dp[i]:
                dp[i]=dp[i-coin[j]]+1

if dp[k]==0:
    print(-1)
else:
    print(dp[k])

1번째 줄은 n과 k를 입력받고 2번째 줄의 coin은 동전의 가치를 입력받을 리스트다.

6번째 줄이 중복을 제거하는 코드이며 7번째 줄의 dp는 k인 가치의 합을 인덱스로 갖는 dp 리스트다.

어떤 것을 dp 리스트로 잡을지는 문제를 많이 풀다 보면 감 잡게 될 것이다.

이제 8번째 줄부터 이중 for문을 통해 전체 dp 리스트를 돌며 각 인덱스마다 coin 리스트를 반복해 해당 인덱스가 해당하는 값에서 동전을 쓸 수 있는지 확인하고 쓸 수 있다면 최소 개수인지 확인한다.

10번째 줄의 if 문은 동전의 가치를 현재의 가치에서 뺏을 때 0원이라면 동전을 한 개 사용할 수 있단 뜻이므로 현재 가치의 동전 개수를 업데이트했다.

12번째 줄의 if 문에 주목해야 하는데 현재 가치에서 동전의 가치를 뺀 값이 0보다 크고 그 뺀 값의 동전 개수가 0개보다 많을 때만 개수를 업데이트해줬다.

왜냐하면 만약 현재의 가치에서 동전의 가치를 뺀 가치에 대한 동전의 개수가 0개 라면 해당 가치로 동전을 조합할 수 없기 때문이다.

예를 들어 k가 10이고 n이 1이며 동전의 가치가 3일 때를 고려해 보자.

dp[10]인 상황에서 동전의 가치를 뺀 dp[7]을 생각해보면 dp[7]은 0이다.

3으로는 절대로 7을 만들 수 없기 때문이다.

따라서 7원으론 동전을 조합할 수 없기 때문에 10도 불가능하다는 얘기가 된다.

이 부분만 고려한다면 골드 문제를 도전하는 사람들에게 나머진 딱히 어려운 부분이 없을 것이라 생각한다.

이 문제를 통해 지문을 잘 읽고 테스트 케이스를 만들어보는 과정을 직접 해보는 것이 중요하다는 것을 체감했다.

https://www.acmicpc.net/problem/4485

문제 풀이

왼쪽 위칸인 [0,0]에서 출발 후 오른쪽 아래칸인 [N-1, N-1]에 도착하는 경로를 생각하는 그래프 탐색 문제였다.

다만 흔히 Queue나 Stack을 이용하여 BFS, DFS로 탐색하는 방법이 아닌 Priority Queue를 사용한 다익스트라 문제였다.

이 문제에서 중요한 점은 거리의 최소가 아니라 비용, 즉 가중치의 최소가 중요하기 때문이다.

상당히 돌아가는 경로라 하더라도 비용이 최소면 해당 경로를 택하기 때문에 가중치의 합을 기준으로 최소 비용 경로를 고려해야 한다.

Priority Queue를 이용한 원리는 다음과 같다.

먼저 시작 노드에서 이동 가능한 노드를 가중치의 합과 함께 Priority Queue에 넣는다.

가중치의 합이 가장 작은 노드를 선택한 뒤 해당 노드에서 이동 가능한 노드를 가중치의 합과 함께 Priority Queue에 넣는 행동을 [N-1, N-1]에 도착할 때까지 반복한다.

[N-1, N-1]에 도착하면 해당 가중치를 저장하고 반복을 종료한다.

한 번은 중간에 이동 가능한 노드인지 체크하는 과정에서 이미 방문한 노드가 최소 가중치의 합을 보장하는지 의문을 품는 질문을 본 적이 있었는데 결론부터 말하자면 각 노드에서 가장 먼저 선택되었을 때의 가중치가 최소다.

Priority Queue를 통해 매번 가장 작은 가중치의 합을 선택하기 때문에 두 번째 방문할 때는 같거나 클 수밖에 없기 때문이다.

이제 전체 코드를 통해 설명하도록 하겠다.

import heapq
inf = float('INF')
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
res_num = 1
while True:
    n = int(input())
    if n == 0:
        break
    else:
        graph = []
        queue = []
        res = [[inf for i in range(n)]for j in range(n)]
        for i in range(n):
            graph.append(list(map(int, input().split())))
        heapq.heappush(queue, (graph[0][0], 0, 0))
        res[0][0] = graph[0][0]
        while len(queue) > 0:
            temp = heapq.heappop(queue)
            if temp[1] == n-1 and temp[2] == n-1:
                break

            for i in range(len(dir)):
                dy = temp[1]+dir[i][0]
                dx = temp[2]+dir[i][1]
                if 0 <= dy < n and 0 <= dx < n and res[dy][dx] > temp[0]+graph[dy][dx]:
                    res[dy][dx] = temp[0]+graph[dy][dx]
                    heapq.heappush(queue, (temp[0]+graph[dy][dx], dy, dx))
        print("Problem %d: %d" %(res_num,res[n-1][n-1]))
        res_num += 1

4번째 줄까지는 Priority Queue를 사용하기 위한 heapq 선언, 방문하지 않은 노드는 무한대 선언, 노드의 방향 선언, 문제 번호 선언이다.

5번째 줄의 while문을 통해 0을 입력받을 때까지 반복적으로 문제를 처리했다.

12번째 줄의 res는 노드의 최솟값을 갱신하는 리스트로 마지막에 res [N-1][N-1]을 출력하면 된다.

15번째 줄은 시작 노드의 가중치와 y좌표, x좌표 순서대로 넣음으로써 자동으로 MinHeap 구조인 heapq에서 최소 가중치를 꺼내도록 하였다.

18번째 줄의 반복문은 Priority Queue가 빌 때까지 계속 원소를 꺼내는 작업을 하는데 도착지점에 도달한다면 탈출하도록 구현하였다.

방향 탐색을 하기 위해 22번째 줄에서 이동 가능한 노드인지 체크한 후 Priority Queue에 넣어주도록 구현하였다.

구현 방법이나 알고리즘 측면에서 어려운 문제는 아니었지만 우선순위 큐를 거의 사용해보지 않았다면 충분히 떠올리기 어려울 수 있다고 생각한다.

필자 또한 다양한 그래프 문제를 경험해봤지만 습관처럼 BFS, DFS를 사용했기에 해당 문제를 보고 바로 Priority Queue를 떠올리진 못했다.

보다 유연하고 다양하게 생각하도록 노력하는 게 중요한 것 같다.

오늘 (2022.03.19 토) 2022 SK ICT Family 신입 개발자 채용 챌린지 코딩 테스트 2차를 봤다.

1차는 오전(10시 ~ 13시)에 시작해서 3시간 동안 봤지만 2차는 4시간이라서 그런지 오후(13시 ~ 17시)에 시작해서 4시간 동안 봤다.

문제 개수는 똑같이 4문제로 문제당 시간이 늘어나면 그만큼 난이도는 올라간다는 소린데 역시나 상당히 어려웠다.

이번에는 대체적으로 구현 문제가 나왔는데 구현이 이렇게 어렵다는 게 자괴감이 살짝 들긴 했다.

문제를 전반적으로 훑어보고 상당히 어렵단 느낌이 들자 목표를 두 문제로 잡았지만 계속 오류와 씨름하고 시간을 보내느라 결국 한 문제밖에 풀지 못했다.

어떤 느낌이냐면 푸는 방법은 알겠으나 막상 구현하려고 하니까 정확한 구현이 안되고 계속 부분적으로 오류(인덱싱, 순서 등)가 나서 풀릴 거 같은데 안 풀리는 문제였다.

조금 특이한 점은 1차 때는 코드 제출만 되는 거였지만 2차 때는 정확한 구현이 필요한 문제라 그런지 카카오처럼 코드를 제출하면 실제 테스트 케이스를 돌려서 불합 여부를 확인할 수 있었다.

원래 멘탈도 비교적 좋은 편인데 긴 시간 동안 푸는 방법도 알겠지만 지속적으로 부분 부분 오류가 나서 해결이 안 되니 상당히 힘들긴 했다.

2시간 동안 2문제에 대한 구현은 했으나 오류 때문에 정작 한 문제도 제출을 못하자 그만 포기할까 생각이 들었으나 이것도 경험이라 생각하고 끝까지 붙잡고 있으니 결국 한 문제는 풀긴 해서 다행인 것 같다.

끝나고 오픈 단톡방에서도 반응을 확인해보니 다들 어려웠단 분위기라 나만 어려웠던 게 아니란 안도감이 들어서 다행이었다.

0문제 투표가 없어서 그런지 투표한 사람도 적긴 한데 30% 정도가 두 문제, 나머지는 한 문제라 대규모 공채가 아닌 점을 고려하면 아마 합격은 어렵지 않을까 생각한다.

스스로 아직 많이 부족하다는 것을 체감하게 된 아주 좋은 경험이었고 자만 없이 꾸준히 노력해야겠다.

결과 메일이 도착하면 포스팅을 수정하도록 하겠다.

불합격 후기

1차보다 더 늦은 6일 만에 결과가 나왔는데 아마 난이도가 어려워서 합격 컷 기준을 잡는데 시간이 더 걸리지 않았나 싶다.

결과는 예상대로 불합격이었다.

단톡을 보아하니 2문제로 SK에 합격했다는 글을 보아 한 문제만 더 맞혔으면 합격했을 텐데... 란 아쉬움이 많이 남았다.

아예 손을 못 댄 것도 아니고 풀이 방법은 고안했으나 디테일한 부분에서 오류가 발생하여 풀지 못했기 때문이다.

시간도 많은 상황에서 차근차근 논리를 주석으로 정리하며 침착하게 각 조건을 정확하게 구현했으면 충분히 풀었을 텐데 긴 시간과 "어렵다"란 생각이 발목을 붙잡은 것 같다.

최근에 본 토스 뱅크 코테도 6문제 중에서 4문제를 풀 수 있었지만 2번 문제에서 딱 하나의 테스트 케이스를 통과하지 못하여 3문제 푼 점이 상당히 아쉬웠는데 지금 상당히 딜레마에 빠진 상황이다.

SSAFY 강의에 대한 복습과 프로젝트 진행으로 시간이 여유롭지 않은 상태에서 기본 실력으로 코테를 보려 했으나 한동안 준비를 안 해서 그런지 현재 디테일한 구현을 정확하게 못하는 것 같다.

그렇다고 코테에 신경 쓰기도 뭐한 게 SSAFY 시작 두 달 정도는 Front-End와 알고리즘 기본을 해서 시간적으로 여유가 많았지만 지금은 처음 접하는 Back-End를 나가서 여유가 전혀 없기 때문이다.

내일 보는 라인 코테의 결과를 보고 좀 더 시간을 써야 할지 아니면 기본적으로 SSAFY에서 알고리즘 진도를 나가는 시기에 디테일한 부분을 잡도록 해야 할지 결정해야 될 것 같다.

침착함과 디테일한 구현을 위한 정리를 하는 습관이 필요하다는 것을 뼈저리게 느낀 경험이었다.

합격 전 후기

프로그래머스를 통해 SK에 대한 공채 프로세스가 진행되었다.

보통 유명한 IT기업(네이버, 라인, 카카오 등)들은 이미 자소서나 스펙 입력을 최소화하고 자격만 갖추었다면 무조건 코딩 테스트를 볼 수 있게 하여 서류전형 없이 오직 지원자의 개발 능력만을 검증하는 프로세스를 적용했다.

또한 유명하진 않더라도 조건이 상당히 좋은 튼실한 IT기업들도 정량적인 스펙이 개발 역량을 대변하지 않기 때문에 지원자의 역량 평가 기준으로 서류전형을 생략한 채용 프로세스를 진행하고 있는 추세다. 

하지만 흔히 어르신들도 잘 아시는 대기업(삼성, LG, SK)들은 아직 개발자를 채용할 때 서류전형으로 먼저 당락을 결정하고 개발 능력을 검증하는 경향이 있다.

그래서 필자도 조금 놀라웠는데 본인이 아는 한 아마 유명하고 오래된 대기업 중에서는 처음으로 서류전형을 생략하고 오직 개발자의 능력 검증만으로 채용하는 첫 기업이 SK인 것 같다.

그걸 잘 알아서 그런지 채용 내용에도 상당히 강조해 놓은 것을 확인할 수 있었다.

또한 여태까진 계열사에 대한 지원을 일일이 했어야 했지만 이번에는 모집분야를 선택하여 해당 분야를 모집하는 모든 계열사에 대해 지망을 선택하여 한꺼번에 지원 가능하단 점이 상당히 편했다.

전체적인 일정은 1~2차 코딩 테스트 -> 1~2차 면접 -> 입사 순으로 진행되며 이번에 1차 코딩 테스트를 보게 되었다.

언어는 대부분의 코테에서 통용되는 언어들(C, C++, Java, Python 등)을 사용할 수 있어서 딱히 걱정할 필요는 없을 것 같다.

1차 코딩 테스트는 3시간 동안 4문제를 풀게 되며 당연한 말이지만 문제에 대한 정보는 저작권법에 의해 공개가 불가능하다.

다만 말할 수 있는 점은 다양한 문제가 나왔다는 것이며 보통의 코테는 문제당 30분을 기준으로 출제되는데 역시 문제당 시간이 긴 만큼 까다로운 문제가 포함된 것 같다.

필자는 주로 트리와 최적화 문제(까다로운 DP)에 약한 편인데 다행히 카카오를 제외한 대부분의 기업은 효율성 테스트를 적게 보는 듯 하지만 이번에 나온 트리 문제도 역시 어떻게 풀어야 되는지 감을 잡기 힘들었다.

물론 아마 감을 잡았다고 하더라도 풀긴 힘들었을 것 같다.

2문제를 푸는데 약 4~50분이 걸렸으나 그래프 문제에서 아이디어를 떠올리는 것과 조건 처리가 까다로워 약 한 시간 반 정도 걸렸다.

이 문제도 제시된 테스트 케이스와 직접 만든 테스트 케이스도 통과하긴 했으나 "맞았다"라는 확신을 갖기엔 조금 부족한 느낌이다.

따라서 남은 시간은 30분 정도기에 구현할 시간은 부족했을 것이다.

아마 체감상 까다로운 문제가 두 문제 있기도 하고 2차 코테가 예정되어 있기 때문에 합격권은 2~3개가 아닐까 생각한다.

필자는 그래프 문제를 제대로 풀었다면 3문제, 조건에서 틀린 부분이 있다면 2문제를 맞았기 때문에 합격 컷에 비슷하리라 짐작한다.

오픈 단톡방에서도 2문제가 가장 많았고 그다음이 3문제라서 충분히 합격을 기대해 볼 수 있을 것 같다.

여러 기업의 코테를 경험해보고 네이버, 라인 등의 합격 컷 수준까진 올라왔단 자만심에 여태 트리는 단순하게 구현과 탐색 정도의 준비만 했어서 부족한 걸 알면서도 SSAFY 강의 듣는다고 피곤하다는 자기 합리화에 빠져 외면했었던 것 같다.

보다 안정적인 합격권을 위해서 지금부터라도 부족한 부분을 채워나가야겠다.

합격 후기

오늘 (2022.03.16, 수) 코테 합격 메일이 왔다.

지난 토요일(2022.03.12)에 코테를 봤으니 4일 만에 결과 발표가 된 것이다.

이번 채용 과정 자체가 다른 직무, 각 계열사에 대한 지망 순위를 받고 다 같이 코테를 봤기 때문에 아마 거기서 합격 컷이 조금 달라질 수 있을 것이라 생각한다.

필자 또한 확신이 안 서는 문제 포함해서 3문제를 풀어서 합격했고 단톡방을 보아하니 비록 개인의 의견이라 확실한 것은 아니지만 다소 다양하게 합격했단 소리가 들렸다.

따라서 "몇 문제를 풀면 합격이다 아니다" 라고 정확히 말을 할 순 없겠지만 4문제를 기준으로 3문제 정도를 풀면 다소 합격 안정권이라 생각하면 되지 않을까 생각한다.

사실 어느 코테나 75% 정도면 합격권이긴 하지만 말이다.....

2차 코테를 볼 때까지 이틀의 시간이 남았지만 사실 SSAFY 강의도 듣고 공채 시즌이기에 지원서도 작성하고 강의에서 부족한 부분을 복습하다 보니 특별히 알고리즘을 위해 공부를 할 시간은 거의 없을 것 같다.

2차도 마찬가지로 평소 실력대로 보되 트리에 관한 문제만 한 두 개 정도 익히고 시험을 보도록 해야겠다. 

https://www.acmicpc.net/problem/16928

문제 풀이

전형적으로 그래프 탐색 이론인 BFS(너비 우선 탐색)를 이용하면 쉽게 풀리는 문제다.

다만 보편적인 그래프 탐색은 2차원 배열에서 인덱스 접근을 통해 4방 혹은 8방 탐색을 하며 가장 가까운 Target Node를 찾지만 이번 문제는 1번부터 100번까지 각 노드를 번호로 구분할 수 있는 점, 1부터 6까지 적혀있는 주사위를 던져서 옮긴다는 점에 착안하여 1차원 배열에서 6가지 방법을 고려하면 된다는 것을 깨달아야 한다.

이점 외에는 딱히 조심해야 할 부분이 없으므로 바로 코드를 통해 설명하도록 하겠다.

from collections import deque
edge_info=[0 for i in range(101)]
n,m=map(int,input().split())
visited=[0 for i in range(100)]
queue=deque()
for i in range(n+m):
    temp=list(map(int,input().split()))
    edge_info[temp[0]]=temp[1]

             #curr,cnt
queue.append([1,0])
while len(queue)>0:
    curr,cnt=queue.popleft()
    if curr==100:
        print(cnt)
        break
    elif curr>=94:
        print(cnt+1)
        break
    else:
        for i in range(1,7):
            if edge_info[curr+i]==0 and visited[curr+i]==0:
                visited[curr+i]=1
                queue.append([curr+i,cnt+1])
            else:
                if visited[curr+i]==0:
                    visited[curr+i]=1
                    visited[edge_info[curr+i]]=1
                    queue.append([edge_info[curr+i],cnt+1])

1번째 줄은 deque를 사용하기 위해 모듈을 Import 하였다.

물론 이번 문제는 최대 칸이 100개 밖에 없기 때문에 애초에 사이즈가 작아서 시간 복잡도를 줄이기 위해 굳이 deque를 사용할 필요는 없었지만 막상 필요한 상황에서 참고 문서 없이 Import 하려면 까먹기 때문에 잊지 않기 위해서라도 deque를 사용하였다.

만약 deque가 무엇인지 모르는 사람들은 아래 포스팅을 통해 학습하면 될 것이다.

https://khsung0.tistory.com/14

2번째 줄부터 5번째 줄까지는 간선 정보와 방문 체크, 큐 등을 사용하기 위한 초기화 작업이다.

6번째 줄은 반복문을 통해 간선 정보를 저장하였고 11번째 줄은 1번 칸부터 시작해서 BFS를 진행하기 위해 deque에 초기화했다.

12번째 줄부터는 BFS를 구현한 코드이다.

문제에 주어진대로만 구현하면 되기 때문에 딱히 설명할 부분은 없지만 필자는 조금이라도 시간 복잡도 상으로 효율적인 코드를 구현하기 위해 100일 때는 현재 카운트 출력, 94 이상일 때는 주사위를 한 번만 더 돌리면 100이 나오므로 카운트+1 출력, 그 외의 경우에만 다시 deque에 넣도록 구현하였다.

이렇게 구현하면 매번 deque에 넣을 때도 100을 초과하는지 체크하지 않아도 되기 때문이다.

문제는 10X10의 2차원 그래프인 것처럼 나왔지만 1차원 배열로 변환하여 생각하는 게 필요한 문제였다.

https://www.acmicpc.net/problem/13458

문제 풀이

딱히 시간 복잡도나 공간 복잡도를 고려할 필요도 없이 단순한 사칙연산만 하면 충분히 통과 가능한 브론즈 문제인데 생각보다 정답 비율이 엄청 낮아서 포스팅하기로 했다.

브론즈 문제가 약 27%의 낮은 정답률을 보인다는 것은 난이도 설정이 잘못되었거나 문제에 헷갈릴만한 요소가 있어서 잘못된 방향으로 제출하여 많은 오답을 기록하기 때문이라 생각한다.

그래서 필자가 추측컨대 아마 감독관 수의 최솟값을 구해야 하는 문제에서 "총감독관은 오직 1명만 있어야 하고" 란 지문이 오히려 헷갈리게 했을 가능성이 있는 것 같다.

이 말이 총감독관은 2명 이상 있으면 안 된다고 판단하여 "0명도 가능하지 않나?" 란 생각이 들게 할 수 있는 것 같다.

따라서 "총감독관은 반드시 1명 있어야 하고" 로 바뀌었으면 단번에 맞춰서 정답 비율이 더 높진 않았을까 하는 아쉬움이 남았다.

또한 이 문제에 대해 시간 초과가 뜨는 경우가 종종 있던데 시험장의 수와 응시자의 수가 최대 100만이므로 수학 연산으로 답을 도출해야지 반복문을 통해 일일이 빼는 경우엔 절대 2초 안에 연산이 불가능하다는 것을 생각해야 한다.

방향성만 제대로 잡는다면 상당히 쉬운 문제라 서론이 길었는데 전체 코드를 통해 설명하도록 하겠다.

n=int(input())
n_cnt=list(map(int,input().split()))
b,c=map(int,input().split())
res=0
for i in range(n):
    n_cnt[i]-=b
    res+=1
    if n_cnt[i]>0:
        if n_cnt[i]%c==0:
            res+=(n_cnt[i]//c)
        else:
            res+=(n_cnt[i]//c+1)

print(res)

난이도 답게 상당히 짧고 간결한 코드가 나왔다.

4번째 줄까지는 필요한 입력을 받고 정답으로 출력할 변수를 초기화하는 코드다.

5번째 줄에서 for문으로 전체 시험장을 반복하며 반드시 총감독관이 있어야 하기에 총감독관이 감시할 수 있는 응시자 수를 빼고 res 변수를 카운트했다.

그 뒤에 만약 남은 응시자 수가 부감독관이 감시할 수 있는 응시자 수의 배수라면 나눈 몫을 카운트했고 배수가 아니라면 몫과 더불어 1만큼 더 큰 숫자를 카운트했다.

그 뒤에 카운트 한 숫자만큼 출력하면 통과할 수 있다.

단순 사칙연산 문제로 아주 쉬운 편이었지만 헷갈릴 수 있는 부분이 있어 입력과 출력 예제를 유심히 봐야 하는 문제였다.

https://www.acmicpc.net/problem/3425

문제 풀이

단순하게 주어진 기능들을 조건에 맞게 구현만 하면 되는 문제다.

각 기능들을 하나씩 보면 브론즈~실버 수준의 기능 구현이고 딱히 시간 복잡도나 공간 복잡도에 대해 고민할 필요가 없지만 아무래도 10개의 기능을 각 조건에 맞게 정확히 구현하는 부분에서 티어가 높게 측정되고 약 14%의 낮은 정답률을 보이는 것 같다.

실제로 필자도 주석을 통해 미리 구현 내용을 순서대로 적어두고 차근차근 구현하는 습관을 안 들이다 보니 다소 많은 양 때문에 헷갈리는 부분이 있어서 NameError, IndexError, UnboundLocalError 등의 런타임 에러가 났었다. 

이를 계기로 양이 많은 문제를 접하면 미리 주석을 사용해야겠다는 다짐을 하였다.

구현하는 과정에서는 딱히 어려운 부분이 없기에 전체 코드를 하나씩 따라가보며 설명하도록 하겠다.

def NUM_X(array,num):
    return array.append(num)

def POP(array):
    if len(array)==0:
        return "ERROR"
    else:
        array.pop()
        return 1

def INV(array):
    if len(array)==0:
        return "ERROR"
    else:
        temp=array.pop()
        array.append(temp*(-1))
        return 1

def DUP(array):
    if len(array)==0:
        return "ERROR"
    else:
        temp=array.pop()
        array.append(temp)
        array.append(temp)
        return 1

def SWP(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        array.append(temp1)
        array.append(temp2)
        return 1

def ADD(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        if abs(temp1+temp2)>10**9:
            return "ERROR"
        else:
            return array.append(temp1+temp2)

def SUB(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        if abs(temp2-temp1)>10**9:
            return "ERROR"
        else:
            return array.append(temp2-temp1)

def MUL(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        if abs(temp2*temp1)>10**9:
            return "ERROR"
        else:
            return array.append(temp2*temp1)

def DIV(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        op=1
        if temp1==0:
            return "ERROR"
        else:
            if temp1<0:
                temp1=temp1*(-1)
                op=op*(-1)
            if temp2<0:
                op=op*(-1)
                temp2=temp2*(-1)
            return array.append((temp2//temp1)*op)

def MOD(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        op=1
        if temp1==0:
            return "ERROR"
        else:
            if temp2<0:
                op=op*(-1)
                temp2=temp2*(-1)
            return array.append((temp2%abs(temp1))*op)

command="START"
command_array=[]
while command!="QUIT":
    command=input()
    if command=="QUIT":
        pass
    elif command=="END":
        n=int(input())
        for i in range(n):
            res="START"
            stack=[int(input())]
            for j in range(len(command_array)):
                if len(command_array[j].split())==2:
                    temp=command_array[j].split()
                    res=NUM_X(stack,int(temp[1]))
                elif command_array[j]=="POP":
                    res=POP(stack)
                elif command_array[j]=="INV":
                    res=INV(stack)
                elif command_array[j]=="DUP":
                    res=DUP(stack)
                elif command_array[j]=="SWP":
                    res=SWP(stack)
                elif command_array[j]=="ADD":
                    res=ADD(stack)
                elif command_array[j]=="SUB":
                    res=SUB(stack)
                elif command_array[j]=="MUL":
                    res=MUL(stack)
                elif command_array[j]=="DIV":
                    res=DIV(stack)
                else:
                    res=MOD(stack)
                if res=="ERROR":
                    break
            if res=="ERROR" or len(stack)!=1:
                print("ERROR")
            else:
                print(stack[0])
        input()
        print()
        command=="START"
        command_array.clear()
    else:
        command_array.append(command)

딱 봐도 여태 포스팅한 코드들과는 확연히 양에서 차이가 난다.

비록 양은 많지만 어려운 부분은 없기에 미리 겁먹을 필요는 없다.

먼저 전체적인 구성은 각 기능에 해당하는 10개의 함수를 선언하고 메인 함수에서는 입력방식대로 입력을 받은 후 필요한 경우 해당하는 함수를 호출해서 연산 결과를 사용하는 방식으로 구현하였다.

1번째 줄의 NUM_X는 인자로 받은 숫자를 스택의 가장 위에 저장(Push)하는 함수다.

3번째 줄의 POP은 스택에 아무것도 없다면 ERROR를 반환하고, 있다면 가장 위에 있는 숫자를 제거하는 함수다.

11번째 줄의 INV는 스택에 아무것도 없다면 ERROR를 반환하고, 있다면 첫번째 수(가장 위에 있는 수)의 부호를 바꿔서 저장하는 함수다. (이제 보니 굳이 pop 하지 않고 array [len(array)-1]=-1*array [len(array)-1] 이렇게 직접 접근해서 한 줄로 처리 가능할 것 같다.)

19번째 줄의 DUP는 스택에 아무것도 없다면 ERROR를 반환하고, 있다면 가장 위에 있는 숫자를 한번 더 추가하는 함수다.

28번째 줄의 SWP는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 첫 번째 숫자와 두 번째 숫자의 위치를 바꾸는 함수다.

38번째 줄의 ADD는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 첫 번째 숫자와 두 번째 숫자를 더한다.

이때 문제 조건에서 연산 결과의 절댓값이 10^9를 넘어간다면 프로그램 에러이므로 꼭 이 부분을 처리해줘야 한다.

49번째 줄의 SUB는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 두 번째 숫자에서 첫 번째 숫자를 빼면서 이때도 마찬가지로 절댓값이 10^9를 넘어가는지 체크해야한다.

60번째 줄의 MUL은 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 첫 번째 숫자와 두 번째 숫자를 곱하고 값을 체크한다.

71번째 줄의 DIV는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 두 번째 숫자를 첫 번째 숫자로 나눈 몫을 저장하는데 이때 0으로 나눠지는지, 부호는 어떻게 되는지 정확히 판단해서 구현해야 한다.

89번째 줄의 MOD는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 두 번째 숫자를 첫 번째 숫자로 나눈 나머지를 반환하는데 이때도 마찬가지로 부호와 0으로 나눠질 경우를 예외 처리해야 한다.

106번째 줄부터는 QUIT를 입력받기 전까지 반복하면서 명령어에 해당하는 함수를 실행시키면 된다.

이때 END를 입력받기 전까지 일련의 명령어를 입력받고 수행해야 하므로 명령어를 리스트에 저장해서 수행하는 것을 잊으면 안 된다.

다소 구현해야 하는 기능이 많고 예외처리를 해야 되는 부분도 많아서 각각의 구현 난이도는 쉽지만 어렵게 느껴질 수 있는 문제였다.

주석처리를 통해 차례대로 구현해야 하는 기능을 정리하는 습관을 들여야겠다.

https://www.acmicpc.net/problem/11559

문제 풀이

어렸을 때 많이 했던 뿌요뿌요(PuyoPuyo) 게임의 연쇄작용을 구현하는 문제이다.

테트리스와 비슷하지만 뿌요뿌요는 같은 색의 슬라임들이 4개 이상 연결되어있으면 터지고 빈 공간을 채운다는 점이 조금 다르다.

따라서 만약 테트리스였다면 행을 기준으로 탐색을 했겠지만 뿌요뿌요는 전체 탐색을 하면서 빈 공간이 아닐 때는 4개 이상 연결되었는지 BFS를 통해 체크하며 4개 이상인 모든 부분들을 빈 공간으로 치환하고 다시 바닥으로 정렬하는 과정을 반복해야 한다.

이때 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터지고 한 번의 연쇄가 추가된다고 하니 연쇄를 추가하는 부분을 정렬하는 과정에 위치시키면 적절할 것이다.

사실 12X6 크기의 행렬이라 상당히 크기가 작아 시간이나 공간에 대한 효율성을 따질 필요성까진 없지만 구현하는 과정에서 다소 헷갈리거나 복잡한 부분이 있었기에 문제를 세분화하여 주석을 통해 구현해야 할 기능들을 구분해놓고 구현하는 것이 도움 될 것 같다.

코드가 짧은 편은 아니라서 한눈에 들어오긴 힘들겠지만 한 줄씩 따라가다 보면 이해할 수 있을 것이다.

graph=[]
dir=[[-1,0],[1,0],[0,-1],[0,1]]
queue=[]
for i in range(12):
    graph.append(list(input()))
res=0

while True:
    check=True    #터졌는지 체크하는 변수
    visited=[[0 for i in range(6)]for j in range(12)]
    changed_col=[]
    del_queue=[]
    for i in range(12):
        for j in range(6):
            #뿌요가 존재하는 칸인 경우
            if graph[i][j]!="." and visited[i][j]==0:
                curr_char=graph[i][j]    #현재 뿌요 저장
                temp_cnt=0
                queue.append([i,j])
                visited[i][j]=1
                
                #현재뿌요와 연결되어있는 뿌요 탐색
                while len(queue)>0:
                    curr=queue.pop(0)
                    temp_cnt+=1
                    for k in range(len(dir)):
                        dy=dir[k][0]+curr[0]
                        dx=dir[k][1]+curr[1]
                        if 0<=dy<12 and 0<=dx<6 and graph[dy][dx]==curr_char and visited[dy][dx]==0:
                            queue.append([dy,dx])
                            visited[dy][dx]=1

                #연결된 뿌요가 4개 이상일 경우
                if temp_cnt>=4:
                    check=False
                    changed_col.append(j)
                    del_queue.append([i,j])
                    while len(del_queue)>0:
                        temp=del_queue.pop(0)
                        graph[i][j]="."
                        for k in range(len(dir)):
                            dy=dir[k][0]+temp[0]
                            dx=dir[k][1]+temp[1]
                            if 0<=dy<12 and 0<=dx<6 and graph[dy][dx]==curr_char:
                                del_queue.append([dy,dx])
                                graph[dy][dx]="."
                                if dx not in changed_col:
                                    changed_col.append(dx)

    if check:
        break
    else:
        res+=1
        #빈칸없게 위에 있는 뿌요들을 정렬
        for i in range(len(changed_col)):
            for j in range(10,-1,-1):
                if graph[j][changed_col[i]]!=".":
                    curr=j
                    while curr<=10 and graph[curr+1][changed_col[i]]==".":
                        graph[curr+1][changed_col[i]],graph[curr][changed_col[i]]=graph[curr][changed_col[i]],graph[curr+1][changed_col[i]]
                        curr+=1

print(res)

6번째 줄까지는 그래프를 입력받고 방향 리스트, 사용할 큐 초기화, 결과 변수를 선언했다.

8번째 줄의 while문은 더 이상 터진 뿌요들이 없을 때까지 터뜨리고 빈칸을 정렬하는 과정을 반복하는 부분이다.

check변수를 통해 터진 뿌요가 없을 경우 반복문을 탈출하고 매번 방문했는지 체크하는 visited 리스트를 초기화하도록 구현하였다.

13번째 줄부터는 전체 리스트를 반복하면서 뿌요가 존재할 경우 현재 뿌요를 저장하고 근접한 동일 뿌요들의 개수를 세서 4개 이상이라면 해당하는 뿌요들을 빈칸으로 초기화하였다.

이때 뿌요는 5종류가 있지만 변수에 현재 위치한 뿌요를 저장함으로써 종류에 대한 고려를 하지 않도록 했고 47번째 줄의 changed_col은 삭제된 뿌요가 존재하는 열을 추가하여 이후에 뿌요들을 정렬할 때 불필요한 탐색을 줄이는 방식으로 구현하였다.

53번째 줄에서 res+=1을 통해 카운트를 증가시키는데 문제에서 터질 수 있는 뿌요가 여러 그룹이라면 동시에 터지며 한 번의 연쇄가 추가되므로 다 터지고 난 뒤에 추가하도록 증가시키는 위치를 주의해야 한다.

터진 뿌요가 없다면 50번째 줄에서 반복문을 탈출하겠지만 터진 뿌요가 존재한다면 빈칸보다 위에 뿌요가 존재하지 않도록 정렬시킨 후 다시 반복문으로 돌아가면 된다.

그래프의 행을 기준으로 리스트 시작은 위, 끝은 바닥을 뜻하므로 끝부터 시작까지 역으로 오면서 뿌요를 최대한 리스트의 끝까지 정렬하는 것에 주의해야 한다.

해당 반복문이 끝나면 결과 변수인 res를 출력하면 끝이다.

그래프의 크기도 작고 특별한 알고리즘도 없이 흔한 그래프 이론으로 푸는 구현 문제였지만 구현 과정이 다소 길어지다 보니 충분히 헷갈릴 수도 있는 문제였다.

따라서 구현해야 하는 부분과 과정을 간략하게 주석으로 써놓고 차근차근 작성해 나가는 것이 실수를 방지하기 위해 중요한 것 같다.