Algorithm

[알고리즘] 동적계획법 (Dynamic Programming, DP)

동적계획법 (Dynamic Programming, DP) : 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제는 해결하는 알고리즘 DP 문제가 성립할 조건 1. 최적 부분 구조(Optimal Substructure) : 상위 문제를 하위 문제로 나눌 수 있으며 하위 문제의 답을 모아서 상위 문제를 해결할 수 있다. 2. 중복되는 부분 문제(Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 한다. 쉽게 설명하면 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘 * 혹은 Top-down (재귀)으로도 구성될 수 있다. 이는 이미 계산된 하위 문제에 대한 결과를 별도의 메모리 영역에 저장하여 다..

[알고리즘] 이분 탐색(Binary Search)

이분 탐색(Binary Search) : 전체 데이터에서 탐색 범위를 절반씩 줄여가며 key를 찾는 탐색 방법 이분 탐색은 정렬되어 있는 배열에서 데이터를 찾을 때 작동 가능하다. 이분 탐색은 결정 문제(Decision Problem)의 답이 이분적일 때 사용할 수 있는 탐색 방법이다. 이때 결정 문제란 Yes or No인 문제를 의미하며 보통 1개의 Parameter를 가집니다. ex) 1 2 3 4 5 6 에서 2를 찾고자 할 때 1) 배열의 중간에 위치한 3과 2를 비교 2) 2는 3보다 작으므로, 3의 오른쪽에 위치하는 값들을 탐색할 필요가 없다. 3) 그러면 3의 왼쪽에 있는 값 대상으로 다시 이분 탐색 4) 1 2 3 중에 중간값인 2와 비교 => 탐색 종료 종료 조건 1. 검색을 성공할 경우..

[Programmers/Java] 완전탐색 level2 : 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839# 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 ..

[Programmers/Java] 완전탐색 level1 : 모의고사

https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4..

[BOJ/JAVA] 1924번 : 2007년

https://www.acmicpc.net/problem/1924 1924번: 2007년 첫째 줄에 빈 칸을 사이에 두고 x(1 ≤ x ≤ 12)와 y(1 ≤ y ≤ 31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. www.acmicpc.net Calendar 클래스 사용하기 이 문제를 보자마자 필자는 Calendar 클래스를 떠올렸다. 이전 학기에 프로젝트를 진행하며 스케줄러에 잔뜩 치인 탓이었을까..? 그래서 정말 단순 무식하게 Calendar 클래스로 문제를 해결했다. import java.io.BufferedReader; import java.io.IOException; import jav..

[BOJ/C] 3045 이중 연결 리스트

https://www.acmicpc.net/problem/3045 3045번: 이중 연결 리스트 첫째 줄에 노드의 수 N과 연산의 수 M이 주어진다. (2 ≤ N ≤ 500,000, 0 ≤ M ≤ 100,000) 다음 M개 줄에는 상근이가 입력한 연산이 문제 설명에 나온 형식으로 주어진다. www.acmicpc.net 문제 창영이는 1학년 때 숙제로 했던 이중 연결 리스트 소스를 상근이에게 생일 선물로 보내주었다. 상근이는 드디어 자신이 원하던 기능이 있는 소스를 받게 되어서 매우 기뻤다. 상근이는 하루종일 이 리스트를 가지고 놀려고 한다. 리스트에는 총 N개의 노드가 포함되어 있고, 가장 왼쪽 노드가 1번이며 나머지는 오른쪽으로 갈 수록 1씩 번호가 증가한다. 리스트가 수행할 수 있는 연산은 아래와 같..