Redddy's Devlog

🔈 문제 안녕하세요~ 저는 오늘 다이나믹 프로그래밍(동적 계획법)을 설명하기 위해 등장한 욱제예요! 다이나믹은 이름이 엄청 거창하지만 사실 이름에 비해 개념은 간단하답니다. 다이나믹의 기본 아이디어는 바로 이전에 계산한 값을 사용해서 (= 이미 계산된 값을 사용해서, 어려운 말로 메모이제이션 한다고 해요) 반복되는 똑같은 연산 횟수를 줄이는 거예요. 예를 들어서, 5번째 피보나치 수열을 구하는 F(5)의 동작 과정을 살펴볼게요. 같은 함수가 불필요하게 많이 호출되는 것을 볼 수 있죠? F(2)와 F(3)을 미리 구해놓고 F(4)를 구할 땐 미리 구해둔 F(2)와 F(3)의 값을 이용하면 불필요한 호출을 줄일 수 있어요. 조금 엄밀하게 이야기 해볼게요. 수학적으로 피보나치 수열은 F(n) = F(n-1) ..

🔈 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇..

🧩문제 해석 수빈이와 동생은 일직선 상에 위치하고 수빈이는 1초에 x-1, x+1, 2*x 로 이동할 수 있다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하면 된다. 📚풀이 BFS를 사용하여 풀었다. 방문을 체크하기 위한 visited 리스트를 생성하였다. 큐에 현재 위치와 현재 누적 초를 같이 저장하여, 이동 할 때마다 초를 누적 시켜주었다. 이동 가능 위치는 arr 리스트로 만들어주었고, arr 요소 중 아직 방문 하지 않았고, 0~100000 사이 값이라면 방문하고 큐에 삽입 하였다. 그렇게 하여 k와 같은 값을 찾으면 현재 누적 초를 출력하였다. 만약 시작부터 동생과 수빈이가 같이 있다면 이동할 필요 없기에 0을 출력..

🧩문제 해석 a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야한다. k와 n이 주어질때 k층의 n호에는 몇 명이 살고 있는지 출력하면 된다. 층은 0층부터 있지만 입력 범위는 1

🧩문제 해석 F = 스타트링크 건물 층의 총 계수 S = 현재 강호의 위치 G = 스타트링크의 위치 U = 위로 올라가는 엘레베이터 층의 간격 D = 아래로 내려가는 엘레베이터 층의 간격 위 사항들이 주어졌을 때, 현재 강호의 위치에서 스타트링크의 위치로 엘레베이터로 가려 할 때, 누른 버튼의 최소값을 출력하는 문제이다. 만약 도달할 수 없다면, 계단 이용하라는 문장을 출력한다. 모든 층을 돌아다닐 필요가 없고 목표층에 도달하면 엘레베이터를 멈추면 되니까 BFS가 효율적이다. 📕 풀이 BFS로 풀었다. 이동할 수 있는 층은 [현재 위치 + U, 현재 위치 -D] 를 통해 유추하였고, 이 데이터가 F 안에 있고, 방문한 적이 없다면, 그 층으로 방문하였다. 💻 코드 from collections impor..

🧩문제 해석 체스 판의 크기와 현재 나이트의 위치 그리고 목표 위치가 주어졌을 때 최소 이동 횟수를 출력하는 프로그램! 📕 풀이 나이트의 이동 가능 경로는 다음과 아래의 그림과 같다. 최소 이동 횟수를 구하려면 이전에 방문 했던 곳은 지양한다. 그리고 체스판에서 벗어나는 위치도 제외한다. 이 두가지를 지키면서 BFS 탐색을 하였다. 칸을 모두 방문하는 것이 아니라 목표 위치에 도달하면 탐색을 멈출 것이기에 DFS 보다 BFS가 더 효율적이다. 💻 코드 import sys from collections import deque input = sys.stdin.readline # 나이트 이동 경로 dx = [-2,-1,1,2,2,1,-1,-2] dy = [1,2,2,1,-1,-2,-2,-1] def bfs()..

