문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이코드 package com.algorithm._00_._Current; import java.util.Arrays; import java.util.Scanner; import java.util.stream.IntStream; /** * @Date 2022/04/14 * @URL https://www.acmicpc.net/problem/11399 */ public class A11399_ATM { static int N..
문제 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 풀이코드 (실패 - 시간초과) package com.algorithm._10_투포인터; import java.util.Scanner; import java.util.stream.IntStream; /** * @Date 2022/04/10 * @URL https://www.acmicpc.net/problem/2559 */ public class A2559_수열 { static in..
문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이코드 package com.algorithm._05_BFS; import java.util.*; /** * @Date 2022/03/31 * @URL https://www.acmicpc.net/problem/7576 */ public class A7576_토마토 { static int[][] graph; static int N; static int M; static Lis..
문제 https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 풀이코드 package com.algorithm._00_._Current; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * @Date 2022/03/27 * @URL https://programmers.co.kr/learn/courses/30/lessons/42578 */ public class P42578_위장 { Map map = new HashMap(); public static void main(S..
문제 https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 풀이코드 package com.algorithm._01_그리디_구현; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.stream.Collectors; impo..
문제 https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 풀이코드 package com.algorithm._00_._Current; import java.util.Arrays; import java.util.HashMap; import java.util.Map; /** * @Date 2022/03/21 * @URL https://programmers.co.kr/lea..
문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘 https://devfunny.tistory.com/641?category=905091 최단 경로 알고리즘 - 다익스트라 알고리즘 우선순위 큐 사용 버전 들어가기전 기본 다익스트라 알고리즘에 대해 먼저 공부하자. https://devfunny.tistory.com/638 최단 경로 알고리즘 - 다익스트라 알고리즘 기본 버전 최단 경로 알고리즘..
계수 정렬 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을대 사용 가능하고, 이 경우에 매우 빠르게 동작한다. 동작 예시 0) 데이터 - List 객체 1) 원소를 모두 순회하여, List 객체의 인덱스에 해당 숫자가 나오면 +1을 해준다. - 원소 '7' - 원소 '5' 2) 모든 원소를 순회한 결과 3) 리스트의 원소를 순회하며 개수만큼 출력한다. 예제코드 public class M12_계수정렬 { public static final int MAX_VALUE = 9; public static void main(String[] args) { int n = 15; // 모든 원소의 값이 0보다 크거나 같다고 가정 int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4,..
퀵 정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. - 가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot 이라고 불린다.)로 설정한다. 동작 예시 0) 0번째 원소 '5'가 피벗이다. 1번째 원소인 '7'은 '5'보다 크고, 마지막 원소인 '8'은 '5'보다 크다. 대신 '8' 앞의 원소인 '4'가 '5'보다 작다. - 따라서 '7'과 '4'의 위치를 바꾼다. 1) 피벗은 그대로 '5'다. 왼쪽에서부터 '5'보다 큰 데이터를 선택한다. 원소 '9'와 오른쪽의 '5'보다 작은 '2'를 바꾼다. 2) 왼쪽에서부터 피벗 '5'보다 큰 데이터는 '6'이고, 오른쪽에서부터 '5'보다 작은 데이터는 '1'이다. - 위치가 엇가리게 되었을 경우 피벗 '5'와..
삽입정렬 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야한다. 구현 예시 0) 0번째 인덱스가 아닌 1번째 인덱스부터 시작한다. 원소 5를 기준으로 자신의 위치 앞의 '7' 원소의 왼쪽/오른쪽 둘 중 선택하여 삽입된다. - 원소 '5'는 원소 '7'보다 작으므로 '7'의 왼쪽에 삽입된다. 1) 2번째 원소인 '9'가 앞의 원소인 '7', '5'의 왼쪽/오른쪽 중 어디로 삽입될지 결정한다. 2) 3번째 원소인 '0'이 앞의 원소 '9', '7', '5' 의 왼쪽/오른쪽 중 어디로 삽입될지 결정한다. 3) 4번째 원소인 '3'이 앞의 원소 '9', '7', '5', '0' 의 왼쪽/오른쪽 중 어디로 삽입될지 결정한다. 4) 이러한 과정이 반복된다. 예제코드 import java.util.st..
선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 구현 예시 0) 정렬할 데이터 1) 0번째 인덱스인 '7'을 대상으로, 1번째 ~ 마지막까지의 인덱스의 원소 중 작은 값을 선택한다. 2) 1번째 인덱스인 '5'를 대상으로, 2번째 ~ 마지막까지의 인덱스의 원소 중 작은 값을 선택한다. 3) 2번째 인덱스인 '9'를 대상으로, 3번째 ~ 마지막까지의 인덱스의 원소 중 가장 작은 값을 선택한다. 4) 이러한 과정을 반복하면 오름차순으로 정렬된다. 예제 코드 import java.util.stream.IntStream; public class M9_선택정렬 { public static void main(String[] args) { int n =..
메모이제이션 (Memoization) 메모이제이션이란, 컴퓨터 프로그램이 동일한 계산을 반복해야할 때, 이전의 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법(Dynamic Programming)의 핵심이 되는 기술이다. 예시 (피보나치 수열) - 앞의 2개의 인덱스 원소의 합이 그 다음 인덱스 원소가 된다. Input : 5 Output : 1 1 2 3 5 0번쨰 + 1번째 = 2번째 원소 1) 1 + 1 = 2 1번째 + 2번째 = 3번째 원소 2) 1 + 2 = 3 2번째 + 3번째 = 4번째 원소 3) 2 + 3 = 5 메모이제이션 구현 코드 public class Memoization { private static ..