명이나물 라이브러리

이분 탐색이분 탐색은 영어로 Binary Search라고 한다.처음에는 이름이 조금 어렵게 느껴졌는데, 개념 자체는 생각보다 단순하다.핵심은 이것이다.정렬된 데이터에서 가운데 값을 확인하고,필요 없는 절반을 버리면서 원하는 값을 찾는 방법이다.즉, 처음부터 끝까지 하나씩 확인하는 것이 아니라,범위를 계속 절반으로 줄여가며 찾는 탐색 방법이다.이분 탐색이란?이분 탐색은 정렬된 배열에서 원하는 값을 빠르게 찾는 알고리즘이다.예를 들어 1부터 100까지 숫자 중에서 73을 찾는다고 해보자.하나씩 찾는다면 이렇게 확인해야 한다.1, 2, 3, 4, 5, ... 73운이 나쁘면 꽤 많은 숫자를 확인해야 한다.하지만 이분 탐색은 가운데부터 본다.1 ~ 100의 가운데쯤인 50을 확인한다.73은 50보다 크다.그러면..

프로그래머스 체육복 Java 풀이이번에는 프로그래머스 그리디 유형의 체육복 문제를 풀었다.체육복 문제는 그리디 입문 문제로 많이 언급되는 문제이다.문제 자체는 어렵게 느껴지지 않았지만, 실제로 풀면서 연산자 실수 때문에 잠깐 헤맸다.특히 +=를 써야 하는 부분에서 =+처럼 작성하면서 값이 예상과 다르게 나왔고, 디버깅하여 실수를 확인하고 수정하였다.문제 정보항목내용문제프로그래머스 체육복유형그리디사용 언어Java핵심 자료구조int 배열주요 개념학생별 체육복 개수 관리, 앞뒤 학생에게 빌려주기시간복잡도O(N log N)공간복잡도O(N)풀이시간40분결과통과문제 설명 정리전체 학생 수 n이 주어진다.일부 학생은 체육복을 도난당했고, 일부 학생은 여벌 체육복을 가지고 있다.체육복을 도난당한 학생은 수업을 들을 수..

그리디 알고리즘이번에는 코딩테스트에서 자주 나오는 그리디 알고리즘에 대해 공부했다.그리디는 이름부터 조금 낯설었다.영어로 Greedy는 “탐욕스러운”이라는 뜻인데, 알고리즘에서는 매 순간 가장 좋아 보이는 선택을 하는 방법을 의미한다.처음에는 “그냥 제일 큰 값이나 제일 작은 값을 고르면 되는 건가?”라고 생각했는데, 공부해보니 그렇게 단순하게만 볼 문제는 아니었다.그리디에서 중요한 것은 지금 선택한 것이 나중에도 손해가 되지 않는지 확인하는 것이다.그리디 알고리즘이란?그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 반복해서 답을 구하는 방식이다.쉽게 말하면 이런 느낌이다.지금 가장 좋아 보이는 선택을 한다.그 선택을 반복한다.최종적으로 답을 구한다.예를 들어 거스름돈을 줄 때를 생각해볼 수 있..

정수 삼각형, DFS로 접근했다가 DP로 다시 풀기처음에는 삼각형의 꼭대기에서 시작해서 아래로 내려가며 모든 경로를 탐색하면 된다고 생각했다.각 위치에서 아래 왼쪽 또는 아래 오른쪽으로 내려갈 수 있기 때문에, 자연스럽게 DFS처럼 모든 경우를 따라가보는 방식을 떠올렸다.하지만 그렇게 접근하니 시간초과가 났다.이 문제는 모든 경로를 직접 탐색하는 문제가 아니라, 각 위치까지 도달했을 때의 최대 합을 저장하면서 내려가는 DP 문제였다.문제 정보항목내용문제프로그래머스 정수 삼각형레벨Level 3유형DP (동적 계획법)사용 언어Java첫 접근DFS / 완전탐색결과시간초과최종 접근DP핵심각 칸까지 도달할 수 있는 최대 합 저장문제 설명삼각형 모양으로 숫자가 주어질 때, 맨 위에서 시작하여 아래층으로 내려가면서 ..

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모든 괄호의 짝이 맞음"())..