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씩 증가시키며 자연수를 스택에 push한다. 그리고 push가 끝나면 수열을 출력하기 위해 마지막 1회만 pop한다. 현재 수열 값 < 자연수 현재 수열 값보다 자연수가 크다면 pop으로 스택에 있는 값을 꺼낸다...

https://www.acmicpc.net/problem/11003 1단계 - 문제 분석하기 일정 범위 안에서 최솟값을 구하는 문제 → 슬라이딩 윈도우 + 정렬 일반적인 정렬의 시간 복잡도 nlog(n) → N과 L의 최대 범위가 5,000,000인 이 문제에서 정렬 사용 불가 → O(N)의 시간 복잡도로 해결해야 함. → 슬라이딩 윈도우를 덱(deque)으로 구한하여 정렬 효과를 볼 수 있음 덱은 그림처럼 양 끝에서 데이터를 삽입하거나 삭제 가능한 자료구조이다. 2단계 - 손으로 풀어 보기 덱에서는 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장한다. 덱에서 노드를 제거하는 상황 설명을 위 해 (1,1)을 덱에 추가할 때, (2,5)를 덱에 추가할 때 필요한 탐색, 검사 과정 생략 이 상태에서 ..

4. 슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결한다. 투 포인터 알고리즘과 매우 비슷하다. [❌][백준 12891] DNA 비밀번호 12891번: DNA 비밀번호 1단계 - 문제 분석하기 P와 S의 길이가 1,000,000으로 매우 큼 → O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 함. 부분 문자열의 길이가 P → 슬라이딩 윈도우의 개념을 이용하면 문제를 쉽게 해결 가능 길이가 P인 윈도우를 지정하여 배열 S의 시작점에 놓는다. 윈도우를 오른쪽으로 밀면서 윈도우에 잡힌 값들이 조건에 맞는지 탐색 배열 S의 길이만큼만 탐색을 진행하면 되므로 O(n)의 시간 복잡도로 문제 해결 가능 2단계 -..

2. 구간합 구간 합은 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘. 코딩 테스트에서 사용 빈도 높음! 구간 합의 핵심 이론 합 배열 S 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열. 합 배열을 미리 구해두면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소! A[i]부터 A[j]까지의 배열 합을 합 배열 없이 구하는 경우, 최악의 경우는 i가 0이고 j가 N인 경우로 시간 복잡도는 O(N)이다. 합 배열을 사용한다면 O(1) 안에 답을 구할 수 있다. 합 배열 S를 만드는 공식 S[i] = S[i - 1] + A[i] ..

1. 배열과 리스트 배열과 리스트의 핵심 이론 배열 배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 배열의 값은 인덱스를 통해 참조 가능하고 선언한 자료형의 값만 저장 가능 ex) 아래 배열을 배열 A라 하고, 값 4에 접근하고자 하면 → A[3] 배열의 특징 인덱스를 사용하여 값에 바로 접근 가능 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움. -> 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정 필요 배열의 크기는 선언할 때 지정 가능, 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 구조가 간단 → 코딩 테스트에서 많이 사용 리스트 리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 리스트의 특징 인덱스가 없다 → 값에 접근하..

문제 설명 이 문제는 손님들을 온 순서대로 엘리베이터에서 호수까지 가깝게 층수가 h까지고 동수가 w까지인 호텔에 배치하는 것이다. 그리고 거리가 같을 때는 아래층을 선호하기에 1호 라인의 101부터 h층까지 순서대로 채우고 다 채우면 2호라인 순으로 나아가면 된다. 따라서 w는 고려하지 않고 입력받은 h와 n만을 이용하여 문제를 풀 수 있다. 풀이과정 효율적인 입출력을 위해 BufferedReader와 InputStreamReader를 통해 문자열 데이터를 입력 받는다. 이 과정을 위해서는 IOException 예외를 처리해준다. 문자열의 효율적인 처리를 위해 StringBuilder 객체를 선언한다. t를 입력받고 for문 안에 StringTokenizer 객체를 생성하여 공백을 기준으로 h, w, n..