명이나물 라이브러리

Heap 정리, 우선순위 큐를 이해하기 위한 자료구조자료구조에서 Stack, Queue, Deque를 정리한 뒤, 이번에는 Heap에 대해 공부했다.처음에는 Heap이라는 이름만 보고 메모리 영역의 Heap을 떠올렸는데, 코딩테스트에서 말하는 Heap은 보통 우선순위가 높은 데이터를 빠르게 꺼내기 위한 자료구조를 의미한다.Java에서는 Heap을 직접 구현하기보다는 보통 PriorityQueue를 사용한다.1. Heap이란?Heap은 최댓값 또는 최솟값을 빠르게 찾기 위한 완전 이진 트리 기반 자료구조이다.코딩테스트에서는 보통 다음 상황에서 사용한다.상황사용하는 자료구조가장 작은 값을 계속 꺼내야 한다최소 힙가장 큰 값을 계속 꺼내야 한다최대 힙우선순위가 높은 작업부터 처리해야 한다우선순위 큐매번 정렬하..

자료구조: Stack, Queue, Deque, PriorityQueue자료구조의 핵심은 하나다.데이터를 어떤 순서로 꺼내야 하는가?상황떠올릴 자료구조가장 최근에 넣은 값을 먼저 꺼내야 한다Stack먼저 들어온 값을 먼저 꺼내야 한다Queue앞뒤 모두에서 넣고 빼야 한다Deque최솟값/최댓값을 계속 꺼내야 한다PriorityQueue1. Stack핵심 개념Stack은 나중에 들어온 값이 먼저 나가는 구조이다.LIFOLast In First Out예시:push(1)push(2)push(3)pop() → 3Java에서 Stack 사용Stack stack = new Stack();stack.push(1);stack.push(2);stack.push(3);System.out.println(stack.pop())..

AI-DLC란?최근 개발 방법론에서 AI-DLC라는 용어가 자주 등장하고 있다.AI-DLC는 보통 AI-Driven Development Lifecycle, 즉 AI 주도 개발 생명주기를 의미한다.기존 SDLC가 사람이 요구사항을 정리하고, 설계하고, 개발하고, 테스트하고, 배포하는 흐름이었다면, AI-DLC는 이 전 과정에 AI Agent나 생성형 AI를 적극적으로 참여시키는 개발 방식에 가깝다. AWS는 AI-DLC를 “AI를 중심에 둔 소프트웨어 개발 접근 방식”으로 설명하며, 핵심은 AI가 실행을 돕고 사람은 방향성과 의사결정을 담당하는 구조라고 설명한다. (Amazon Web Services, Inc.)1. AI-DLC를 한 문장으로 정리하면AI-DLC는 기획, 설계, 개발, 테스트, 배포, 운..

프로그래머스 K번째수정렬 알고리즘을 공부한 뒤, 연습 문제로 프로그래머스 K번째수 문제를 풀어보았다.문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42748사용 언어: Java풀이 시간: 약 24분제한 시간: 30분결과: 성공남은 시간: 약 6분처음에는 단순히 배열을 자르고 정렬하면 되는 문제라고 생각했다.하지만 직접 풀어보니 Arrays.copyOfRange() 사용법, 인덱스 처리, 원본 배열 보존 여부가 중요한 문제였다.1. 문제 설명배열 array의 i번째 숫자부터 j번째 숫자까지 자른 뒤,자른 배열을 정렬했을 때 k번째에 있는 수를 구하는 문제이다.문제 흐름1. array의 i번째부터 j번째까지 자른다.2. 자른 배열을 정렬한..

정렬 알고리즘Arrays.sort, Comparator, 문자열 정렬, 원본 배열 보존까지코딩테스트 문제를 풀다 보면 정렬은 정말 자주 등장한다.처음에는 정렬을 단순히 숫자를 오름차순이나 내림차순으로 나열하는 기능 정도로 생각했다.하지만 문제를 풀다 보니 정렬은 단순한 문법이 아니라, 데이터를 문제 풀이에 유리한 순서로 재배치하는 과정이라는 생각이 들었다.예를 들어 K번째 수를 찾거나, 구간이 겹치는지 확인하거나, 가장 큰 수를 만들거나, 좌표를 압축하는 문제에서도 정렬이 핵심으로 사용된다.이번 글에서는 Java 기준으로 정렬의 기본 문법과 코딩테스트에서 자주 나오는 정렬 유형을 정리해보려고 한다.1. 정렬이란?정렬은 데이터를 특정 기준에 따라 순서대로 배치하는 것이다.가장 기본적인 정렬은 오름차순 정렬..

