본문 바로가기

알고리즘74

[BFS] 백준 5014번 : 스타트링크 - 파이썬 Python https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 생각하기 버튼을 누르는 최소 횟수를 구하는 것이기 때문에 전형적인 BFS 문제라고 생각하였다 시간 복잡도 S, G, F가 모두 1000000 이하의 수이므로 충분히 BFS로 풀어도 시간 안에 들어올 수 있는 문제 구현하기 q = deque() (현재 강호가 있는 층, 현재까지 누른 버튼의 횟수) 를 q에 append / popleft 한다 올라가는 버튼 현재 강호가 있는 층 + U 가 건물을 넘지 않아야 함 .. 2022. 2. 7.
[BFS] 백준 14395 : 4연산 - 파이썬 Python https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 생각하기 최소의 변환을 찾으면 되는 문제이기 때문에 BFS로 접근해야겠다고 생각 평소처럼 visited 배열(list)을 통해서 방문 여부를 검사려고하니, 메모리 문제가 발생 -> 각 연산의 특성을 잘 생각해보면 모든 10^9숫자를 다 사용하지는 않음 뺄셈을 만나면 S - S 로 0이 되므로 사실상 끝 나눗셈을 만나면 S / S 로 1이 되므로 사실상 2의 배수가 된다 S^a * 2^b 형.. 2022. 2. 7.
[DP] 백준 1496번 : 기타리스트 - 파이썬 Python https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 생각하기 N개의 연주곡 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주 V[i] - i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨 (차이) -> P + V[i] 혹은 P - V[i] 로 연주 가능 이때, 0 2022. 2. 4.
[이분탐색] 프로그래머스 입국심사 - 파이썬 Python https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 생각하기 처음에는 모든 경우를 살펴보자는 생각이었지만 n의 개수와 시간이 너무 커서 불가했다 이분 탐색으로 풀기 위해서 기준을 정해야 하지만 어떤 기준을 정해야할지 생각하는데에 오래 걸렸다 이분 탐색의 기준을 심사 시간이라고 가정 = 각 심사관이 사람을 처리할 수 있는 시간 right (max)는 가장 오랜 시간이 걸리는 심사관이 모든 사람(n)을 처리했을 때, .. 2022. 2. 1.

티스토리툴바