백준

[백준] 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..

[백준] 1012. 유기농 배추 - 파이썬

https://www.acmicpc.net/problem/1012 풀이 [백준 3197 - 백조의 호수], [백준 7569 - 토마토] 문제와 유사했던 문제. 마찬가지로, BFS를 이용해 풀이. 배추밭을 2차원 배열로 초기화, 이후 입력된 배추의 좌표를 가지고 2차원배열에 적용. 매 반복마다, 배추가 없는 지 확인. 배추가 있다면, 제일 먼저 발견된 배추를 Queue에 넣고, 먹어치워진 배추의 상하좌우를 탐색하며 BFS를 이용해 탐색을 진행. 인접한 모든 배추를 처리하고 나서, 다시 다음 반복을 진행~ 복잡한 건 없어서 주석 이외 부가 설명은 필요하지 않은 듯.. ^ㅁ^ from collections import deque test_case_cnt = int(input()) # 결과값 저장 worms =..

[백준] 7569. 토마토 - 파이썬

https://www.acmicpc.net/problem/7569 풀이 [백준 3197 - 백조의 호수] 문제와 상당히 유사했던 문제. BFS를 이용해 풀이함. 주의할 점은, 토마토를 익히는 과정에서 한 번 익혀지고, queue에 들어간 토마토는 값이 이미 1이 되었기 때문에, visited나 queue에 이미 존재하는 지 확인할 필요가 없음. in 이나 not in 연산자는 O(N) 의 time complexity를 가지므로, for나 while문 안에서 남발했다가는 그대로 시간초과가 되기 쉽다. [백준 3197 - 백조의 호수] 보다 쉬웠던 점은, 토마토가 다 익었는지 확인하는 과정을 Brute-Force로 처리해도 되었음. 그러나 3차원 배열을 써야 하므로 index의 순서가 바뀌지는 않았는지 항상..