백준

[백준 - Python] 2579번 : 계단 오르기

🌱 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 💡 설명 필자는 해당 문제를 BFS로 해결하려 했으나 채점 7% 에서 메모리 초과가 발생하였습니다. 아무리 n이 300이라고 해도 주어진 메모리가 128MB인 상황에서 메모리를 많이 요구하는 BFS로 문제를 해결하기에는 문제가 있어 보였습니다. 다음 방법으로 다이나믹 프로그래밍(DP)로 접근을 시도하였습니다. Memoization 기법을 통해 이전에 구한 최적값(해당 층까지 구한 최대 스코어)을 dp..

[백준 - Python] 1697번 : 숨바꼭질

🌱 문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 💡 설명 해당 문제는 BFS(너비 우선 탐색) 알고리즘으로 해결할 수 있는 문제입니다. 만약, BFS가 아닌 DFS(깊이 우선 탐색)를 사용하여 문제를 해결하려고 하면 시간초과가 발생합니다. 해당 문제에서 BFS와 DFS 사용의 차이를 생각해본 결과는 다음과 같습니다. DFS는 찾고자 하는 방향에 노드가 있으면 매우 빠른 속도로 찾을 수 있으나, 반대로 찾고자 ..

[백준 - Python] 2839번 : 설탕 배달

🌱 문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 💡 설명 해당 문제는 다이나믹 프로그래밍 또는 그리디 알고리즘을 요구하는 문제입니다. 우선 다이나믹 프로그래밍으로 풀이가 가능한지 확인하기 위해서는 2가지 조건이 있습니다. 1. 최적 부분 구조 (Optimal substructure) 2. 중복 부분 문제 (Overlapping subproblems) 즉, 큰 문제 상황을 작게 나누어서 해결하고자 할 때, 중복되는 상황이 발생 하며, 작게 나눠진 ..

[백준 - Python] 2671번 : 잠수함식별

🌱 문제 https://www.acmicpc.net/problem/2671 2671번: 잠수함식별 입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고 www.acmicpc.net 💡 설명 해당 문제는 정규식을 사용하면 LOC를 최소화 할 수 있는 문제입니다. 사실상 설명에 정규식을 표현해주는 문자가 있어서 골드V 문제에 비해 비교적 쉽게 해결할 수 있었습니다. 문제를 읽어보면 기호 ~ 는 최소 1번 이상 반복된다는 것을 의미합니다. 1~ = {1, 11, 111, 1111, ..., 1...1, ...} (01)~ = {01, 0101, 010101, 010101..

[백준/파이썬] 1004번 문제 '어린 왕자'

c 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 문제 어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다. 빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 ..

[백준/파이썬] 1003번 문제 '피보나치 함수'

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)..

[백준/파이썬] 1002번 문제 '터렛'

https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 문제 조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다. 이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다. 조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r..

[백준/파이썬] 1000번 문제 'A+B'

https://www.acmicpc.net/problem/1000 1000번: A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 A와 B가 주어진다. (0 a and a b and b < 10)): a, b = input().split() a = int(a) b = int(b) print(int(a) + int(b)) 우선, 값을 입력받을 변수로 a와 b를 -1로 선언 및 초기화해준다. 그리고 문제 ..