즐겁게, 코드

[백준 온라인 저지 링크] 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 다른 분들 코드를 보니 한번의 탐색만으로 답을 구하는 분들이 많았는데, 저는 두 번의 탐색을 활용하는 코드를 작성했습니다. 테스트케이스로 주어진 배열과 함께 빗물의 높이가 3인 경우를 예로 들겠습니다. 첫 번째 BFS 탐색에서는 원본 배열을 탐색해 안전 여부를 판단하는 배열을 만들어냅니다. 두 번째 BFS 탐색에서는 이렇게 만들어진 안전 영역의 수를 세 줍니다. 다만 한 가지 조심할 점은 "비가 오지 않는 경우 (= 높이가 0일때)" 가 마지..

[백준 온라인 저지 링크] 9047번: 6174 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스마다 한 줄에 네 자리 수(1000~9999)가 하나씩 주어진다. 단, www.acmicpc.net 기초 테스트 문제로 올라와 풀어본 문제였는데, 생각보다 까다로운 문제였습니다. 숫자 문자열의 (내림차순 정렬 결과) - (오름차순 정렬 결과)를 계속 구해주면 간단하게 답을 찾을 것 같지만... 아무 생각 없이 덤비면 피로 얼룩진 결과창을 보게 됩니다. 시간 초과의 이유는 바로 1000과 9998 두 개의 케이스 때문으로, 두 케이스는 다음 결과를 얻게 됩니다. (+ 이 둘은 제가 발견한 일부로, 찾지 ..

[백준 온라인 저지 - 문제 링크] 아이디어도 아이디어지만, 은근히 구현이 어렵게 느껴진 문제였습니다. [정답 코드 - Python] N = int(input()) t = [0] for i in range(N): t.append(list(map(int, input().split()))) for i in reversed(range(N)): for j in range(i): t[i][j] = t[i][j] + max(t[i + 1][j], t[i + 1][j + 1]) print(*t[1]) 풀이는 아이패드 구입 후 조만간 업데이트하도록 하겠습니다..

[백준 온라인 저지 - 문제 링크] N번째 피보나치 수를 구하는 문제입니다. 다만 N의 범위가 0 ~ 1백만 사이로, 꽤나 큰 피보나치 수를 구해야 합니다. 우선 이 문제는 파이썬 + 재귀 조합으로는 풀 수 없습니다! C++이나 자바 등의 언어에서는 어떤지 모르겠지만, 파이썬은 기본적으로 1000번까지의 *재귀 호출만을 허용합니다. 따라서 메모이제이션을 활용하는 재귀 함수 코드로는 런타임 에러를 피할 수 없게 됩니다. (* sys 모듈을 불러온 후 sys.setrecursionlimit() 함수를 활용하면 최대 재귀 깊이를 조정할 수 있긴 합니다만, 이 문제에서는 메모리 초과 에러에 걸리게 됩니다.) 그래서, 이 문제는 잠깐 초심(?) 으로 돌아가 단순 for문을 활용해 해결할 수 있습니다. [정답 코드..

혹시 피보나치의 수를 구하는 알고리즘을 알고 계신가요? 아마 많은 분들이 재귀함수를 사용하는 알고리즘을 떠올릴 것입니다. N = int(input()) def fib(N): if N == 0 or N == 1: return N return fib(N - 1) + fib(N - 2) print(fib(N)) # input output time # 10 55 0.00092s # 5 5 0.00018s # 100 한없이 긴 시간이 소요됩니다... 얼핏 보면 완벽해 보이는 알고리즘이지만 여기에는 함정이 하나 숨어있는데요, 잠깐 5번째 피보나치 수를 구하는 과정을 그림으로 소개하자면 아래와 같습니다. 5번째 피보나치 수는 4번째 피보나치 수와 3번째 피보나치 수를 더한 결과이며, 4번째 피보나치 수는 3번째 + ..

[백준 온라인 저지 - 문제 링크] 이 문제에는 시간 초과라는 무시무시한 함정이 깔려 있습니다. 따라서 여느 DP 문제처럼 DP 테이블을 그려 해결하되, 테이블을 조금 더 창의적으로 고안해야만 합니다! 처음 제가 구상한 알고리즘은 증가하는 인덱스 i ~ N까지의 원소 중 최댓값을 각 i 별로 구한 후, 이 중에서 최댓값을 찾는 방법이었습니다. 이를 기반으로 거친 생각과 불안한 마음을 안고 코드를 짜 봤으나... [실패 코드 (Python)] # 시간 초과 코드 T = int(input()) d = [0] * 100001 arr = list(map(int, input().split())) ans_list = [] temp_list = [] d[0] = arr[0] for i in range(1, T): t..