꾸준히 개발하기

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

그래프 내 연결되어 있는 그룹이 몇개인지 묻는 문제다. BFS든 DFS든 돌리면서 방문 정보를 저장해주는 visited 배열에서 False인 요소가 존재하면 그룹 수 +1 해주고 다시 BFS/DFS를 돌리면 되는 문제다. visited 배열의 모든 값이 True가 되면 총 그룹 수를 출력해주면 된다.

나는 BFS로 접근해서 풀었다. 이런식으로 그래프가 끊어져 있을 때 어떻게 풀면 될지 고민헀는데 이 문제같은 경우에는 노드 번호가 1부터 N까지 정해져 있어서 수월했다. 

코드는 다음과 같다.

import sys

input = sys.stdin.readline

from collections import deque


def bfs(start):
    visited[start] = True
    queue = deque()
    queue.append(start)

    while queue:
        x = queue.popleft()
        for y in graph[x]:
            if not visited[y]:
                visited[y] = True
                queue.append(y)


N, M = map(int, input().split(" "))
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
for _ in range(M):
    u, v = map(int, input().split(" "))
    graph[u].append(v)
    graph[v].append(u)

cnt = 0
for i in range(1, N + 1):
    if not visited[i]:
        cnt += 1
        bfs(i)

print(cnt)

2년동안 발전은 했는데 .. 2년 내내 했으면 눈부신 발전 덕분에 취업을 이미 하지 않았을까 하는 생각이 눈물이 앞을 가리는 문제였다.

이 난이도가 실버 2? 거짓말이라고 해달라....

재귀함수는 문제를 이해하고 점화식 도출해서 코드로 구현하는 그 일련의 과정이 감이 안오면 정말 손도 못 대겠더라. 끙끙 고민하다가 결국 다른 사람의 풀이를 보고 이해했다.

문제를 살펴보면 원반 N개를 해결하려면 원반 N-1개인 상황을 해결해야 한다. 즉, 다음의 과정을 도출해낼 수 있다.

1. N개의 원반이 주어지면 위에서부터 N-1개의 원반을 두번째 기둥으로 옮김
   현재 상태 -> 기둥 1에는 제일 큰 N번째 원반이 남아있으며 기둥 2에는 N-1개의 원반이 있다.
2. 기둥 1의 N번째 원반을 목표 지점인 기둥 3로 옮긴다
3. 기둥 2에 남아있는 N-1개의 원반을 목표 지점인 기둥 3로 옮기면 된다.

문제에서 20이 넘어가면 횟수만 출력하라 했는데, 재귀의 깊이가 너무 깊어질 수 있어 20이 넘어가면 단순히 값만 출력하라고 하는 듯 하다. 원판이 n개 일 때, 2^n -1(=2의 n승 빼기 1)번의 이동으로 원판을 모두 옮길 수 있다. 

이를 코드로 구현하면 다음과 같다.

import sys

input = sys.stdin.readline


# start -> end로 원반 disc개 이동
def hanoi(start, mid, end, disc):
    if disc == 1:  #
        print(start, end)  # 출력
    else:
        hanoi(start, end, mid, disc - 1)  # 기둥1 -> 기둥2 (n-1개를 잠시 이동)
        hanoi(start, mid, end, 1)  # 가장 큰 원반 기둥1 -> 기둥 3
        hanoi(mid, start, end, disc - 1)  # 기둥2 -> 기둥3


N = int(input())

print(2 ** N - 1)
if N <= 20:
    hanoi(1, 2, 3, N)

재귀... 재귀.... 이름도 귀신같아가지고 아주 무서운 놈이다 ... 

이번주는 KT 인적성과 코테 공부를 병행해야 한다. 심지어 강의 준비까지 해야된다. 바쁘다 바빠.

3. 재귀함수와 정렬

https://www.acmicpc.net/workbook/view/9000

22.10.17 (월)

재귀함수는 너무 어렵다. 점화식을 도출하고 꼭 멈출 수 있는 조건을 적어서 타고 타고 들어가야 되는데 말이다...

22.10.18 (화)

