CodingTest(64)
-
[코딩테스트][다이나믹프로그래밍][Java] 백준 14501, 퇴사
1. 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 2. 접근 위의 예제에서 1일에 상담을 수행하면 총 3일이 소요되며 상담을 시작하는 날 포함하여 3일까지는 다른 상담을 수행할 수 없습니다. 만약 3일에 상담을 수행하면 3일 당일에 상담을 완수하고 10원을 받을 수 있습니다. 위의 예제에서 퇴사전에 받을 수 있는 최대 이익은 1일, 4일, 5일에 상담을 수행하고 총 45원을 받는 것입니다. 여기서 주목할 점은 7일까지 전부 상담을 마치고 8일날 퇴사를 하게 되는데 8일날에 45원을 받는다는 점입니다. 예를 들어 3일날 일을하고 당일에 상담을 완료하였다고 바로 10원을 받는..
2022.01.27 -
백준 17298, 오큰수
https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 알고리즘(접근방법) 처음 이 문제를 해결하기 위해서 접근했던 방법은 스택 자료구조를 사용하지 않고 이중 for문을 사용하였습니다. 하지만, 코드 제출 결과 시간 초과를 받았습니다. 제 코드의 테스트 결과 n=1,000,000으로 설정하였을 경우 165초정도 소요되었었습니다. 따라서 이 문제를 해결하기 위해서 스택 자료구조를 사용하였습니다. 스택의 간단한 원리는 "후입선출(Last-In-First-Out..
2022.01.03 -
백준 1085, 직사각형에서 탈출
문제 https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 문제요약 1. (0,0), (w,h) 두점으로 만들어지는 직사각형에 내에 존재하는 (x,y)라는 점이 직사각형의 경계선까지 가기 위해서 필요한 최솟값(가로 또는 세로)을 구하시오. 문제풀이 예를 들어 x,y,w,h의 값이 6,2,10,3일때 그래프는 다음과 같이 생성된다. (x,y) 점이 직사각형안에 존재할때 어떤 방향이든 상관없이 (0,0) (w,h) 두점이 만든 직사각..
2021.10.22 -
백준 4948, 베르트랑 공준
문제 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제요약 1. 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있습니다. 2. 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 문제풀이 소수를 판별하기 위한 대표적인 방법은 어떤 수 N이 주어질때 2~N의 양의 제곱근까지 N이 나누어 떨어질때 합성수로 ..
2021.10.21 -
백준 1929, 소수 구하기
문제 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제요약 1. M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 2. (1 ≤ M ≤ N ≤ 1,000,000) 문제풀이 소수판별 방법 중에서 간단한 방법으로는 어떤 수 N의 양의 제곱근 이하의 수들로 N을 나눠서 한번이라도 나누어 떨어지면 합성수(소수아님), 아니면 소수라고 판정하는 방법이 존재합니다. 즉, 어떤 수 N이 주어지면 2~N의 제곱근까지 나누어보았을때 N이 한번이라도 나누어 떨어지면 N은 합성수입니..
2021.10.21 -
백준 11053, 가장 긴 증가하는 부분 수열
1. 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 2. 문제요약 수열 A가 주어졌을때 가장 긴 증가하는 부분 수열의 길이 값을 구하시오. 수열의 크기 N, 1
2021.10.14