전체 글 (70) 썸네일형 리스트형 1강. 배열과 해시맵: 값을 빠르게 찾는 법 강의 목표이번 강의의 목표는 배열에서 원하는 값을 빠르게 찾는 방법을 익히는 것입니다.초보자가 코딩테스트 문제를 처음 보면 보통 이렇게 생각합니다.“배열을 처음부터 끝까지 다 확인하면 되지 않을까?”맞습니다. 처음에는 완전탐색으로 생각하는 것이 좋습니다.하지만 입력 크기가 커지면 모든 경우를 다 확인하는 방식은 너무 느려집니다.그래서 오늘은 다음 세 가지를 배웁니다.HashMap을 사용해서 값을 빠르게 찾는 법정렬과 투 포인터를 함께 사용하는 법배열 자체를 해시처럼 사용하는 고급 테크닉오늘 다룰 문제는 다음과 같습니다.난이도문제명핵심 개념 난이도문제명핵심 개념EasyTwo SumHashMapMedium3Sum정렬 + 투 포인터HardFirst Missing Positive배열 인덱스 활용1. 배열과 해시.. [Java/Algorithm] 모노톤 스택(Monotone Stack) '괄호 맞추기'가 스택의 기본적인 LIFO(후입선출) 특성을 이용한 것이라면, 택 내부의 데이터를 항상 '오름차순' 혹은 '내림차순'으로 유지하는 고급 기법인 **모노톤 스택(Monotone Stack)**을 배웁니다.이 기법을 완벽히 이해하면, 최악의 경우 O(N^2)이 걸리는 탐색 로직을 단숨에O(N)으로 줄여버리는 마술을 부릴 수 있습니다.1. 💣 치명적인 함정: 이중 루프의 늪 (백준 17298 오큰수)https://www.acmicpc.net/problem/17298문제 요약:크기가 N인 수열이 주어집니다. (N )각 원소에 대해, 자신의 오른쪽에 있으면서 자신보다 큰 수 중 가장 왼쪽에 있는 수(오큰수)를 구해야 합니다.오큰수가 없으면 -1을 출력합니다.예: [3, 5, 2, 7] -> 3의.. [Java/Algorithm] 희소 배열(Sparse Array) 처리 기법 앞서 2차원 배열의 제어와 회전을 배웠다면, 오늘은 물리적인 메모리의 한계를 돌파하는 희소 배열(Sparse Matrix/Array) 처리 기법을 다룹니다.코딩 테스트에서 시간 초과(TLE)만큼이나 무서운 것이 바로 메모리 초과(MLE)입니다. 데이터의 범위가 기하급수적으로 커질 때, 무작정 2차원 배열을 선언했다가는 단 1초 만에 프로그램이 터져버립니다. 오늘은 이 한계를 어떻게 우아하게 극복하는지 알아보겠습니다.1. 💣 치명적인 함정: 2차원 배열과 메모리 초과어떤 알고리즘 문제에서 다음과 같은 조건이 주어졌다고 가정해 봅시다."가로 10^5, 세로 10^5 크기의 격자판이 주어집니다. 이 격자판 위에 100개의 점을 찍고 로직을 수행하세요. (메모리 제한: 256MB)"🚫 초보자의 접근// 10.. [Java/Algorithm] 스택(Stack)의 본질과 호출 스택(Call Stack)의 이해 배열(Array)과 리스트(List)가 단순히 데이터를 일렬로 나열한 것이라면, 스택(Stack)은 데이터의 입출력 방식에 엄격한 규칙을 부여한 자료구조입니다.스택은 코딩 테스트의 단골손님일 뿐만 아니라, 프로그램이 컴퓨터 메모리(OS와 JVM) 위에서 어떻게 동작하는지를 이해하는 핵심 열쇠입니다.1. 🥞 스택(Stack): 후입선출 (LIFO)스택의 룰은 단 하나입니다. "가장 나중에 들어온 데이터가 가장 먼저 나간다 (Last In, First Out - LIFO)"식당에 쌓여있는 접시를 떠올려보세요. 설거지가 끝난 접시를 위로 차곡차곡 쌓고(Push), 요리를 담을 때는 맨 위에 있는 접시부터 꺼내서(Pop) 사용합니다. 맨 밑에 있는 접시를 빼려면 위에 있는 접시를 다 치워야만 하죠.Push (.. [Java/Algorithm] 2차원 배열 회전과 대칭 구현 시뮬레이션 및 구현(Implementation) 문제의 꽃이라 불리는 2차원 배열의 회전(Rotation)과 대칭(Flip)을 완벽하게 해부해 보겠습니다. 복잡한 시뮬레이션 문제(예: 테트리스, 블록 맞추기, 로봇 이동 등)를 풀 때, 배열을 90도씩 돌리거나 뒤집어야 하는 상황이 반드시 옵니다. 이때 인덱스 연산을 헷갈리면 ArrayIndexOutOfBoundsException의 늪에 빠지게 됩니다. 오늘은 이 연산을 수학적으로 명확히 정리하고, 재사용 가능한 유틸리티 메서드로 뽑아내는 연습을 해봅니다.1. 🔄 2차원 배열 90도 시계 방향 회전 (The Golden Rule)크기가 N * M인 2차원 배열 arr가 있다고 가정해 보겠습니다. 이를 시계 방향으로 90도 회전한 새로운 배열을 rotat.. [Java/Algorithm]ArrayList의 한계 극복과 스택(Stack)을 활용한 시뮬레이션 ArrayList가 인덱스 조회(O(1))에는 압도적으로 빠르지만, 중간에 데이터를 삽입하거나 삭제할 때는 뒤에 있는 모든 데이터를 밀고 당겨야 하므로 O(N)의 시간이 걸린다는 치명적인 단점을 배웠습니다. 이 단점이 어떻게 '시간 초과(TLE)'라는 재앙으로 다가오는지, 그리고 이를 어떤 발상의 전환으로 해결할 수 있는지 알아보겠습니다.1.백준 1406 (에디터)https://www.acmicpc.net/problem/1406 문제 요약:최대 10만 글자의 초기 문자열이 주어집니다.커서(Cursor)를 조작하는 명령어(L: 왼쪽, D: 오른쪽, B: 삭제, P $: 추가)가 최대 50만 개 주어집니다.명령어에 따라 커서를 움직이며 문자를 지우거나 중간에 끼워 넣은 후, 최종 문자열을 출력해야 합니다.시.. [Java/Algorithm] 1차원/2차원 배열 제어와 투 포인터(Two Pointers) 배열과 리스트의 특성을 바탕으로, 코딩 테스트 단골 손님인 *배열 제어'와 '투 포인터(Two Pointers)' 기법을 다뤄보겠습니다.단순히 for문을 두 번 중첩하면 풀리는 문제들이 있습니다. 하지만 입력 데이터가 10만 건 이상 넘어가는 순간, 중첩 반복문은 여지없이 '시간 초과(TLE)'를 뱉어냅니다.1. 1차원 배열과 투 포인터 (Two Pointers)투 포인터는 1차원 배열에서 두 개의 포인터(인덱스)를 조작하여 원하는 결과를 얻어내는 알고리즘입니다. 보통 정렬된 배열에서 두 수의 합을 구하거나, 연속된 구간의 합을 구할 때 사용되며 O(N^2)의 연산을 O(N)으로 획기적으로 줄여줍니다.🎯 실전 문제: 백준 3273 (두 수의 합)https://www.acmicpc.net/problem/.. [Java/Algorithm] 배열(Array)과 리스트(List)의 내부 구조와 시간 복잡도 모든 자료구조의 뼈대가 되는 **배열(Array)**과 **리스트(List)**에 대해 다뤄 봅시다.Java 백엔드 개발을 하다 보면 무의식적으로 List list = new ArrayList();를 작성하곤 합니다. 하지만 코딩 테스트 환경이나 대규모 트래픽을 처리하는 실무 환경에서는 데이터의 특성에 따라 ArrayList를 쓸지, LinkedList를 쓸지 정확한 근거를 가지고 선택해야 합니다. 오늘은 이 둘의 내부 동작 원리와 시간 복잡도를 완벽하게 비교해 보겠습니다.1. 배열 (Array): 빠르고 경직된 절대 권력배열은 메모리 상에 데이터가 '연속적으로(Contiguous)' 할당되는 자료구조입니다.장점 (Random Access): 메모리 주소가 연속적이기 때문에, 시작 주소만 알면 인덱스(I.. 이전 1 2 3 4 ··· 9 다음