백준 문제풀이 코드저장소 (99) 썸네일형 리스트형 Baekjoon 31885. Yunny's Trip / Python https://www.acmicpc.net/problem/31885알고리즘 설명문제 설명회윤이는 특정 목적지 (Ex, Ey)로 이동해야 한다.이동하는 방법은 두 가지가 있다.인접한 격자판으로 한 칸 이동한다. -> 기력 1 소모아이템을 사용하여 (a, b) 만큼 이동한다. -> 기력 2 소모조건초기 기력 K로 목적지에 도달할 수 있는지 확인한다.도달 가능하다면 최소 기력을 구한다.기력은 0 이상으로 유지해야 한다.코드 설명초기 거리 계산 : 목적지로 아이템 없이 직접 이동하는 경우의 거리를 계산한다.아이템의 좌표와 목적지의 상대 좌표를 활용하여, 코드를 최대한 단축시킨다. : 시간 복잡도를 N으로 나누는 효과를 얻을 수 있다.도달 가능한 경우의 최소 소모 기력을 계산한다.import sys; input .. Baekjoon 31963. 두 배 / Java, Python https://www.acmicpc.net/problem/31963알고리즘 설명문제 설명문제는 주어진 수열에서 어떤 연속된 두 수 a[i-1]와 a[i]가 있을 때, a[i-1]가 a[i]보다 작지 않도록 하기 위한 최소한의 조작 횟수를 구하는 문제, 조작은 a[i]를 2의 제곱만큼 증가시키는 것입니다.코드 설명비율 계산: 현재 수 arr[i]와 이전 수 arr[i-1]의 비율을 계산. arr[i-1]가 arr[i]보다 크면 arr[i]를 적절히 증가시키는 것이 필요하다. 비율을 구하는 식은 Math.log(arr[i-1] / arr[i]) / Math.log(2). 이를 Math.ceil 함수를 사용해 올림조작 횟수 누적: 각 단계에서 필요한 조작 횟수를 누적합니다. cnt_arr는 각 단계에서의 조작.. Baekjoon 4307. 개미 / Java https://www.acmicpc.net/problem/4307알고리즘 설명문제 설명개미들이 만나면 방향을 바꾸지만, 만났을 경우 서로 지나쳐간다라고 생각해도 논리가 같다.라는 생각을 해내면 굉장히 쉬워지는 문제코드 설명개미의 현재 위치로부터 막대 양 끝으로 가는 시간을 구해서 최소시간, 최대시간을 구한다.import java.io.*;import java.util.StringTokenizer;public class Main { public static int tc; // 테스트 케이스 수 public static int n; // 개미의 수 public static int l; // 막대의 길이 public static int[] arr; // 각 개미의 초기 위치를 저장하는.. Baekjoon 1865. 웜홀 / Python https://www.acmicpc.net/problem/1865알고리즘 설명문제 설명주어진 그래프에 음수 가중치가 있는지를 확인하여 시간 여행이 가능한지(즉, 음수 사이클이 존재하는지) 판단하는 문제코드 설명모든 노드에서 출발하여 음수 사이클이 존재하는지 확인한다.dp 배열을 사용하여 각 노드까지의 최단 거리를 저장하고, 그래프의 모든 간선을 N - 1번 반복하여 최단 거리를 갱신한다.N번째 반복에서도 최단 거리가 갱신되면 음수 사이클이 존재한다고 판단한다.import sysinput = sys.stdin.readlineinf = 1e10 # 벨만-포드 알고리즘을 사용하여 음수 사이클을 탐지하는 함수def sol(start=1): # 각 노드까지의 최단 거리를 저장하는 dp 배열 dp = .. Baekjoon 1238. 파티 / Python https://www.acmicpc.net/problem/1238알고리즘 설명문제 설명단방향 그래프에서 최단경로를 찾는 문제최단 경로의 값을 모두 구하고 그 중에 최댓값을 찾는다.코드 설명사람 별로 파티장까지 갔다가 돌아오는 길의 최단경로를 찾는다.최단경로의 경로길이들의 최댓값을 갱신한다.import sysfrom heapq import heappop, heappushinput = sys.stdin.readlineinf = 1e10n, m, x = map(int, input().split())arr = [[] for _ in range(n + 1)]# 최단경로구하기def sol(start, end): dp = [inf for _ in range(n + 1)] dp[start] = 0 q .. Baekjoon 23295. 스터디 시간 정하기 1 / Python https://www.acmicpc.net/problem/23295알고리즘 설명문제 설명주어진 스터디 시간에 사람들이 가장 많이 참여할 수 있는 시간 구간을 찾는 문제코드 설명슬라이딩 윈도우 알고리즘을 이용한 문제 풀이T 시간 간격으로 포인터를 이동시키면서 최대 만족도가 나온 경우 시작시간과 끝나는 시간을 갱신하는 방법import sysinput = sys.stdin.readlinen, t = map(int, input().split()) # 참가자 수 n 스터디 시간 tsummation = [0] * 100002 # 시간 범위를 저장할 배열end = 0 for i in range(n): k = int(input()) # 현재 참가자가 가능한 시간 구간의 수 k for j in ran.. Baekjoon 11779. 최소비용 구하기 2 / Python https://www.acmicpc.net/problem/11779알고리즘 설명문제 설명노드들이 주어지고 노드들 사이의 가중치가 주어졌을 때, 임의의 노드에서 다른 임의의 노드로 이동하는데 걸리는 최소 비용을 구하는 문제코드 설명다익스트라 알고리즘우선순위 큐를 사용하여 최단 경로를 탐색한다.주어진 시작점에서부터 시작하여 각 도시에 대한 최단 경로를 찾는다.각 도시 now에서 인접한 도시 next로 가는 비용 tmp를 더한 값이 현재 저장된 최소 비용보다 작으면 갱신하고 큐에 추가한다.dp[end][0] : 도착 도시까지의 최소 비용len(dp[end][1]) : 경로에 포함된 도시의 개수dp[end][1] : 최소 비용을 갖는 경로from heapq import heappop, heappush # 최소비.. Baekjoon 1069. 집으로 / Pyhton https://www.acmicpc.net/problem/1069알고리즘 설명문제 설명점프와 걷기를 이용해서 주어진 위치에서 원점으로 돌아가는데 필요한 최소 시간을 구하는 문제코드 설명걷기만 하는 경우점프를 한 후에 걷는 경우뒤로 조금 걸어간 후 점프를 하는 경우 -> 점프가 효율적이어서 점프 칸 수를 맞추기 위한 뒷걸음import math# 입력 받기x, y, d, t = map(int, input().split())# 유클리드 거리 계산dist = (x ** 2 + y ** 2) ** 0.5# 점프 횟수 계산jump = dist // d# 점프를 포함한 최단 시간 계산if dist >= d: tmp1 = t * jump + (dist - (d * jump)) tmp2 = t * (jump .. Baekjoon 11478. 서로 다른 문자열의 개수 / Java https://www.acmicpc.net/problem/11478알고리즘 설명문제 설명문자열의 서로 다른 '부분 문자열'의 개수를 구하는 문제코드 설명모든 부분 문자열을 생성하고 집합자료구조에 부분문자열을 저장했다.집합은 중복을 허용하지 않으므로, 집합의 크기가 문제의 답이 된다.import java.io.*;import java.util.*;public class Main { public static String s; public static BufferedReader br; public static Set arr; public static int res; public static void main(String[] args) throws IOException { .. Baekjoon 16951. 블록 놀이 / Java https://www.acmicpc.net/problem/16951알고리즘 설명문제 설명각기 다른 높이를 가진 배열을 높이 차를 k로 만드는 문제코드 설명한 번에 몇개를 옮기든 하나의 블록의 높이를 바꾸는 시간은 동일하기 때문에, 하나의 블록을 고정해 놓고 완전 탐색을 하면 된다.n ㄴimport java.io.*;import java.util.StringTokenizer;public class Main { public static int n; public static int k; public static int[] arr; public static int answer = Integer.MAX_VALUE; public static void main(String[] args) t.. 이전 1 ··· 3 4 5 6 7 8 9 10 다음