자료구조 & 알고리즘/백준(Baekjoon)

[백준] 1806(파이썬) - 부분합

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 이 문제는 언뜻 보면 2중 for문으로 탐색하면 되는 거 아니야...?라고 생각할 수 있지만, 메모리와 시간제한을 보면 절대 그럴 수 없다. 이 문제는 투 포인터 문제로, 두개의 변수를 이용해서 인덱스로 활용해서 푸는 문제이다. 투 포인터인 점만 확인하면 비교적 쉽게 풀 수 있는 문제이다. #시간초과 때문에 2중 for문은 안되고.. import sys input = sys.stdi..

2021.08.05 게시됨

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 2638(파이썬) - 치즈

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 이 문제는 2636 치즈 문제와 비슷한 문제로, BFS를 이용해서 푸는 문제이다. 여기서 조건 중 가장자리의 치즈가 녹는다는 점은 2636번 문제와 비슷하지만 각 치즈 격자의 4 변 중 2 변 이상이 공기와 접촉해야 녹는다는 점을 고려해야 한다. 여기서 만약에 치즈가 있을 경우(배열 값이 1일경우) 에는 BFS가 진행되면 안 되므로 q라는 큐 구조에 좌표를 추가하지 않고, 치즈가 없을..

2021.08.04 게시됨

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 2096(파이썬) - 내려가기

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 이 문제는 메모리를 보면 4MB.... DP를 사용해도 메모이제이션을 쓰면 안 되고 현재의 상태만 배열에 저장해 두고 값을 비교해서 갱신해 내 가는 방식으로 구현해야 했다. PYPY로 풀었을 때는 입력값을 일단 받아서 배열에 넣고 그 배열 값의 첫 번째 값을 변수에 담은 뒤, 변수를 갱신해 나가는 방법을 사용했다. PYPY3에서 N이 100000이라고 가정했을 때 100000번을 입력받는 것 또한 메모리 초과가..

2021.08.03 게시됨