본문 바로가기

전체 글229

[백준] 11003 최솟값 찾기(python) https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 1. 난이도 플레티넘 5 이 문제의 데이터의 범위는 0 ~ 5,000,000이기 때문에 정렬(O(nlogn))을 이용해서 풀면 시간초과가 발생한다. 따라서 deque를 이용해 정렬을 진행해야한다. 문제를 해결하는 알고리즘은 1. deque의 마지막에 있는 값들부터 현재 들어올 값보다 크면 최솟값이 아니기 때문에 모두 pop을 시킨다. 2. dequq의 마지막에 현재.. 2023. 3. 6.
[백준] 12891번 DNA 비밀번호(python) https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 1. 난이도 실버2 (🥈) 2. 문제 해결 방법 부분문자열의 크기가 1,000,000으로 크기 때문에 시간복잡도 O(n) 으로 해결해야한다. 따라서 슬라이딩 윈도우 + 딕셔너리를 이용해서 문제를 해결했다. (다른 푼들이 푸는 코드를 보니 단순하게 if elif를 사용하는게 더 이득이었던 거 같음,,) 1. DNA라는 딕셔너리를 선언해주고, 첫 start 부터 end까지의 염.. 2023. 3. 5.
[프로그래머스] Level2 예상 대진표(python) https://school.programmers.co.kr/learn/courses/30/lessons/12985 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 해결 방법 1. 오답이 난 풀이 두 수의 차가 1인 경우 cnt를 return 해주는 방식으로 문제를 풀었는데 많은 문제에서 실패가 떠서 고민을 해봤다. A => 2번 / B => 3번일 경우 두 수의 차는 1이지만 round가 같지 않아 발생하는 경우의 반례가 생긴다는 것을 깨닫고, abs(A-B) ==1 or A//2 != B//2 => 두 수의 차는 1이고, 두 수를 2로 나눈 몫.. 2023. 3. 5.
[백준] 1005번 ACM Craft(python) https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 1. 난이도 골드 3 2. 문제 해결 방법 건물을 짓는 순서가 정해져 있으며, 가장 빨리 지을 때까지의 최소시간을 알아내야한다. 따라서 순서가 정해져 있는 작업을 차례대로 수행할 때 사용되는 알고리즘인 위상정렬을 이용해 문제를 해결했다. value라는 새로운 list를 만들고, value에는 그 건물을 짓기 위한 시간을 누적해 저장한다. value 가 0인 경우는 아직 시간 측정이 안 된 건.. 2023. 3. 4.
[백준] 21921번 블로그(python) https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 1. 난이도 실버 3 2. 문제 해결 방법 넓이 구간이 고정되어 있으면 슬라이딩 윈도우를 이용하고, 유동적이면 투 포인터를 이용하면 된다. 처음에 sum 함수를 while문 속에 넣어서 문제를 풀었는데 O(N^2)가 되어 시간초과가 발생했다. (sum함수의 시간복잡도는 O(N)) 두 번째로는 투 포인터 방식을 이용했는데, 구간이 유동적이지 않아 굳이 이 방법을 사용할 필요가 없다는 걸 깨달.. 2023. 3. 3.
[백준] 1940번 주몽(python) https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 1. 난이도 실버 4 2. 문제 해결 방법 투 포인터를 이용하면 된다. 데이터의 크기가 작기 때문에 sort를 이용해 정렬한 후, start + end 의 값이 m과 같을 경우 카운팅해줬다. 3. 내가 작성한 코드 n = int(input()) #재료의 개수 m = int(input()) #번호 합 material = list(map(int, input().split()).. 2023. 3. 3.
[백준] 2018 수들의 합(python) https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 1. 난이도 실버5 (🥈) 2. 문제 해결 방법 투 포인터를 이용해 문제를 해결했다. 투 포인터란 list를 순차적으로 접근할 때 start 와 end라는 두 점으로 각각 기록하는 알고리즘이다. 3. 내가 작성한 코드 Version1 n = int(input()) num = [i for i in range(1,n+1)] interval_sum = 0 cnt = 0 end = .. 2023. 3. 3.
[알고리즘] 투 포인터 + 문제풀이 투 포인터 리스트에서 순차적으로 처리할 때 두 개의 점(start, end)으로 기록하며 처리하는 알고리즘 완전탐색은 O(N^2), 투 포인터는 O(N) 코드 n = 5 m = 5 data = [1,2,3,2,5] cnt = 0 interval_sum = 0 end = 0 for start in range(n): while interval_sum < m and end < n: #부분합이 더 작으면 end를 이동 interval_sum += data[end] end+=1 if interval_sum == m: cnt+=1 interval_sum -= data[start] #부분합이 더 크면 start를 이동 print(cnt) 관련 문제 - 백준 2018번 연속된 자연수의 합 구하기 (실버5) O - 백준.. 2023. 3. 3.
[프로그래머스] Level2 귤 고르기(python) https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 해결 방법 1. Counter 를 이용해 key 와 value 값을 구한다. (=> 귤의 크기에 따른 개수가 카운팅된다.) 2. list명.values() 를 출력하면 오름차순 정렬되기 때문에 reverse = True 로 내림차순 정렬한다. 3. 각 value 값을 하나씩 뽑으며 k보다 크거나 같으면 cnt 를 return 시키고, k보다 작으면 cnt를 1 증가시킨다. 2. 내가 .. 2023. 3. 3.

티스토리툴바