일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 백준
- es6
- 가상화
- 알고리즘
- 리액트
- 파이썬
- 프론트엔드
- HTML
- 이슈
- 이더리움
- JavaScript
- 클라우드
- BFS
- 백엔드
- CSS
- 솔리디티
- kubernetes
- AWS
- 컴퓨터공학
- 웹
- next.js
- 블록체인
- TypeScript
- k8s
- 쿠버네티스
- node.js
- 자바스크립트
- docker
- react
- 타입스크립트
- Today
- Total
목록💯 알고리즘 (29)
즐겁게, 코드
[백준 온라인 저지 링크] 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문을 활용해 해결할 수 있습니다. [정답 코드..
혹시 피보나치의 수를 구하는 알고리즘을 알고 계신가요? 아마 많은 분들이 재귀함수를 사용하는 알고리즘을 떠올릴 것입니다. 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번째 + ..