1. 버블 정렬 (Bubble Sort)정의: 두 인접한 데이터의 크기를 비교해 swap 연산으로 정렬함.시간 복잡도: O(N^2)특징 (비대칭성과 병목 현상):오른쪽 이동: 큰 숫자는 조건만 맞으면 한 번의 루프에서 끝까지 빠르게 이동 가능함.왼쪽 이동 (병목 지점): 작은 숫자는 한 번의 루프에서 아무리 작아도 무조건 왼쪽으로 딱 1칸만 이동함. j와 j+1을 비교해서 j가 더 크면 바꾸는 방식이기 때문임.결론: 정렬이 완료되려면 모든 숫자가 제자리에 가야 함. 오른쪽으로 가야 할 원소들은 한 번에 이동해 금방 끝나지만, 왼쪽으로 멀리 가야 하는 원소들은 한 번에 한 칸씩밖에 못 가므로 정렬의 속도를 결정하는 병목이 됨.2. 선택 정렬 (Selection Sort)정의: 대상 데이터에서 최대(혹은 최..

백준 17298번(오큰수)1. 주요 오개념 및 시행착오 (Pain Point)O(N^2) 완전 탐색 접근으로 인한 시간 초과 발생.배열을 [인덱스, 값] 형태로 미리 오름차순 정렬하여 접근하려 했으나, '오른쪽에 있으면서 가장 가까운'이라는 위치 조건을 만족시키기 위해 반복문 내부에서 추가 탐색이 발생하여 시간 복잡도 최적화에 실패함.정답 도출 로직이 완벽하더라도 System.out.print를 반복 호출하면 입출력 병목으로 인해 1초의 시간 제한을 통과할 수 없음을 인지하지 못함.2. 핵심 원리 및 수학적 근거 (Logic & Math)단조 스택(Monotonic Stack) 알고리즘 적용. 스택 내부에 아직 오큰수를 찾지 못한 원소들을 대기시키고, 새로 들어온 값이 스택 맨 위(top) 원소보다 클 ..

코딩에 대해 배웠다면 무조건 들어본 스택과 큐!하지만 이젠 스택과 큐를 쓰면 안됩니다! 왜? Stack vs ArrayDeque Stack 클래스의 강점 (하지만 치명적인 단점)- 스레드 안전성: 자바 1.0 극초창기에 만들어진 구식(Vector 상속) 클래스! 동기화 처리로 멀티스레드 환경에서 유용함(스레드 동기화란? 여러 개의 스레드가 하나의 데이터(객체)에 동시에 접근할 때, 데이터가 꼬이지 않도록 한 번에 한 스레드만 접근할 수 있게 잠금을 거는 장치) 하지만 코딩테스트에선 단일스레드 환경!나만 왔다갔다하기에 동기회 처리가 불필요한 오버헤드가 발생하고 속도를 낮추는 요인! 코테뿐만 아니라 스택을 안 쓰는 이유자물쇠를 열고 닫는 과정 자체가 너무 무거움! -> 게다가 자바 공식 문서에서도 LIF..

System.out.print vs BufferedWriter2가지를 많이 써봤다.둘 중 하나만 우세하다면 굳이 2개의 클래스로 구분될 필요가 없기에 각각의 존재 이유와 용도를 알고 싶었다.작은 데이터이지 않는 한 왠만하면 코딩테스트에서는 BufferedWriter를 쓰도록 한다. 속도가 빠르기 때문이다.그렇다면 System.out.print은? 필요 없는 것일까?아니다. 각각의 특징을 알아보자! System.out.print(PrintStream) - 압도적인 편의성: throws IOException이나 try-catch 같은 예외 처리를 억지로 안 해줘도 돼서 코드가 깔끔해진다.- 실시간 즉각 출력: 데이터를 모아두지 않고 그때그때 콘솔에 쏜다.그래서 코드 중간중간 변수값이 맞는지 확인하는 디버깅..

슬라이딩 윈도우: 2개의 포인터로 범위를 지정한 후 범위를 유지한 채로 이동핵심 원리- 업데이트할 때 새로 추가하는 문자열과 제거되는 문자열만 확인- 배열의 길이만큼만 탐색 진행- 시간 복잡도: O(n) 주요 사용처: 연속된 데이터 구간의 합, 최댓값/최솟값, 부분 문자열 검색 등. Deque(Double-Ended Queue): 양쪽 끝에서 모두 데이터의 삽입과 삭제가 가능한 핵심 원리- 먼저 들어온 것이 먼저 나가는 큐(FIFO)의 특성과 나중에 들어온 것이 먼저 나가는 스택(LIFO)의 특성을 모두 가짐.- 데이터의 앞(Front/Head)과 뒤(Rear/Tail) 어디서든 자유롭게 넣고 뺄 수 있어 유연함. 슬라이딩 윈도우와의 시너지: 윈도우가 이동할 때, '빠져나가야 할 오래된 값'은 앞에서 빼..

투 포인터: 2개의 포인터로 알고리즘의 시간 복잡도를 최적화 전제데이터 정렬: 특정 인덱스를 옮겼을 때 결과의 변화가 불규칙하다면 투 포인터 적용이 불가능함. 이동 원칙- A[start_index] + A[end_index] > target: end_index--;- A[start_index] + A[end_index] - A[start_index] + A[end_index] == target: start_index++; end_index--; count++; 결론- 시간 복잡도: 중첩 반복문 O(N^2)의 작업을 배열을 한 번 훑는 O(N)의 속도로 최적화함. (정렬 시간을 포함할 경우 O(N log N)- 공간 복잡도: 별도의 대규모 메모리 할당 없이 변수 두 개(포인터)만으로 탐색이 가능하여 메모리..

1. 주요 오개념 및 시행착오 (Pain Point)연속된 부분의 정의: '연속된'이라는 표현을 인접한 두 요소의 합으로 한정 지어 오해함. 실제로는 시작점 i와 끝점 j 사이의 모든 요소를 포함하는 임의의 구간 합을 의미함을 인지함.조합(nC_2) 활용의 당위성: 순서가 없는 조합을 사용하는 이유에 대해 의문이 있었으나, 누적 합 나머지가 같은 두 지점을 선택하는 행위가 곧 하나의 유일한 연속 구간을 정의하는 경계선 역할을 수행함을 이해함.시간 복잡도 설계 오류: 모든 구간을 전수 조사하는 O(N^2) 방식은 데이터 100만 개 기준 약 1조 번의 연산이 발생하여 시간 초과(TLE)가 불가피함. O(N)으로의 최적화 필요성을 체감함. 2. 핵심 원리 및 수학적 근거 (Logic & Math)나머지 연산..

알고리즘 선택의 기준 = 시간 복잡도수행 시간 -> 1억 번의 연산 = 1초의 시간최악일 때를 대비해야 함! -> 빅-오 O(n) 빅-오 표기법의 시간 복잡도 (데이터 크기 순) O(n!)-O(2^n)-O(n^2)-O(nlogn)-O(n)-O(logn)이때 상수는 간주하지 않음 n = 3n따라서, 같은 차수의 반복문이 여러 개인 것은 의미 없음하지만, 다른 차수의 반복문은 주의! ex) n과 n^2 -> 가장 많이 중첩된 반복문의 수행 횟수 = 시간복잡도의 기준 디버깅의 중요성시간 제한, 변수 초기화 오류, 메모리 누수 방지를 위해 디버깅은 필수적임!디버깅 대표사례1. 반복문에서 변수 초기화 오류반복문에서 다른 테스트 케이스로 결과 변수를 출력하는 경우, 테스트 케이스별로 결과 변수를 초기화하지 않음-..