알고리즘/백준
-
알고리즘/백준 2023. 2. 8. 19:18
💁🏻 문제 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 🤷🏼♀️ 문제 설명 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 출발은 상근이네 집에서 하고, 20병이 들어있는 맥주 한 박스를 들고 출발한다. 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다. 상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서 가는동안 맥주가 떨어진다면 맥주를 더 구매하기 위해 편의점에 들릴 수 있다. 맥주를 파는 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을..
-
알고리즘/백준 2023. 2. 6. 21:40
💁🏻 문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 🤷🏼♀️ 문제 설명 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 인구이동이 며칠동안 발생하는지 구하자...
-
알고리즘/백준 2023. 1. 30. 22:00
💁🏻 문제 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 🤷🏼♀️ 문제 설명 한 행 또는 한 열의 한쪽 끝에서 다른 쪽 끝까지 지나가는 것을 길이라 한다. 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 같아야 한다. 단, 경사로를 놓아서 지나가는 길을 만들 수 있다. 경사로는 낮은 칸에 놓으며, L개의 연속한 칸에 경사로의 바닥이 모두 접해야 한다. 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다. 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다. 아래와 같은 경우에는 경사로를 놓을 수..
-
알고리즘/백준 2021. 12. 29. 16:13
문제 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 풀이 a. 접근법 https://www.acmicpc.net/problem/1463 문제와 유사하게 메모이제이션(memoization) 방식으로 접근하였다 DP[i] = i번째 곡을 연주할 때 가질 수 있는 볼륨값 P+V[i]와 P-V[i]가 범위 내의 볼륨 값을 가진다면 DP에 추가, DP[i]의 볼륨값을 가지고 DP[i+1]의 볼륨값을 구해낸다 이 때 마지막 곡을 연주할 수 없는 경우 (DP에 값이 없는 row가 존..
-
알고리즘/백준 2021. 12. 9. 19:14
문제 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 a. 접근법 N개의 동전을 사용하여 가치의 합이 K가 되는 경우의 수를 구해야 한다 knapsack 알고리즘을 이용하여 접근한다 ⓐ j가 coin[i]보다 작은 경우는, i번째 동전을 사용할 수 없으므로 DP[i][j] = DP[i-1][j] ⓑ j가 coin[i]보다 크거나 같은 경우는, i번째 동전을 0개 ~ x(x*coin[i]
-
알고리즘/백준 2021. 12. 9. 16:21
문제 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 풀이 a. 접근법 [0,0] ~ [m, n]까지의 최단 거리 경로의 수 구하는 방법 b. 실패 해당 index에 대하여 모든 경로의 수를 먼저 계산한 뒤, 갈 수 없는 경로의 수를 계산하여 제하는 방법 -> 효율성, 정확성 모두 실패 * 시간복잡도 O(N^3) 그림 때문에 m, n이 너무 헷갈렸다ㅠㅠㅠ def get_shortest_path(start_y, start_x, end_y, end_x): dp0 = [[1] * (end_y-start_y) for ..
-
알고리즘/백준 2021. 10. 24. 23:27
문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 a. 오답 및 시간 초과 import sys n = int(input()) data = [] for i in range(n): data.append([j for j in map(int, sys.stdin.readline().split())]) # 회의 시간이 짧은 순으로 정렬했음 -> 이러면 회의를 최대 갯수만큼 할 수 있을 거라고 생각했는데 # 반례 n=3, data = [[3,5],[1,4],[4,8]] data.sort(key=lambda x: x[1] - x[0]) # 회의실 사용 여부 _usage = [0 for i in range(max(x[1] for x..
-
알고리즘/백준 2021. 10. 24. 18:10
문제 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 a. 시간 초과 서류순위를 기준으로 오름차순 정렬을 수행한다 서류 순위가 1등인 이는 무조건 채용이 될 것이므로, [1: 지원자수]의 범위에 대하여 합격 여부를 확인한다 지원자보다 서류 순위가 높은 모든 이에 대하여, 면접 순위를 비교한다 서류/면접 순위가 모두 떨어지는 이를 합격자 명수에서 제외한다 해당 풀이의 경우 O(N^2)의 시간복잡도를 가지게 된다. 시간 초과로 실패 import sys T = int(input()) fo..