Algorithm/백준

[백준] 11659. 구간 합 구하기 4 - 파이썬

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 1 Brute-Force로 풀어봤으나 시간초과 N, M = map(int, input().split()) nums = list(map(int, input().split())) totals = [] for _ in range(M): total = 0 i, j = map(int, input().split()) for k in range(i-1, j): total += nu..

[백준] 1697. 숨바꼭질 - 파이썬

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 난이도에 맞지 않게 굉장히 애를 먹었던 문제. 시간초과 메모리초과 틀렸습니다의 늪에서 허우적거린...^ㅁ^ 풀고 보니 결국 하나를 잘못 생각했다. 풀이 1 [백준] 1463. 1로 만들기 와 비슷하게, DP로 풀 수 있을 것이라 생각했으나, 오답. 아무래도 +1, -1이 둘 다 존재하기 때문에, 수가 계속 커지기만 하는 것은 아니라서, 이런 방식으로 풀이하는 것은 불가능..

[백준] 1541. 잃어버린 괄호 - 파이썬

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 복잡하게 생각할 거 없이, 괄호는 무한정 칠 수 있으므로, 첫 '-' 뒤에 나오는 숫자를 모두 빼면 된다. 문자열 처리만 잘 해주면 됨. s = input() buffer = '0' result = 0 isMinus = False '''마지막 숫자의 연산 처리를 위해 전체 문자열 맨 뒤에 연산자 하나 넣어줌''' s += '+' for i in s: if isMinus: if i == ..

[백준] 1463. 1로 만들기 - 파이썬

https://www.acmicpc.net/problem/1463 풀이 1 정말 단순하게 생각하면, "당연히 3으로 나누는게 가장 빨리 숫자를 줄일 수 있고, 그 다음이 2로 나누는 거고, 그 다음에 1을 빼는 것을 택하는 게 제일 유리한 거 아닌가?" 라고 생각할 수 있다. (약간의 Greedy 느낌!) 그러나, 10의 Input 예시만 생각해 봐도, 위와 같은 알고리즘으로는 10은 2로 나눠지므로, 10/2 = 5 5는 3, 2로 나눠지지 않으므로, 5-1=4 4는 2로 나눠지므로, 4/2 = 2 2는 2로 나눠지므로, 2/2 = 1 로 4번의 연산만에 1이 된다. 그러나, 첫 번째 단계에서 1을 빼는 것을 택한다면, 10 - 1 = 9 9 / 3 = 3 3 / 3 = 1 로 3번의 연산만에 1을 만..

[백준] 1389. 케빈 베이컨의 6단계 법칙 - 파이썬

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 BFS로 단순하게 풀이하기에는, BFS의 기본 time complexity가 O(N+E) / O(N^2)이므로, 대충 생각해봐도 O(N^2(N+E)) => O(N^3+E*N^2) 정도, 또는 O(N^4) 정도의 time complexity가 된다. 그렇기에, O(N^3) 정도의 time complexity인 Floyd-Warshall(플로이드-..

[백준] 1260. DFS와 BFS - 파이썬

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 기본적인 DFS, BFS 구현 문제. dictionary를 사용한다면, 없는 key에 접근하지 않도록 유의할 것. 예외처리를 하지 않고 제출했다가, 런타임 에러(keyError)가 남. line 30~32, 49~51과 같이 정점에 연결된 간선이 없을 때를 예외처리 해 주면 된다. 아마 정점이 딱 하나만 들어왔을 때 Error가 났을 듯. from col..

[백준] 1074. Z - 파이썬

https://www.acmicpc.net/problem/1074 풀이 재귀함수, 분할정복(Divide and Conquer)를 통해 어렵지 않게 풀 수 있었던 문제. 각 단계마다 4개의 구역으로 나누어, 어느 구역에 있는 지를 확인하고, 크기를 다시 1/4로 줄여 어느 구역에 있는 지를 확인하는 과정을 반복하면 된다. 와 같은 경우, N=2일 때 1행 3열의 숫자인 7을 구하는 과정은 (0행 0열이 start.) sol(2, 3, 1) 에서 middle = 2 이므로, r >= middle, c = middle 이므로 r = r - middle = 1 그리고 1구역이므로, 1x4 = 4 에, sol(N-1, r, c) 을 재귀호출하여 더해준다. 호출된 sol(1, 1, 1) 에서..

[백준] 1003. 피보나치 함수 - 파이썬

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 문제 이름부터 대놓고 피보나치 함수인데.. DP 써야겠죠? Top-Down 방식(재귀)로 구현함. 일반적으로 DP의 예시로 많이 나오는 게 피보나치 함수인데, 그거 생각하면서 풀었던 것 같다. 다만 원하는 결과값이 좀 다르므로, 잘 처리해주면 될 듯. dp = dict() test = [int(input()) for _ in range(int(input()))] def fib(n): if dp.get(n, -1) != -1: return dp[n] elif n == 0: return [1..