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)를 덱에 추가할 때 필요한 탐색, 검사 과정 생략 이 상태에서 ..

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] 배열의 특징 인덱스를 사용하여 값에 바로 접근 가능 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움. -> 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정 필요 배열의 크기는 선언할 때 지정 가능, 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 구조가 간단 → 코딩 테스트에서 많이 사용 리스트 리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 리스트의 특징 인덱스가 없다 → 값에 접근하..

알고리즘을 공부하면서 많은 정렬들이 등장한다. 버블 정렬, 삽입 정렬 등등... 오늘 공부한 내용은 이렇게 수많은 정렬 알고리즘 중 시간 복잡도가 O(n)으로 엄청난 성능을 보여주는 알고리즘이다. 카운팅 정렬을 공부하면서 처음에는 이게 왜 빠를까?를 생각했다. 시간 복잡도를 공부할 때, 시간 복잡도 도출 기준은 상수의 시간 복잡도는 계산에서 제외하고, 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다고 배웠다. 카운팅 정렬은 각 배열 원소끼리(예를 들어 for문 중첩) 직접 비교하지 않고, 인덱스를 가지고 위치를 찾아나가는 것이다. 이 방법의 가장 큰 장점은 매우 빠르다는 것이다. 하지만 카운팅 정렬은 수의 범위가 매우 클 경우(예를 들어 10억, 100억 등등...) 심한 메모리 낭비를..

문제 접근 처음에 문제를 접하고, 큐를 사용한 문제 풀이와 인덱스와 pop을 활용한 문제 풀이 2가지를 생각해보았다. 1. 파이썬(Python) 1) index와 pop을 이용한 문제 풀이 n, k = map(int, input().split()) arr = [i for i in range(1, n + 1)] ans_arr = [] idx = k - 1 # 시작 인덱스를 K-1로 설정 while arr: # 인덱스가 배열의 길이를 초과하는 경우, 인덱스를 배열의 길이로 나눈 나머지로 조정 if idx >= len(arr): idx %= len(arr) remove_elem = arr.pop(idx) ans_arr.append(remove_elem) # 다음 시작 인덱스를 K-1만큼 증가 idx += k ..