여름 언덕에서 배운 것

탐색이란? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. (대표적인 탐색 알고리즘 : DFS와 BFS) DFS (Depth-First Search, 깊이 우선 탐색) : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 1. 인접행렬 : 2차원 배열에 각 노드가 연결된 형태를 표현 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. import java.util.*; public class search_0519_02 { public static final int INF = 999999999; // 2차원 리스트를 이용해 인접 행렬 표현 public static int[][] graph = { {0, 7, 5}, {7, 0, INF}, {5, INF, 0} }; ..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 📚 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램..

구현이란? 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 그렇다면 어떤 문제가 구현하기 어려운 문제일까? - 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 - 특정 소수점 자리까지 출력해야 하는 문제, - 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 등 또한 프로그래밍 문법을 정확하게 숙지하지 못했거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 풀 때 불리하다. 📚 예제4-1 ) 상하좌우 여행가 A는 N * N 크기의 정사각형 공간 위에 서있다. 이공간은 1 * 1 크기의 정사각형으로 나누어져 있다..

그리디 알고리즘이란? 기준에 따라 좋은 것을 선택하는 알고리즘 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. (대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.) 📚 3-1 ) 거스름돈 아이디어 : '가장 큰 화폐 단위부터' 돈을 거술러 주는 것 복잡도 : O(k) public class greedy01 { public static void main(String[] args){ int n = 1260; int cnt = 0; int[] coinTypes = {500, 100, 50, 10}; for(int coin : coinTypes){ cnt += n / coin; n ..