Algorithm
-
[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..
-
[Python] 11053 가장 긴 증가하는 부분 수열Algorithm/백준 2023. 1. 20. 17:20
1. 문제 📚 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 2. 입출력 예 📋 3. 알고리즘 ✅ N이 1000이기 때문에 완탐으로 하면 시간초과가 날 것이다 앞부분 수열에 따라 뒷부분 수열까지 영향을 주기 때문에 DP로 풀어야 한다! dp 를 1로 초기화해준 다음, 현재 index로 이전의 숫자와 차근차근 비교해서 증가하는 수라면 그 이전에 저장된 dp 값 + 1..
-
[Python] 15657 N과 M (8)Algorithm/백준 2023. 1. 20. 16:21
1. 문제 📚 https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 2. 입출력 예 📋 3. 알고리즘 ✅ 문제 조건 중 비내림차순이 있었기때문에 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 1. 정렬을 해주었고 2. dfs 파라미터로 그 이전 값을 받아, 그 이전 값보다 큰 값들만 append 시켜주었다 4. 소스코드 💻 import sys in..