백준 클래스 4, 골드 2 달성! and 문제 후기

백준 클래스 4, 골드 2를 달성했다.

뿌듯하다.

그래도 골드 문제는 여전히 힘들다.

코딩 테스트 합격을 위해선 아직 갈 길이 머니 더 열심히 해야겠다.

…

일부 기억나는 (최소 두 번 이상 틀리거나, 웰 노운, 혹은 재밌는) 문제 복기.

RPG Extreme

• 플래티넘 1
• 구현, 시뮬레이션
• 던전 트랩을 해쳐나가고 던전 보스를 처치하는 텍스트 RPG 스타일 문제
• 가장 시간이 오래 걸린 빡구현 문제
• 테케가 많아도 디버깅이 힘듦 (트랩칸 표시 처리, 악세 간 시너지, 엔딩 처리 순서 등)
• 시간이 제한된 사항이면 플래1로 책정될만 하나, 시간을 많이 쓰면 난이도 수직하강한다고 생각함
• 별다른 알고리즘을 요구하지 않음. 게임을 만드는 것 같아 문제가 재밌음
  
  

큰 수 만들기

• 플래티넘 5
• 그리디, 정렬
• 배열의 수를 조합해서 가장 큰 수를 구하는 문제
• 각 요소들 간 대소를 비교해 정렬해주는 발상만 있으면 플래치고 쉬운 문제 (증명하려면 어렵다고 함)
• 프로그래머스 2레벨 문제에서 풀어봐서 금방 풀었음
  
  

버블 소트

• 플래티넘 5
• 자료 구조, 정렬, 세그먼트 트리, 분할 정복
• 버블 소트 시 swap 횟수를 알아내는 문제
• 수의 범위가 크므로 세그먼트 트리, 펜윅 트리 등 사용 필요
• 나는 위 알고리즘을 안 보고 쓸 줄 몰라서, 시간복잡도 O(NlogN)인 머지 소트로 풀면 되지 않을까 해서 풀었는데 맞았음
  
  

구간 합 구하기

• 골드 1
• 자료 구조, 세그먼트 트리
• n개의 수에서 특정 구간의 합 구하기
• 세그먼트 트리 기본 문제
• 세그먼트 트리를 안 보고 쓸 정도로 익혀서 품 (패턴을 외워서 나중에 까먹음. 다시 공부 예정)
  
  

폭탄 던지는 태영이

• 골드 2
• 그리디, 누적합
• 2차원 배열의 땅에 던져진 폭탄의 개수를 구하는 문제
• 2차원 배열 누적합을 모른 상태에선 풀이의 공식을 이해하기 어려웠던 문제
• 누적합을 알면 공식을 유도할 수 있는 문제라고 생각
  
  

게임

• 골드 2
• 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 깊이 우선 탐색
• 2차원 배열 그래프에서 요소에 적힌 숫자만큼 4방향으로 이동하여, 최대 이동 가능 횟수를 구하는 문제
• dp + dfs 혼합 유형 문제
• 시작점부터 깊이를 갱신하는 것이 아니라, 끝점까지 가서 회귀할 때 이전 노드에서 다음 노드의 횟수를 더해주는 아이디어
• 횟수를 더해줄 때 dp 사용
  
  

가장 긴 바이토닉 수열

• 골드 3
• 다이나믹 프로그래밍
• 어떤 수열의 부분 수열 중 가장 긴 바이토닉 수열을 구하는 문제
• dp 웰 노운 패턴의 가장 긴 증가하는(감소하는) 수열 활용
• 앞뒤로 dp를 활용하는 발상이 어려웠던 문제
• 반대로 발상만 있으면 쉽게 풀리는 문제
  
  

트리의 지름

• 골드 3
• 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색
• 트리의 지름을 구하는 문제
• 임의의 노드에서 가장 먼 노드를 찾은 후 해당 노드에서 가장 먼 노드를 찾으면 트리의 지름이 되는 공식 활용
• 위 알고리즘을 모르면 시간 내 풀기가 어려움
• 반대로 위 알고리즘만 익히면 매우 쉽게 풀이 가능
  
  

소코반

• 골드 3
• 게임 소코반 플레이 현황을 구현하는 문제
• 구현, 시뮬레이션
• 별다른 알고리즘이 필요하지 않음
• 게임을 만드는 것 같아 문제가 재밌음
  
  

나머지 합

