백준 [2477] 수열의 합(Python3)
문제 링크 : https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 수학적 사고가 요구되는 문제. 뭔가 누적합을 사용할 수 있을 거 같아서 여기에 대해 1시간 정도 고민하다 도저히 안 돼서 풀이를 봤다. 완전 탐색 1부터 1,000,000,000까지 돌면서 각 지점에서 2부터 L까지의 합을 구한다. 총 시간 복잡도 O(N * (L - 2))로, N과 L이 최대 값일 때 시간 초과 완전 탐색 최적화 - 누적합 사용. 1부터 1,000,000,000까지의 누적합을 구한 뒤, 한 지점을 정하고 ..
프로그래머스 - [1차] 뉴스 클러스터링
들어가기 전에 문제를 해결하기 위해 어떤 생각을 했는지 기록하기 위해 쓰는 글입니다. O(10^8)의 계산을 1초라 가정했습니다. 잘못되거나 개선이 필요한 부분 지적은 언제나 환영입니다! 지문 해석 두 문자열 str1, str2을 upper나 lower를 통해 대문자나 소문자로 변환해야 한다 변환된 문자를 슬라이딩 윈도우를 통해 특수문자가 있는지 확인하고, 없다면 배열에 추가한다. 각각 시간 복잡도가 O(n)이 나온다. 그 후, 슬라이딩 윈도우의 결과를 가지고 교집합과 합집합을 구한다. 여기서 주의할 점은 교집합을 구하는 과정에서 교집합이 된 쌍은 다음 교집합 확인에서 제외해야 한다. 예를 들자면 A = {1, 1, 2, 2, 3}, B = {1, 2, 2, 4, 5} 의 교집합에서 A[0] = 1과 B..
백준 [13913] 숨바꼭질4(Python3)
지문 해석 현재 위치를 X라 할 때, 일정한 범위 (X - 1, X + 1, X * 2)를 탐색한다. 매 이동엔 1초가 필요하니, 큐를 이용하는 BFS 방식이 필요했다. 방문 여부 체크에 관해서는 Boolean 값이면 충분했다. 최적의 탐색 비용의 경우, 큐 삽입 때, 기존 비용 + 1을 하면 간단히 해결됐다. 하지만, 지나온 경로를 표시하는 부분 해결에서 문제를 겪었다. 지나온 경로 문제 해결 1, 2번은 틀린 풀이다. 1. BFS 한 번 더 사용 데이터 범위가 작기 때문에 N -> K로 가는 BFS의 시간 복잡도가 적은것을 이용해 K -> N으로 다시 BFS를 할까 생각했다. 하지만, 이 과정은 코드가 너무 길어지고, 되돌아간 위치가 최단 경로 중 하나인지에 대한 검증이 필요했기 때문에 좋은 해결책이..
백준 [16564] 히오스 프로게이머(Python3)
들어가기 전에 문제를 해결하기 위해 어떤 생각을 했는지 기록하기 위해 쓰는 글입니다. O(10^8)의 계산을 1초라 가정했습니다. 잘못되거나 개선이 필요한 부분 지적은 언제나 환영입니다! 지문 해석 레벨을 올릴 수 있는 총합 K를 적절히 배분해서 얻을 수 있는 가장 높은 최솟값 T를 찾아야 한다. 브루트 포스로 해결한다면 최악의 경우 O(1,000,000 * 1,000,000,000) = O(10^15) 로 시간 초과를 받는다. 이분 탐색으로 해결한다면 O(1,000,000 * log(1,000,000,000)) O(1,000,000 * 29.8) = O(29,800,000) 로 해결할 수 있다. 이분탐색 범위 지정 N = 2 이고 X = {10, 10}, K = 1이라면, T의 값은 어떠한 경우에도 1..
