Coder's Cattitude

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..

2023년은 그냥 알 수 없는 해 였다. 의욕이 없고, 아무것도 하고싶지 않고, 모든걸 그냥 다 포기하고 싶었다. 옆에서 계속 챙겨주고 꺼내주던 사람들이 아니었으면 그냥 반년을 버렸을 수도 있었을 것 같다. 짜꿍, 현똥, 떠연, 믕디, 몌딘, 미디, 셍, 유떤, 난니, 찌니, 쏘히, 응됴, 으니에게 감사하다. 죽을거 같다 싶을때 기가막히게 연락와서 멘탈 회복시켜주고 갔다. 내 자양강장제들 이제 너넨 완벽하게 내꺼다. 아무한테도 안줘 스트레스로 위에 구멍이나고, 심안정제도 처방받으며, 인생이란 무엇인가를 많이 고민했다. 이 글을 쓰는데 유명 연예인의 비고 소식을 봤다. 사람들은 자기가 보고 싶고 믿고 싶은대로 믿는다. 아무리 아닌건 아니라해도 안 믿고 당사자에게 묻기보다는 자기들끼리 말을 나누고 결론을 낸..

🔒 문제 ⌨ 입력 🖨 출력 📍 제한 📚 예제 📌 풀이 이 문제는 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..