본문 바로가기
반응형

백준알고리즘68

[백준] 11286번 - 절댓값 힙 (Java)(◎) https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 입력값이 실시간으로 오른차순 정렬이 되어 있어야 한다. 2. 입력값이 양수와 정수가 번갈아 존재하고, 절대값 기준으로 정렬이 되어야 한다. 3. 절대값이 같을 경우 부호를 붙였을 때 작은 수가 앞쪽에 와야 한다. 4. PriorityQueue를 사용해서 실시간 정렬을 해보자. 5. class Node를 구성해서 num은 원래 값, abs는 절대값을 저장한다. class .. 2023. 1. 3.
[백준] 2164번 - 카드2 (Java)(Python) https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자... 2023. 1. 3.
[백준] 17298번 - 오큰수 (Java)(○) https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 1. 수열이 A1 ~ An 만큼 있다. 각 수열의 오큰수를 구해야 한다. 2. 오큰수란? Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수이다. 없으면 -1이다. 3. 오큰수 구하기 로직 - Ai가 가장 오른쪽 수이면 -1이다. - Ai 보다 큰 수가 없으면 -1이다. - Ai의 오른쪽 수를 순차적으로 비교해서 더 크면 스택에 push 한다. - 스택이 빌 때까지 pop을 하고 .. 2023. 1. 3.
[백준] 1874번 - 스택 수열 (Java)(△) https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1. 1~n 까지의 자연수를 스택에 집어 넣는다. 2. 그 n까지의 자연수들을 스택에 넣었다 뺐다 하면서 입력값으로 주어진 수열을 만들 수 있는지 확인한다. 3. 오름차순으로 증가시키면서 집어 넣는데 push 때는 '+', pop은 '-'을 출력한다. 불가능하면 'NO'을 출력한다. import java.io.Buf.. 2023. 1. 2.
[백준] 11003번 - 최솟값 찾기 (Java)(△) 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 N : 수의 갯수 : 1 ~ 5,000,000 L : 수의 범위 : 1 ~ 5,000,000 1. 특정 범위만큼 앞으로 이동하면서 그 범위 안에서 최솟값을 골라서 D에 저장해야 한다. 2. A[i-L+1] ~ A[i]가 범위로 주어지고, 예제 1의 L=3이라고 할 때 A[-2] ~ A[0]의 최솟값 : 1 A[-1] ~ A[1]의 최솟값 : 1 A[0] ~ A[2].. 2022. 12. 30.
[백준] 12891번 - DNA 비밀번호 (Java)(○) https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net S : 문자열 길이 : 1 ~ 1,000,000 P : 비밀번호 길이 : 1 ~ 1,000,000 1. DNA 문자 배열에서 첫 요소부터 i ~ +P 만큼 인덱스를 넘겨줘서 패스워드로 유효한지 체크 더보기 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokeniz.. 2022. 12. 29.
[백준] 1253번 - 좋다 (Java)(○) https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net N : 수의 개수 : 1 ~ 2,000 Ai : 정수 : 1 ~ 1,000,000,000 1. N개의 수 중 2개를 골라서 그 수의 합이 다른 어떤 수와 같다면 그 수를 GOOD이라고 한다. 2. 투 포인터를 이용해서 A[i] 값을 순차적으로 M으로 대입해서 투포인터 알고리즘으로 A[s] + A[e] == M 인 경우의 수를 찾는다. import java.io.BufferedReader; import java.io.Input.. 2022. 12. 28.
[백준] 1940번 - 주몽(Java)(○) https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net N : 재료의 수 : 1 ~ 15,000 M : 갑옷 필요한 재료의 수 : 1 ~ 10,000,000 1. 재료 번호 중 2개의 합이 M이 되면 갑옷이 완성된다. 2. DFS로 풀기에는 N이 너무 크다. 3. 투 포인터로 sIdx는 앞에서, eIdx는 뒤에서부터 진행하면서 합산한다. import java.io.BufferedReader; import java.io.Inpu.. 2022. 12. 28.
[백준] 11986번 - 나머지 합(Java)(△) https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 1. 먼저 구간 합 배열 D[N]을 구성한다. 2. 구간 합 배열을 순회하면서 M으로 나눠지는 요소를 찾아서 카운트 한다. 3. D배열 첫 인자부터 순회를 하면서 자기보다 작은 구간 합 배열을 뺐을 때 M으로 나눠지는 요소를 찾아서 카운트 한다. - D[i] - (D[0] ~ D[i-1]) 더보기 import java.io.BufferedReader.. 2022. 12. 28.
반응형

티스토리툴바