할인 행사 - 고정길이 슬라이딩 윈도우로 풀기문제를 풀게 된 이유슬라이딩 윈도우를 공부한 뒤, 실제 문제에 적용해보기 위해 프로그래머스의 할인 행사 문제를 풀어봤다.이 문제는 10일 동안 할인하는 상품 목록을 확인해서, 내가 원하는 상품과 수량을 모두 구매할 수 있는 회원가입 날짜의 개수를 구하는 문제다.처음 문제를 봤을 때는 단순히 10일씩 잘라서 확인하면 될 것 같았다.하지만 직접 코드를 작성해보니, 단순 반복보다 고정길이 슬라이딩 윈도우로 푸는 게 더 깔끔하다는 걸 알게 됐다.문제 이해회원가입을 하면 가입한 날부터 10일 동안 할인 상품을 구매할 수 있다.예를 들어 내가 원하는 상품이 다음과 같다고 하자.want = ["banana", "apple", "rice", "pork", "pot"];num..

슬라이딩 윈도우코딩테스트를 준비하면서 이번에는 슬라이딩 윈도우 알고리즘을 공부했다.이름만 들었을 때는 조금 낯설었는데, 개념을 하나씩 정리해보니 생각보다 직관적인 방식이었다.말 그대로 창문을 옆으로 밀듯이, 일정한 구간을 유지하거나 조절하면서 배열이나 문자열을 탐색하는 방법이다.처음에는 투 포인터와 비슷해 보여서 헷갈렸다.특히 left, right를 같이 쓰는 문제들이 많다 보니, 이게 투 포인터인지 슬라이딩 윈도우인지 구분이 잘 안 됐다.공부하면서 내가 이해한 기준은 이렇다.고정 길이 구간 문제는 슬라이딩 윈도우로 접근하기 좋다.가변 길이 구간 문제는 left, right 포인터를 조절하는 투 포인터 방식으로 접근한다.다만 가변 길이 문제도 현재 구간의 상태를 유지하면서 이동하기 때문에,넓은 의미에서는..

투포인터 알고리즘1. 투포인터란?투포인터는 배열이나 리스트에서 두 개의 인덱스, 즉 포인터를 사용해 원하는 조건을 만족하는 값을 효율적으로 찾는 알고리즘 기법이다.보통 left, right 또는 start, end라는 이름의 변수를 사용한다.예를 들어 배열이 다음과 같이 있을 때,int[] arr = {1, 2, 3, 4, 5};두 개의 포인터를 사용해 특정 구간을 살펴보거나, 두 수의 합을 비교할 수 있다.[1, 2, 3, 4, 5] L R여기서 L은 왼쪽 포인터, R은 오른쪽 포인터다.2. 투포인터를 사용하는 이유배열에서 두 수를 고르거나, 연속된 구간의 합을 구하는 문제를 단순하게 풀면 보통 이중 반복문을 사용하게 된다.for (int i = 0; i 이 방식의 시간복잡도는 O(N..

연속된 부분 수열의 합 Java 풀이 — 투포인터로 시간초과 해결하기1. 문제 소개이번에 풀어본 문제는 프로그래머스 Lv.2 문제인 연속된 부분 수열의 합이다.문제에서는 비내림차순으로 정렬된 정수 배열 sequence와 정수 k가 주어진다.이때 합이 k가 되는 연속된 부분 수열을 찾아, 해당 구간의 시작 인덱스와 마지막 인덱스를 배열로 반환해야 한다.조건은 다음과 같다.부분 수열의 합은 k여야 한다.합이 k인 부분 수열이 여러 개라면 길이가 가장 짧은 수열을 선택한다.길이도 같다면 시작 인덱스가 더 작은 수열을 선택한다.처음에는 단순히 모든 구간의 합을 구하면 되지 않을까 생각했다.하지만 제한사항을 보고 완전탐색으로는 풀기 어렵다는 것을 알 수 있었다.2. 제한사항 확인문제의 제한사항은 다음과 같다.5 ..