슬라이딩 윈도우3

• 

  [BOJ_12847] 꿀 아르바이트 📌 문제 링크: https://www.acmicpc.net/problem/12847 12847번: 꿀 아르바이트 월세를 내기 바로 전 날 까지 인 n (1 ≤ n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다. 그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000) www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: 슬라이딩 윈도우 또는 구간 합(Prefix Sum) 알고리즘에 대해 알고 있다면 크게 어려운 문제는 아니라고 생각한다. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 6. 15.

• 

  [BOJ_12891] DNA 비밀번호 📌 문제 링크: https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: DNA 비밀번호 문자열의 길이가 최대 1,000,000으로 만약 시간 복잡도가 O(N)보다 큰 알고리즘을 적용한다면 '시간 초과'가 발생한다. 그래서 슬라이딩 윈도우와 단일 for 반복문을 사용해서 시간 복잡도을 O(N)으로 맞추고, 부분 문자열에 등장하는 알파벳의 개수를 세기위해서 딕셔너리를 사용했다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 11. 24.

• 

  [BOJ_10025] 게으른 백곰 📌 문제 링크: https://www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net ❌ 내 풀이(Failure) : ✅ 내 풀이(Success) : 🧐 Review: 입력 값의 크기의 최댓값이 꽤 크기 때문에 시간 복잡도를 O(n)으로 줄이지 않는다면, 무조건 '시간 초과'로 틀릴 수밖에 없다. 그래서 for 반복문 하나로 코드를 작성했지만... 이상하게도 '시간 초과'로 틀리게 되었다. 작성한 코드에서 어떤 부분이 문제가 되는지 하나씩 변경해보면서 테스트를 해보다가 얼음의 양을 구하는.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 10. 14.