프로그래밍 공방

문제 programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 문제해결방법 문제에 나와 있는 LZW 압축 과정을 그대로 코딩해줘서 풀었습니다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667package Programmers; import java.util.ArrayList;..

문제 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제해결방법 이 문제는 DP 배열에 날짜마다 받을 수 있는 최대 금액을 저장해서 풀었습니다. 1. 뒤에서부터 상담 일정표를 보며 DP 배열을 채워나갑니다. 예를 들어 N일에 Ti = 3, Pi = 30 이라는 상담이 있다면, DP[N+1]와 DP[N+3]+Pi을 비교해서 더 큰 값을 DP[N]에 저장합니다. 만약 상담 기간이 퇴사 일자를 넘어서 상담을 할 수 없는 경우에는 DP[N]에 DP[N+1]을 넣어줍니다. 2. DP 배열 중에 가장 큰 값이 최대 금액입니다. 코드 1234567891011121314151617181920212223242..

문제 www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제해결방법 1. 모든 국가(정점)를 모두 연결하는 가장 적은 종류의 비행기(간선)는 국가-1개이다.. 풀고나서 이렇게 풀어도 되나 생각했다.. 코드 1234567891011121314151617181920package baekjoon; import java.io.BufferedReader;import java.io.InputStreamReader;import java..

문제 programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 문제해결방법 1. 열쇠의 크기를 M, 자물쇠의 크기를 N이라고 했을때, M+2*N 길이의 이차 배열을 만들어 준다. 2. 가운데에 키를 두고 자물쇠를 좌측 맨 위부터 우측 M+N 까지 돌면서 키로 열리는지 확인한다. 3. 위 과정을 키를 회전시켜가며 반복한다. 4. 반복 중에 자물쇠가 열린다면 true, 열리지 않는다면 false를 반환한다. 코드 1234567891011121314151617181920212223242..

문제 www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 문제해결방법 이 문제는 단순 구현, BFS를 통해 풀었다. 1. 회전 시킬 배열의 좌측 상단 좌표와 길이를 입력으로 받아서 배열을 회전시키는 rotation이라는 함수를 만들었다. 2. 칸마다 인접한 칸을 확인해서 배열의 칸마다 얼음의 양을 결정하는 check 함수를 만들었다. 3. 위 과정을 통해 마지막 배열을 구하고 BFS를 돌면서 남아있는 얼음의 합과 가장 큰 덩어리의 칸의 개수를..

문제 programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이 programmers.co.kr 문제해결방법 이 문제는 마지막 트럭이 들어가는 시간이 중요하다고 생각했다. 1. 시간 T를 증가시켜가며 큐에 트럭을 집어넣는다. 2. N번 트럭이 다리에 오를 때 다리가 견디는 무게를 초과하면 큐의 앞부터 N번 트럭이 올라갈 수 있을 때까지 트럭을 뺀다. 3. 트럭을 빼면서 트럭이 들어간 시간과 다리의 길이를 이용해서 트럭이 다리에서 나오는 시간을 계산한..

문제 https://programmers.co.kr/learn/courses/30/lessons/17676 코딩테스트 연습 - [1차] 추석 트래픽 입력: [ 2016-09-15 20:59:57.421 0.351s, 2016-09-15 20:59:58.233 1.181s, 2016-09-15 20:59:58.299 0.8s, 2016-09-15 20:59:58.688 1.041s, 2016-09-15 20:59:59.591 1.412s, 2016-09-15 21:00:00.464 1.466s, 2016-09-15 21:00:00.741 1.581s, 2016-09-15 21:00:00.748 programmers.co.kr 문제해결방법 입력값으로 받는 hh:mm:ss.sss과 처리시간 Ts 를 이용해서 ..

문제 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다. 문제해결방법 먼저 이 문제를 해결하기 전에 LIS를 살펴보자. LIS를 푸는 방법은 두 가지가 있다. 첫 번째 방법은 DP를 이용해서 푸는 방법이다. 현재 위치보다 앞에 있는 숫자들 중에 현재 숫자보..

문제 https://www.acmicpc.net/problem/9436 문제해결방법 실제로 주어진 N과 T를 사용해서 리스트를 순회하면서 T번 마다 노드를 제거해주고 모든 노드의 값이 같은지 확인해준다. POINT 위 방법이 마음에 안 들어서 인터넷을 찾아보았다. 이 문제의 핵심은 "남은 나머지를 다시 T에 더한다" 였다. 나머지가 플레이어로 나누어 떨어지거나 하나 더 받는 플레이어가 게임에서 나가는 경우에 반복문을 탈출한다. 해당 방법으로 푼 코드는 추후에 업데이트 하겠습니다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546package blogQueue; import java.io.Buffere..

문제 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. 입력 첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다. 출력 첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다. 문제해결방법 지금 수의 자리가 N 이라면 바로 전에 올 수 있는 수는 0 ~ N (바로 전에 오는 수가 0인 모든 경우 ~ N인 모든 경우) 까지이다. 코드 1234567891011121314151617181920212223..