명이나물 라이브러리

DP(다이나믹 프로그래밍), 중복 계산을 줄여주는 알고리즘이번에는 코딩테스트에서 자주 나오는 DP, 다이나믹 프로그래밍에 대해 공부했다.처음에는 이름부터 어렵게 느껴졌다.Dynamic Programming이라는 이름만 보면 뭔가 복잡한 알고리즘처럼 보이지만, 핵심은 생각보다 단순하다.한 번 계산한 값은 다시 계산하지 말고 저장해두었다가 재사용하는 것이다.즉, DP는 이전에 구한 작은 문제의 답을 이용해서 더 큰 문제의 답을 구하는 방식이다.1. DP란 무엇인가?DP는 Dynamic Programming의 줄임말이고, 한국어로는 동적 계획법이라고 부른다.하지만 이름보다 중요한 것은 개념이다.DP의 핵심은 다음과 같다. 핵심 개념설명저장한 번 구한 답을 배열 등에 저장한다재사용같은 계산이 필요할 때 다시 계..

프로그래머스 타겟 넘버 Java 풀이 기록DFS/BFS 개념을 공부한 뒤, 프로그래머스 타겟 넘버 문제를 풀어보았다.이번에는 30분을 잡고 문제를 풀었지만, 시간 안에 풀이를 완성하지 못했다.문제 설명을 아예 이해하지 못한 것은 아니었다. 오히려 “각 숫자마다 + 또는 - 두 갈래로 경우의 수가 나누어진다”는 점까지는 이해했다.하지만 문제는 그다음이었다.머릿속으로는 트리처럼 가지가 나뉘는 구조가 그려졌는데, 이걸 Java 코드로 어떻게 옮겨야 할지 감이 잘 오지 않았다.특히 두 가지 갈래로 나누어지는 부분을 for문 안에서 구현해야 하는지, 아니면 dfs() 메서드 안에서 구현해야 하는지 헷갈렸다.결국 생각은 어느 정도 했지만, 그 생각을 코드로 표현하는 단계에서 막힌 문제였다.문제 풀이 정보문제프로그래..

한 길을 깊게 갈까, 가까운 곳부터 볼까?이번에는 코딩테스트에서 자주 나오는 DFS/BFS를 공부했다.미로 탐색, 연결 요소, 토마토, 최단 거리 문제를 풀기 전에 기본 개념을 먼저 정리해두려고 한다.처음에는 DFS와 BFS가 둘 다 “탐색”이라 비슷하게 느껴졌는데, 공부해보니 핵심 차이는 생각보다 단순했다.DFS = 한 길을 먼저 깊게 탐색한다BFS = 가까운 곳부터 차례대로 탐색한다다만 여기서 주의할 점이 있다.DFS가 한 방향으로만 가고 끝나는 것은 아니다.BFS가 진짜 동시에 모든 방향으로 움직이는 것도 아니다.이 두 부분이 처음에 조금 헷갈려서 같이 정리해보려고 한다.1. DFS와 BFS는 언제 사용할까?DFS와 BFS는 보통 그래프나 2차원 배열에서 연결된 곳을 탐색할 때 사용한다.예를 들면 ..

Java 정렬 : Arrays.sort()와 Collections.sort()는 뭐가 다를까? Arrays.sort() → 배열을 정렬할 때 사용Collections.sort() → List를 정렬할 때 사용 즉, 핵심은 내가 지금 정렬하려는 대상이 배열인지, 리스트인지를 먼저 확인하는 것이다.1. Arrays.sort()는 배열을 정렬할 때 사용한다Arrays.sort()는 배열을 정렬할 때 사용한다.예를 들어 이런 배열이 있을 때:int[] arr = {3, 1, 2};정렬은 이렇게 한다.Arrays.sort(arr);전체 코드는 다음과 같다.import java.util.Arrays;public class Main { public static void main(String[] arg..

코딜리티 - Nesting자료구조에서 Stack을 공부한 뒤, 코딜리티 Lesson 7의 Nesting 문제를 풀어보았다.이번 문제는 25분 정도 걸려서 풀이를 완료했다.처음 제출했을 때는 87점이 나왔고, 이후 문제 조건을 다시 확인하면서 빈 문자열 케이스를 수정해 100점을 받을 수 있었다.문제 유형항목내용플랫폼Codility문제Nesting유형Stack핵심 개념괄호 중첩 검사사용 언어Java풀이 시간약 25분첫 제출 결과87점최종 결과100점문제 이해문제는 문자열 S가 올바르게 중첩된 괄호 문자열인지 확인하는 것이다.문자열 S는 다음 문자로만 이루어진다.'(' 또는 ')'올바른 중첩 문자열이면 1, 아니면 0을 반환해야 한다.예를 들어:입력결과이유"(()(())())"1모든 괄호의 짝이 맞음"())..

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. 자른 배열을 정렬한..