1. 문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr [문제 요약]부분 수열의 합 중 가장 큰 값을 구하라 2. 생각1. 코딩테스트는 두 가지 유형이 있지문제가 길어 문제가 요구하는 방향을 이해하면 풀 수 있는 문제와문제가 짧어 뭘 구하라는지 알겠는데 어떻게 구해? 하는 문제이 문제는 후자의 경우... 문제 보자마자 든 생각: 뭐 어떻게 구해?2. 펄스 수열 이용해서 2개의 배열 만드는 것까지는 쉬움3. "수열의 부분 수열의 최댓값" 이거 구하는게 관건같은데...하나씩 다 만들어보기에는 sequence의 길이 제한이 커서 안될꺼같다4. 30분정도 고민해보고 인터넷 찾아봤는데 이미 "카데인 알고리즘"..

1. 스택(Stack) 1 - 1. 스택이란? "쌓다", 데이터를 차곡차곡 쌓아 올린 형태의 자료구조를 말합니다 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있습니다. 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 LIFO(Last In First Out) 구조 가장 최근에 스택에 삽입된 자료의 위치를 top이라고 합니다. 활용 예시 웹 브라우저 뒤로가기 실행 취소(Ctrl + z) 역순 문자열 만들기 후위 표기법 계산 수식의 괄호 검사(연산자 우선순위 표현을 위한 괄호 검사) 1 - 2. 자바에서의 스택 자바에서의 스택은 Stack 클래스를 구현하여 제공하고 있습니다. Stack st = new Stack(); Stack의 메서드 boolean empty() : Stack이 비어있는지 확인 ..

### 1. 탐욕 알고리즘 이란? - Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움 - 최적의 해에 가까운 값을 구하기 위해 사용됨 - 여러 경우 중 하나를 결정해야할 때마다, **매순간 최적이라고 생각되는 경우를 선택**하는 방식으로 진행해서, 최종적인 값을 구하는 방식 1. 탐욕 알고리즘(Greedy Algorithm) 각 단계에서 지금 당장 가장 좋은 선택을 하는 알고리즘 이 선택은 그 순간에 대해 최적일지라도, 이후의 선택에 대해서는 고려하지 않는다 여러 가능성 중 하나를 선택할 때 마다 현재의 선택이 문제의 최적 해에 얼마나 가까워지는지를 고려하여 선택을 진행한다 2. 대표적인 문제 1) 거스름돈 문제 import java.util.HashMap; import java.util..

대표적인 그래프 탐색 알고리즘으로는 너비 우선 탐색(BFS, Breadth First Search)과 깊이 우선 탐색(DFS, Depth First Search)가 있다. 1. 너비 우선 탐색 (BFS, Breadth First Search) 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식이다 위 그림에서는, A - B - C - D - G - H - I - E - F - J 순으로 탐색한다 BFS는 재귀적으로 동작하지 않고 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 큐(Queue)를 사용한다 즉, 선입선출(FIFO) 원칙을 탐색한다 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하기 때문에 두 노드 사이의 최단 경로를 찾을 때 주로 사용한다..

탐색이란 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 말한다. 1. 순차 탐색(Sequential Search), 선형 탐색(Linear Search) 순차 탐색 또는 선형 탐색이라고 한다. 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법이다. [ 코드 ] public class main { public static void main(String[] args) { int[] array = {23, 45, 12, 67, 89, 34, 56, 72}; int target = 34; // 선형 탐색을 수행하고 결과를 출력 int result = linearSearch(array, target); if (result == -1) { System.out.println("Ele..

정렬 알고리즘은 n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘이다. 예를 들어 n개의 숫자가 저장되어있는 배열을, 오름차순의 조건으로 작성하여 입력하면 오름차순으로 정렬된 배열을 출력으로 구할 수 있다. 정렬 알고리즘은 정말 다양한데, 이에 따라 각각의 수행시간도 천차 만별이다. 1. 버블 정렬(Bubble Sort) 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 방식이다. [ 코드 ] static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { boolean swap = false; for (int j = ..