이진 탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 탐색 범위를 반으로 좁혀가면서 탐색 - 이진 탐색을 하기 위한 전제 조건(precondition) : 탐색을 실시하기전에 오름차순 정렬이 되어있어야 한다. 동작 예시 0) 오름차순 정렬된 데이터 중에서 값이 4인 원소를 찾아보자. 1) 시작점 0, 끝점 9, 중간점 (9 / 2 = 4) 2) 중간점보다 4가 작으므로 시작점 0, 끝점 3, 중간점 1 3) 중간점보다 4가 크므로 시작점 2, 끝점 3, 중간점 2 예제코드 import java.util.Scanner; public class M14_이진탐색 { public static void main(String[] args) { Scanner sc = new Sc..
들어가기전, 큐 https://devfunny.tistory.com/710 큐 (Queue) 큐 - 선입선출 : 먼저 들어 온 데이터가 먼저 나가는 형식 예제코드 import java.util.LinkedList; import java.util.Queue; /** * Queue */ public class M2_Queue { public static void main(String[] args) {.. devfunny.tistory.com BFS - 너비 우선 탐색 - 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. - 큐 자료구조를 이용한다. [수행 과정] 1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다 2) 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드..
큐 - 선입선출 : 먼저 들어 온 데이터가 먼저 나가는 형식 예제코드 import java.util.LinkedList; import java.util.Queue; /** * Queue */ public class M2_Queue { public static void main(String[] args) { Queue queue = new LinkedList(); queue.offer(5); // push 5 queue.offer(3); // push 3 queue.offer(2); // push 2 queue.poll(); // pop 5 queue.offer(1); // push 1 queue.poll(); // pop 3 while (!queue.isEmpty()) { System.out.printl..
들어가기전, 스택 (Stack) https://devfunny.tistory.com/708 스택 (Stack) 스택 1) 선입후출 : 먼저 들어온 데이터가 나중에 나가는 형식 예제코드 import java.util.Stack; /** * Stack */ public class M1_Stack { public static void main(String[] args) { Stack stack = new Stack.. devfunny.tistory.com DFS - 깊이 우선 탐색 - 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. - 스택 또는 재귀함수를 사용한다. [수행 과정] 1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라..
스택 1) 선입후출 : 먼저 들어온 데이터가 나중에 나가는 형식 예제코드 import java.util.Stack; /** * Stack */ public class M1_Stack { public static void main(String[] args) { Stack stack = new Stack(); stack.push(5); // push 5 stack.push(3); // push 3 stack.push(8); // push 8 stack.pop(); // pop 8 stack.push(2); // push 2 stack.pop(); // pop 2 while(!stack.isEmpty()) { System.out.println(stack.peek()); // 최상위 데이터 peek stack...
구현 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. (구현 유형) - 완전 탐색 : 모든 경우의 수를 다 계산하는 해결 방법 - 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 구현에서의 까다로운 문제 유형 1) 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 2) 특정 소수점 자리까지 출력해야 하는 문제 3) 문자열이 입력으로 주어졌을 대 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 4) 어떻게 풀면 될지 대략 감은 오는데, 막상 코드로 옮기려니 무엇부터 작성해야 할지 모른다. 5) 적절한 라이브러리를 찾아서 사용해야 하는 문제
그리디 알고리즘 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구하며, 이러한 그리디 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야한다. 문제 유형을 분석하기 어렵다면, 해당 문제가 그리디 알고리즘으로 풀이할 수 있는게 아닌건지 생각해봐야한다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 것이므로 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게모르게 제시해준다. 문제 상황 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶다. 1) 일반적인 상황에서 그리디 알고..
문제 https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 풀이코드 package seohae.thiscodingtest.part03.Q03_StringReverse; import java.util.Scanner; /** * https://www.acmicpc.net/problem/1439 */ /* 0, 1로 만 이루어진 문자열 S 문자열 S의 모든 숫자를 같게만들자. S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는것이다. 뒤집는 것은 1 ->..
문제 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할때 항상 최적의 경로를 찾아야한다. N x N 크기의 2차원 배열에 각각의 칸을 지나기 위한 비용이 존재한다. 가장 왼쪽칸 [0][0] 에서 가장 오른쪽 아래칸 [N - 1][N - 1] 위치로 이동하는 최소비용을 출력하라. 화성탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다. 풀이코드 package seohae.thiscodingtest.part03.Q39_MarsExploration; import java.util.*; /* - 구현 후 로직 디버깅 (distance) 5 5 4 3 9 1 3 2 7 의 경우 (1) [1000000000, 1000000000, 1000000000], [1..
문제 https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 풀이코드 import java.util.ArrayList; import java.util.List; /* 문자열 압축 : 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현 (예시) aabbaccc -> 2a2ba3c 앞의 a 개수 : 2 b 개수 : 2 a 개수 (1이므로 a) c ..
문제 N X M 크기의 금광이 있다. 금광은 1 X 1 크기의 칸으로 나누어져있으며, 각 칸은 특정한 크기의 금이 들어 있다. 채굴자는 첫번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에 첫번째 열의 어느 행에서든 출발이 가능하고, 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하라. (예시) 1 3 3 2 2 1 4 1 0 6 4 7 가장 왼쪽의 위치가 (1, 1)이고 가장 마지막의 위치를 (n, m)이라고 했을때 아래와 같다. (2, 1) (3, 2) (3, 3) (3, 4) 위치로 이동하면 총 19만큼 금의 최댓값으로 이동할 수 있다. 첫번째 열에서 (1,1) (2,1) (3,1) 의 ..
문제 https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 풀이코드 package seohae.thiscodingtest.part03.Q25_FailureRate; import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; import java.util.stream.Collectors; ..