Coder's Cattitude

Implementation (구현) 1. 피지컬로 승부하기 코딩 테스트에서 구현이란 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정 을 뜻한다. 어떤 문제를 풀든 소스코드를 작성하는 과정이 필수이며, 구현 문제 유형은 모든 코딩 테스트 문제 유형을 포함하는 개념으로 볼 수 있다. 1) Problem - Thinking - Solution 흔히 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 를 뜻한다. 생각해 낸 문제 풀이를 우리가 원하는 프로그래밍 언어로 정확히 구현해 내야하고, 이를 위해서는 프로그래밍 언어의 문법을 정확히 알고 있어야하고 문제의 요구사항에 어긋나지 않는 답안 코드를 실수없이 작성 해야 한다. 구현하기 어려운 문제 알고리즘은 간단한데 코드가 지나칠 만큼 ..

Greedy (탐욕법) 1. 탐욕법 (Greedy) 탐욕 : 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘 -> 매 순간 가장 좋아 보이는 것 을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 예외) 다익스트라 알고리즘 - 암기가 필요 그리디 알고리즘의 경우 많은 유형을 접해보고 문제를 풀어보며 훈련해야함 => 창의력 즉, 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함 => 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 출 수 있는지를 파악할 수 있어야 함 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘임 => 문제에서 가장 큰 순서대로 혹은 가장 작은 순서대로 ..

📌 풀이 문제 자체는 어렵지 않았지만, 좌표를 행렬에 대입해서 생각할 때 오류를 조금 범했다. 가로의 길이가 M이고 세로의 길이가 N인 직사각형의 경우 좌표가 (x,y)라면, 행렬의 경우 matrix[y][x]와 같다. 좌표를 행렬에 대입해서 생각하면, x좌표는 열, y좌표는 행이 되는 것이다. 그래서 아래 그림처럼 N행 M열인 행렬 (가로 M 세로 N인 행렬)을 transpose 시켜서, M행 N열인 행렬로 바꿔서 풀었다. 이렇게 행렬을 바꿔놓으면 별 문제 없이 코드가 작동하는 것을 알 수 있다. 🔑 python 코드 # 유기농 배추 import sys from collections import deque input = sys.stdin.readline T = int(input()) def bfs(x,..

📌 풀이 이 문제는 어디서부터 시작해야하는 지 나와있지 않기 때문에, NxN을 모두 다 돌 수 있도록 BFS로 풀었다. DFS로 풀어도 풀리지만 BFS로 푼 문제가 몇 개 없어서 그냥 BFS로 풀어봤다. 시간이 나면 DFS로도 풀어봐야겠다. 그래프에서 상하좌우로 이동할건데, 0행, N-1행, 0열, N-1열만 다르게 조건을 주기 싫어서 padding을 넣었다. 그래서 NxN가 아니라 (N+2)x(N+2) 그래프리고 패딩값들은 모두 0으로 채워넣었다. 문제에서 주어지는 값들을 graph에 저장하고, 만약 1이라면 BFS를 실시하고, 아니면 그냥 넘어가도록 했다. bfs에서도, 현재 위치에서 갈 수 있는 좌표들을 queue에 넣어놓고, queue가 다 빌 때까지 탐색을 진행하여 단지에 속하는 집의 수를 re..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 문제를 너무 어렵게 생각했던 것 같다. 그냥 진짜 그래프 문제였다. 신기하게 풀어본다고 이것저것 시도하다 그냥 DFS로 풀었다. 문제에서 주어지는 간선들을 graph에 저장하고, DFS로 1부터 시작해서 재귀함수를 써가며 풀었다. parents = [0, 0, 0, 0, 0, 0, 0, 0] graph에 저장된 것들을 적어본다면 graph[1] = [6, 4] graph[2] = [4] graph[3] = [6, 5] graph[4] = [1, 2, 7] graph[5] = [3] graph[6] = [1,3] graph[7] = [4] 이다. dfs(1)을 해주면 graph[1]에서 첫번째 값인 6의 parents가 0인지 확인하고, parents[6]을 1..

🔒 문제 ⌨ 입력 🖨 출력 📍 제한 📚 예제 📌 풀이 이 문제는 union-find의 기본 문제가 아닐까 싶다. 그냥 보자마자 어,, union-find다 라는 생각이 들었다. 문제를 푸는 것 자체는 안어려웠지만, error가 많이 나서 보니까 1. Recursive error 이 오류는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어져서 발생한다. sys.setrecursionlimit(10**6) 을 사용해서 Python이 정한 최대 재귀 깊이를 변경해서 풀어준다. 2. memory 초과 이건 pypy로 했더니 발생했다. 해결법은 딱히 찾지 못했다. 3. 시간초과 root 함수를 짤 때 처음엔 root를 찾기만 했지, 찾으면서 root값들을 변경해주는 것이 없었다. 그래서 root를 찾..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 1. 책의 위치를 받은 배열을 음의 정수(minus_loca)와 양의 정수(plus_loca) 두 개의 배열로 나눈다. 2. 음의 정수들을 배열에 넣을 때, 계산하기 편하게 -1을 곱해서 넣는다. 3. -1을 곱한 음의 정수와 양의 정수를 내림차순으로 배열에 넣는다. => 가장 큰 보폭인 애들끼리 묶어서 최대한 많은 양을 옮기기 위해 4. 음의 정수와 양의 정수 각각을 M칸씩 건너 뛰면서 새로운 배열(minus_step, plus_step)에 저장한다. => 최대로 들 수 있는 책의 개수만큼 옮길 책들의 묶음을 나눠줌 5. steps를 계산해준다. 5-1. minus_step의 인수 수가 0 인 경우, plus_step의 가장 큰 값은 steps에 한번만 더해..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 이 문제는 조합을 사용해서 풀었다. 고등학교 확률과 통계 조합 단원에서, 집합 X에서 집합 Y로의 함수를 정의 할 때 조건 x1 < x2 이면, f(x1) < f(x2)를 만족하는 함수의 개수를 구하는 문제가 있다. 이 다리 놓기 문제는 다리 끼리 겹쳐지는 상황이 생기면 안되기 때문에 위의 그림에 적어놓은 것 처럼 저 조건을 사용해서 조합으로 풀 수 있다. 🔑 python 코드 #다리 놓기 import sys input = sys.stdin.readline T = int(input()) arr = [[int(i) for i in input().split()]for _ in range(T)] #조합 def nCr(n, m): ans = 1 d = 1 for i ..

🔒 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다. 신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가? ⌨ 입력 첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다. 두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다...

🔒 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 2..