🧩문제 해석 이제 이런 문제들을 딱 보면 그래프 관련 문제라는 걸 바로 알아차릴 수 있게 되었다. '빙산 한 덩이가 주어졌을 때'가 조건에 들어가있으니, 무조건 빙산은 주어진다. 그러면 이제 빙산에서 얼음의 위치와 그 얼음 주위 환경을 살피면 된다. 그리고 빙산이 쪼개졌는지 BFS를 통해 확인한다. 🔉 풀이 전 잡담 앞서 말한 문제 해석을 알고리즘으로 구현해내는데에는 성공했다. 첫번째 제출에는 런타임 에러(RecursionError)가 발생했다. 이는 재귀함수가 너무 깊이 들어갈 경우 발생한다. 이땐 당황하지 말고 sys 모듈을 불러와 sys.setrecursionlimit(n) 을 적어주면 된다. 여기서 n은 최대 깊이를 의미한다. sys.setrecursionlimit(10**4) 을 넣어줌으로써 런..

🧩문제 해석 떡 하나 주면 안잡아 먹지!~ 에서 아이디어를 얻은 문제 같다 ㅋㅎㅎ 문제가 재밌었다. 호랑이가 오늘 먹을 떡의 갯수는 1일전하고 2일전에 얻은 떡을 더한 갯수이다. 이 글을 보면 바로 피보나치 수열이라는 것을 눈치챘을 것이다. n번째 날 먹은 떡에 갯수 k가 주어졌을 때 첫째날하고 둘째날에 먹은 떡에 갯수를 출력하는 문제이다. 📕 풀이 피보나치라는 것을 파악하자 문제 풀기는 쉬워졌다. 첫째날에 먹은 떡의 갯수가 a, 둘째날에 먹은 떡의 갯수를 b라고 할 때 아래의 표를 살펴보자. 날짜 1 2 3 4 5 6 떡의 갯수 a b a+b a+2b 2a+3b 3a+5b 첫째날에는 a개, 둘째날에는 b개, 셋째날에는 첫째날과 둘째날을 더한 a+b개를 먹었다. 그리고 네째날에는 둘째날과 셋째날을 더한 ..

🧩문제 해석 갖고 랜선들을 k개의 같은 길이의 랜선으로 자르되, 자른 랜선쪼가리들은 다시 사용할 수 없다. 이때 만들 수 있는 최대 길이의 랜선을 구하는 문제이다. 📕 풀이 숫자 범위가 심상치 않다. 갖고 있는 랜선의 수가 백만개이고, 랜선이 길이는 2^31-1 보다 작은 자연수이다.ㅎ 일반적으로 접근했다가는 시간초과날 것이 분명하다. 이 문제는 이분탐색으로 풀어야 한다. 첫번째 아이디어! 가지고 있는 랜선중 최소값을 찾는다. 최소값 랜선을 end 값에 두고 이분탐색을 한다. 탐색 값들을 리스트에 저장하고, 최종적으로 그 리스트의 최대값을 출력한다. 최소값랜선을 end 값에 둔 이유는 최대값랜선을 end 값에 둔다 하여도 결국에는 최소값랜선에 올 것이라고 생각했다. 물론 맞는 말이긴 하다. 그러나 생각하..

🧩문제 해석 채팅방에서 사용한 임티갯수를 출력하면 되는 문제였다. 사람들은 새로운 사람이 들어왔을 때 임티를 사용하고 그 다음은 일반 대화를 이어나간다. 즉, 새로운 들어왔을 때 사용한 임티 갯수를 전부 더해주면 되는 문제이다. 📕 풀이 dict() 자료형을 사용하여 문제를 풀었다. 새로운 사람이 들어오면 dict()의 값들을 리셋해주었다. 💻 코드 import sys input = sys.stdin.readline cnt = 0 # 임티갯수 변수 user = {} # 이름과 임티사용을 확인할 변수 for i in range(int(input().rstrip())): # 채팅방의 기록수만큼 for문을 돌린다 # 채팅내용입력받음 s = input().rstrip() # 새로운 사람이 들어왔을때 if s =..