기록방

👉 문제링크 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 🔸 문제 분석 🔸 스택의 pop, push 연산과 후입 선출 개념을 정확하게 알고 있는지 묻는 문제이다. 스택에 넣는 자연수 값은 오름 차순 정렬이다. 현재 수열 값 >= 자연수 자연수가 현재 수열 값과 같아질 때 까지 자연수를 1증가시키며 스택에 push한다. 마지막은 출력하기 위해 1번 pop한다. 현재 수열 값 < 자연수 pop해서 스택의 가장 위 값을 확인한다...

👉 문제링크 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 🔸 문제 분석 🔸 일정 범위 안에서 최소값을 구하는 문제이므로 슬라이딩 윈도우와 정렬을 사용해야 한다. 윈도우의 크기는 최소값을 구하는 범위가 i-L+1 ~ i 이므로 L로 생각한다. 일반적으로 정렬은 O(nlogn)인데 N,L 의 범위가 5,000,000까지 이므로 정렬은 사용하지 못한다. O(n)의 시간 복잡도로 해결해야되므로 윈도우를 덱(deque)로 구현하여 정렬 효과를 낸다. 덱은 (인덱스, 숫자) 형태의 노드..

👉 문제링크 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 🔸 문제 분석 🔸 입력된 문자열 S에서 P 길이의 부분 문자열을 만들었을때, 입력된 DNA 문자열 최소 개수를 충족하는 경우의 수를 출력한다. 슬라이딩 윈도우 알고리즘을 이용해서 P길이의 부분 문자열을 문자열 S의 시작점부터 오른쪽으로 밀어간다. 윈도우에서 벗어나는 인덱스는 현재 상태에서 빼기 윈도우에 새로 들어오는 인덱스는 현재 상테에 더하기 조건에 충족 하는지 확인해서 카운트 🔸 코드 🔸 import java.io.Buffe..

👉 문제링크 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 🔸 문제 분석 🔸 문자열 A와 B가 주어지고, A를 최대한 B에 비슷하게 앞 뒤로 문자를 추가한다. 문자가 다른 인덱스의 수를 출력한다. A는 B보다 길이가 작거나 같다. 문자열 B에서 문자열 A를 겹쳤을때 가장 많이 겹치는 부분을 찾는다. 문자열 A의 길이에서 겹친 부분의 수를 뺀 값이 가장 클 때를 찾아 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io..

👉 문제링크 1064번: 평행사변형 평행사변형은 평행한 두 변을 가진 사각형이다. 세 개의 서로 다른 점이 주어진다. A(xA,yA), B(xB,yB), C(xC,yC) 이때, 적절히 점 D를 찾아서 네 점으로 평행사변형을 만들면 된다. 이때, D가 여러 개 나 www.acmicpc.net 🔸 문제 분석 🔸 세 점의 좌표가 주어지면, 만들 수 있는 평행사변형 중 가장 큰 너비에서 가장 작은 너비를 뺀 값을 출력한다. 세 점으로 그릴 수 있는 평행사변형은 3가지가 나오는데, 그 중 2가지는 같을 수 있다. 평행사변형을 만들 수 없는 경우는 세 점이 한 직선위에 존재할 때이다. 두 점의 기울기 (x증가량/y증가량)을 확인해서, 기울기가 같으면(한 선분 위에 존재하면) -1.0 을 출력한다. 그릴 수 있는 평..