• 골드 3
• 수학, 누적 합
• 배열의 연속된 부분 구간의 합이 m으로 나누어 떨어지는 구간의 개수를 구하는 문제
• 풀이 아이디어가 어려웠던 문제
• 입력과 동시에 구간합을 구할 때, 나머지가 같은 값을 map으로 구해주고,
• 나머지가 같은 수 중 2개를 선택(nC2)해서 부분합 시 나누어 떨어지는 알고리즘을 이용
• 알고리즘을 모르면 풀기 어려운 듯
  
  

오큰수

• 골드 4
• 자료 구조, 스택
• 배열의 특정 요소의 오른쪽에 있으면서, 요소보다 큰 수이며, 그 중 가장 왼쪽에 있는 수를 구하는 문제
• 배열 끝부터 스택에 넣어주면 배열 왼쪽으로 이동하며 스택 top에 있는 수와 비교
• 구현은 간단하나 발상하기 쉽지 않았음
  
  

벽 부수고 이동하기

• 골드 4
• 그래프 이론, 그래프 탐색, 너비 우선 탐색
• 2차원 배열 0, 1 적힌 그래프에서 1을 한 번만 넘어갈 수 있으면서, 목적지까지 최단 거리를 구하는 문제
• 벽을 부수지 않은 세계와 벽을 부순 세계로 나뉘는 분기가 흥미로움
• 3차원 배열 dp(혹은 2차원 dp 2개)로 품
• 벽 부수지 않은 세계에서 부순 세계로 넘어갈 때 처리( [][][n-1] = [][][n] + 1 )를 잘못해 디버깅이 오래걸렸음
  
  

LCS

• 골드 5
• 다이나믹 프로그래밍
• 두 수열의 공통 부분 수열 중 가장 긴 것을 찾는 문제
• LCS(최장 공통 부분 수열) 알고리즘을 모르면 풀기 어려웠음
• 알고리즘 알면 그냥 기본 dp 문제
  
  

평범한 배낭

• 골드 5
• 다이나믹 프로그래밍, 배낭 문제
• 배낭에 담을 수 있는 무게 내에 최대 가치값을 구하는 문제
• 웰 노운 DP 0-1 KnapSack 기초 문제
• 중복 없이 수를 선택해야 해서 2차원 배열 dp 이용해서 각 kg마다 이전(i - 1) 결과와 비교해서 최대값 산정
• DP 문제는 풀 때마다 새로운 듯..
  
  

N-Queen

• 골드 5
• 브루트포스 알고리즘, 백트래킹
• 크기가 n*n인 체스판 위 퀸 n개를 서로 공격할 수 없게 놓는 문제
• 웰 노운 백트래킹 문제
• 1차원 배열만 써서 “arr[행] = 열” 발상이 1차적으로 어려우며,
• 유망(혹은 유효)한 자리인지 판단하는 과정, 즉 현재 퀸 위치가 이전 각 행의 퀸 위치 i와,
• 열이 같은지 arr[i] == arr[row]
• 대각선 위치에 있는지 row - i == abs(arr[row] - arr[i]) 판단을 재귀적으로 푸는 발상
• 위 알고리즘을 모르면 풀기 어려울 듯
  
  

이중 우선순위 큐

• 골드 5
• 자료 구조, 트리를 사용한 집합과 맵, 우선순위 큐
• 우선순위 큐가 있다고 가정하고, 일련의 삽입 및 삭제 연산이 주어진 후 큐 내 최댓값과 최솟값을 출력하는 문제
• 다른 사람들과 내 풀이가 조금 달라 기억나는 문제. 난 priority_queue를 전혀 안 쓰고 map으로만 해결
• 삭제 시 원래 맵 내에 값이 있던(값이 “1”) 키였으면 값을 -1해줌. (값이 0이면 없는 것과 같은 취급)
• 코드가 간단하고 시간복잡도가 평균보다 빨라 나와 좋았음 (물론 우선순위 큐 써도 빠르게 나올 수 있음)
  
  

하노이 탑 이동 순서

• 실버 1
• 재귀
• 세 개의 장대 중 첫 번째 장대에 반경이 서로 다른 n개의 원판을 다른 탑으로 옮기는 순서를 기록하는 문제
• 웰웰웰-노ㅡㅡㅡ운 재귀 문제
• 한 번 풀어봐야 패턴을 기억함 (생전 첨보고 풀면 천재라고 생각함)
• 파생 문제로 재귀 훈련 필요(장대가 4개가 된다거나 등)