Algorithm/백준
-
[Java] 11726 2×n 타일링Algorithm/백준 2023. 8. 2. 13:46
1. 문제 📚 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2. 입출력 예 📋 ㅁㄴㅇㅁㄴㅇ 3. 알고리즘 ✅ 1. 가짜문제 정의 dp[n] := 2*n 타일에 할 수 있는 경우의 수 2. 가장 작은 문제 해결하기 3. 점화식 세우기 dp[n] = dp[n - 1] + dp[n - 2] 4. 소스코드 💻 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReade..
-
[Python] 11501 주식Algorithm/백준 2023. 2. 16. 17:37
1. 문제 📚 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 2. 입출력 예 📋 3. 알고리즘 ✅ 입력값이 큰 것을 보고 그리디인가 dp인가 생각해보다가 제일 큰 값에 팔면 최대 이익이 나오므로 -> 그리디 라고 생각하였다 처음엔 앞에서부터 차근차근 순회해가면서 하는 로직으로 짰지만 80퍼쯤에서 시간초과가 났다. 앞에서 순회하게 되면 리스트를 잘라주는 작업을 계속해주어야했다. 왜냐면 7, 6, 9, 1, 6 이라면 7, 6 은 9..
-
[Python] 15686 치킨 배달Algorithm/백준 2023. 2. 16. 17:27
1. 문제 📚 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 2. 입출력 예 📋 3. 알고리즘 ✅ 1. dfs를 이용하여 M개의 치킨 집 고르기 2. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. -> 각각의 집과 오픈한 치킨 집 중에서 가장 가까운 치킨집 거리를 구하기 3. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. -> for 문을 돌아가며 치킨 거리의 합을 구하기 어떻게 고르면, 도시의 치킨 거리가..
-
[Python] 2096 내려가기Algorithm/백준 2023. 2. 10. 17:49
1. 문제 📚 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 2. 입출력 예 📋 3. 알고리즘 ✅ 아무리 생각해도 로직은 맞는 거 같은데 자꾸 메모리 초과가 떠서 질문게시판을 참고했다 알고보니 입력부분 때문에 문제였다 ㅡ3ㅡ 이 글(https://www.acmicpc.net/board/view/82973)을 보고 그 부분만 수정하니 정답처리가 됐다 입력값은 크고, 현재 min과 max값은 그 전 위치가 영향을 주므로 dp라고 생각되어서 dp 방식으로 접근했..
-
[Python] 1806 부분 합Algorithm/백준 2023. 2. 10. 15:19
1. 문제 📚 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 2. 입출력 예 📋 3. 알고리즘 ✅ 투포인터에 응용문제이다 입력이 100,000이 들어오니까 이중포문 돌리면 시간초과날것이다 투포인터 개념만 있다믄 쉽게 푸는 문제이다 4. 소스코드 💻 import sys input = sys.stdin.readline N, S = map(int, input().strip().split()) arr = list(map(int, inp..
-
[Python] 2457 공주님의 정원Algorithm/백준 2023. 2. 3. 20:54
1. 문제 📚 https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 2. 입출력 예 📋 3. 알고리즘 ✅ 이 문제는 조건이 2가지이다 처음엔 날짜계산을 일일히 하는 바람에 분기문이 헷갈려서 이틀이나잡고있었다; 구글링을 통해 힌트를 얻고 다시 내 로직으로 풀어봤당 조건1) 3/1 ~ 11/30 까지 매일 한가지 꽃 날짜는 월 * 100을 해주어 비교가 쉽도록 바꿔주었다 또한, 3/1 일 이전에 심을 수있는 꽃은 301 으로 통일해주..
-
[Python] 2847 게임을 만든 동준이Algorithm/백준 2023. 1. 31. 14:15
1. 문제 📚 https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 2. 입출력 예 📋 3. 알고리즘 ✅ 점수를 내리는 것을 최소한으로 하는 방법은 뒤에 숫자가 1이 더 크면 된다 → 그리디 나는 while 문을 돌려가며 하나씩 -1을 해주고 마지막에 리스트를 전부 순회하며 뒤에 숫자가 큰 지 다시 체크를 해주었다. 맞긴했지만, 더 좋은 방법이 있을 것같아 구글링해보았다! 다른 사람들 코드를 보니 뒤에부터 리스트를 순회하며 뒤의 값보다 1만큼 ..
-
[Python] 1439 뒤집기Algorithm/백준 2023. 1. 31. 10:15
1. 문제 📚 https://www.acmicpc.net/problem/1439 2. 입출력 예 📋 3. 알고리즘 ✅ 최소 횟수를 구하기 위해선 가장 적은 뭉텅이를 뒤집어야한다 → 그리디 예를 들어 0001100 이면 뭉텅이로 자르게 되면 0은 2개고 1은 1개이므로 1만 뒤집으면 최소행동이 될 것이다 따라서, 1. 뭉텅이로 잘라주고 (0, 1, 0) 2. 그 갯수를 세어 가장 작은 것을 프린트해주면 된다 4. 소스코드 💻 import sys N = list(sys.stdin.readline().strip()) # 뭉텅이로 잘라줌 stack = [N[0]] for i in range(1, len(N)): if N[i - 1] != N[i]: stack.append(N[i]) zero_count = sta..