즐겁게, 코드

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

[백준 온라인 저지 링크] 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 분류가 BFS로 되어있어 별 생각없이 BFS로 탐색을 구현했지만, DFS를 사용하면 시간 초과가 난다고 한다. DFS를 사용하는 코드는 약간 백트래킹? 하듯이 분기별로 값을 저장해둔 뒤 저장한 값들 중 최솟값을 구하면 될 듯 한데... 나보다 잘 짜는 사람들이 안된다는 데에는 이유가 있을 것이다. (_ _) 아무튼 최단거리를 구하는 문제는 BFS 방식을 사용하는 것이 정석이라고 한다. 앞으로 비슷한 유형은 BFS를 열심히 우려먹자. (예전에 얼핏 어떤 문제 유형..

[백준 온라인 저지 링크] 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 분명 테케는 통과했고 코드에도 문제가 없는데 계속 틀려 의아했다. 원인은 바로 탐색을 시작하는 첫 번째 노드를 방문했다고 체크하지 않아서였는데, 다행히도 금방 실수를 캐치할 수 있었다. 탐색을 시작하는 첫 번째 노드도 방문했음을 체크해주는걸 잊지 말고... 타입 캐스팅을 좀 더 세련되게 하는 방법이나 찾아봐야겠다 @__@ [정답 코드 - Python] from collections import deque T = int(input()) b..

특이한 점은 없는 탐색 문제다. 오랜만에 푸는 탐색 문제다 보니 DFS 코드를 어떻게 구현할지 고민을 많이 했었는데, 그래도 감을 더듬어가며 코드를 짜니 금방 풀렸다. [정답 코드 - Python] T = int(input()) dy = [1, 0, -1, 0] dx = [0, 1, 0, -1] def DFS(row, col, visited): for i in range(4): new_row = row + dy[i] new_col = col + dx[i] if field[new_row][new_col] == 1 and visited[new_row][new_col] == False: visited[new_row][new_col] = True DFS(new_row, new_col, visited) for _..

[백준 온라인 저지 - 문제 링크] 아이디어도 아이디어지만, 은근히 구현이 어렵게 느껴진 문제였습니다. [정답 코드 - 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문을 활용해 해결할 수 있습니다. [정답 코드..

[백준 온라인 저지 - 문제 링크] 이 문제에는 시간 초과라는 무시무시한 함정이 깔려 있습니다. 따라서 여느 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..