지난주에 끝내지 못했던 수학 챕터를 마무리했다.

https://www.acmicpc.net/workbook/view/8997

22.10.10 (월)

2. 자료구조 

https://www.acmicpc.net/workbook/view/8999

22.10.10 (월)

22.10.11 (화)

22.10.12 (수)

22.10.13 (목)

갑자기.. 카카오 서버가 터지면서 티스토리까지 접속이 안되는 불상사가 발생했다...

22.10.14 ~ 22.10.17 동안 week2를 모두 해결했다.

풀이 참고한 문제 : https://www.acmicpc.net/problem/2812 (추후 꼭 다시 풀어볼 것!)

입출력 기본 문제들

(https://plzrun.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4PS-%EC%8B%9C%EC%9E%91%ED%95%98%EA%B8%B0참고)

22.10.7 (금)

백준 : 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992

아래 커리큘럼 시작

https://dev-dain.tistory.com/155

1. 수학

(합공식, 피보나치수, 약수, 최대공약수, 최소공배수, 소수, 조합과 순열)

https://www.acmicpc.net/workbook/view/8997

22.10.7 (금)

22.10.8 (토)

22.10.9 (일)

(티스토리야 반갑다... 카카오 서버가 터지는 사태 이후로 티스토리 접속이 원활하지 않아서 지난주 금요일 이후로 오랜만에 접속해서 TIL을 올리는 것 같다!)

이 문제는 사실 꽤 정답까지 근접했던 것 같은데 마지막 한방이 부족했다. 순간순간에 어떤 자료구조를 쓰는게 효율적인지 아직 손에 익지 않은 탓이겠지.

문제에서 원하는 좌표 압축이란 i번째 수보다 작은 서로 다른 좌표의 개수를 Xi`에 저장하는 것이다. 즉 중복을 허용하지 않는 본인보다 작은 요소의 개수를 세어주면 된다.

• 중복 허용 X -> set() 으로 변환하여 중복 제거
• 본인보다 작은 요소의 개수 : sorted()하여 정렬한다. 이때 인덱스값이 해당 요소보다 작은 값의 개수이다.

여기까지는 어렵지 않게 떠올렸다. 다만 인덱스값과 해당 데이터를 매번 입력받은 data를 돌면서 index() 함수로 찾았다는게 문제였다..^^ 이럴 필요가 전혀 하등! 없다. 그러나 머리가 왜인지 안 돌아가서... 살짝 구글링했다. 아쉽다... 

dictionary 자료구조를 사용하여 (key:value) - (값 : 인덱스) 형태로 저장해준 뒤 data를 돌면서 해당 자료를 dictionary에서 찾으면 된다. 그래야 정답을 출력할 때 시간초과가 안 난다. 

코드는 다음과 같다. 마지막은 띄어쓰기 때문에 한칸 빼고 출력해줬다.

import sys

input = sys.stdin.readline

N = int(input())

data = list(map(int, input().split(" ")))

sorted_data = sorted((set(data)))

dictionary = {sorted_data[i]: i for i in range(len(sorted_data))}

answer = ""
for d in data:
    answer += str(dictionary[d]) + " "

print(answer[:-1])

그 순간에 적합한 자료구조와 로직을 떠올리는 건 연습으로 얼마든지 해낼 수 있다고 믿는다. 꾸준히 꾸준히!

2022.10.15 10시 ~ 12시, 총 2시간동안 치뤄졌던 시험이다. 120분에 12문제가 나온다고 명시되어 있어 어떻게 코테를 10분에 1문제씩 풀지 이랬는데 코테 2문제 객관식 10문제의 유형이었다. (그간 KT 코테 검색해봤을 때 이런건 없었던 것 같은데...!)

문제 유출은 금지되어 있다고 하여 간략하게만 적어본다.

[ 코테 ]

1. 트리 (코드 구현)

2. 문자열 (코드 구현)

[ 객관식 ]

3 ~ 10. SQL, CS, 언어별 문제, 자료구조 다양하게 출제

난이도는 ... 모르겠다. 일단 테스트케이스는 다 통과하게 코드를 짜서 제출했는데, 객관식에서 다 깎아먹었을 듯 하다^^

일단 다음 KT 신입 코테가 일주일 뒤니 또 그것도 바짝 준비해야겠다.

문제를 이해하면 다음과 같다.

높이가 다른 탑이 일렬로 있고, 모든 탑은 자기 기준 왼쪽으로 레이저를 송신한다. 수신 가능한 탑은 해당 레이저가 발사된 탑보다 높이가 크거나 같아야 하며, 레이저는 가장 먼저 닿은 탑 1개에서만 수신된다.

처음에 한 1시간정도 계속 뒤에서 접근해가면서 봐서 끙끙 앓았다. 앞에서 어느 탑이 수신 가능한지 알 수 없는데 뒤에서부터 본 게 잘못이었다.

자고 일어나서 다음날 다시 앞에서부터 보는 방향으로 생각의 방향을 틀었다. 앞에서부터 차근차근 보면 된다. 수신 가능한 탑을 배열로 저장하고, 최신순으로 꺼내보면 된다. 

1. 첫번째 탑 : 이전 탑이 없으므로 수신 가능한 탑 배열에 (높이, 탑번호) 넣어주기만 하면 된다.
2. 두번째 탑 : 수신 가능한 탑 배열에서 pop() 하여 높이를 비교한다. pop() 한 요소의 데이터는 prev_를 붙여 저장했고 현재 탑의 데이터는 now_를 붙여 저장했다.
   • prev_h > now_h : prev_i번째 탑이 현재 레이저를 수신 가능한 경우.
     pop()한 데이터를 다시 수신가능한 탑에 append해줘야 한다. 현재 탑 데이터도 수신 가능한 탑 배열에 append
   • prev_h == now_h : prev_i번째 탑이 현재 레이저를 수신 가능한 경우.
     높이가 같은 경우 최신 탑이 먼저 수신하게 되므로 현재 탑의 데이터만 수신 가능한 탑 배열에 append
   • prev_h < now_h : prev_i번째 탑이 현재 레이저를 수신 불가능한 경우.
     pop()한 데이터를 저장해줄 필요 없이 넘어간다.
     만약 모든 데이터를 다 훑었음에도 수신 가능한 탑이 없다면 현재 탑의 데이터를 수신 가능한 탑 배열에 append해주고 넘어간다.
3. i번쨰 탑 : 뒤와 동일한 로직이다.

이렇게 풀어주니 별 문제 없이 통과했다!

코드는 다음과 같다.

import sys

input = sys.stdin.readline

N = int(input())
Heights = list(map(int, input().split(" ")))

# 맨 앞 탑은 수신 불가능하므로 미리 저장하고 고려X
answer = [0]
available_tower = [(Heights[0], 1)]  # (높이, 탑번호)

for i in range(1, len(Heights)):
    now_h, now_i = Heights[i], i + 1

    received = False
    while len(available_tower) > 0:
        prev_h, prev_i = available_tower.pop()
        # 수신 가능한 탑 발견
        if prev_h > now_h:
            available_tower.append((prev_h, prev_i))
            answer.append(prev_i)
            available_tower.append((now_h, now_i))
            received = True
            break
        # 수신 가능한 탑 발견
        # 높이가 같은 경우 최신 탑이 더 우선이므로 최신 탑 데이터만 저장
        elif prev_h == now_h:
            answer.append(prev_i)
            available_tower.append((now_h, now_i))
            received = True
            break
        else:
            continue
    # 모든 탑이 다 수신 불가능한 경우
    if received == False:
        available_tower.append((now_h, now_i))
        answer.append(0)

print(" ".join(map(str, answer)))

현재 접근한 방법으로 문제가 안 풀릴때 빠르게 다른 방향으로 생각의 전환을 해보는 것이 중요하다고 어제 깨달았고, 오늘 직접 전환해보니 실제로 문제가 풀려서 매우 좋다. 골드 V 문제도 풀리기 시작하는 걸 보니 늘긴 느나보다.