본문 바로가기

Problem Solving208

[Problem Solving] BOJ 8980: 택배 문제 출처: https://www.acmicpc.net/problem/8980 본부에서 N번째 마을까지 이동할 때, 배송할 수 있는 최대 박스 개수를 출력해야하는 문제다. 우선 목적지를 기준으로 오름차순 정렬하고, 목적지가 같다면 출발지를 기준으로 오름차순 정렬한다. 목적지가 현재 트럭이 향하고 있는 곳 중에 가장 가까운곳에 먼저 박스를 내려야하고, 왼쪽에서 적재한 박스부터 우선적으로 내려야하기 때문이다. 우선 구간별 적재 가능량을 모두 C로 설정한다. 박스의 목적지가 e라면 [s, e) 구간에서 적재 가능량이 가장 조금 남은 것을 구해서, [s, e)에서 그 만큼 빼준다. C가 60이고, remain이 다음과 같은 상황(중간 과정은 생략)이라고 가정하자{30, 60, 20, 60, 60, 60} 2에서.. 2025. 8. 27.
[Problem Solving] BOJ 2660: 회장 뽑기 문제 출처: https://www.acmicpc.net/problem/2660 문제에서 말하는 점수는 한 노드에서 다른 노드까지의 최단거리 중 가장 큰 값을 의미한다. 모든 노드 사이의 최단 거리를 구해야하므로 플로이드워셜 알고리즘을 사용하는게 적합하다. 노드의 수도 50개 이기 때문에 연산이 최대 50^3 발생해도 1초 안에는 해결 가능 하다. 먼저 플로이드 워셜 알고리즘을 사용해서 각 노드에서 다른 노드까지의 최단 거리 중 가장 큰 값을 알아낼 수 있다.그 값들 중에 가장 작은 값을 가진 노드들이 회장 후보가 된다.가장 작은 값을 찾고, 그 작은 값과 일치하는 최단 거리 중 가장 큰 값을 가진 노드들의 번호를 answers에 저장한 후, 가장 작은 값, answers의 크기,answers에 있는 노드.. 2025. 8. 26.
[Problem Solving] BOJ 2342: Dance Dance Revolution 문제 출처: https://www.acmicpc.net/problem/2342 DDR 게임 지시 사항이 주어졌을 때, 주어진 지시 사항을 만족하는 데 사용하는 최소의 힘을 출력하는 문제다. 우선 DP테이블을 다음과같이 정의할 수 있다.DP[i][left][right]는 i번째 지시 사항까지 수행했을 때, 왼발이 left에 있고, 오른발이 right에 있는 경우 누적된 최소의 힘이다. 지시 사항이 총 N개 라면, DP[N][left][right] 중에 가장 작은 것을 고르면 된다. 다음 지시 사항이 next 라면, dp[i + 1][next][right], 와 dp[i + 1][left][next]를 갱신할 수 있다.dp[i + 1][next][right]를 갱신할 때는, 기존 dp[i + 1][next].. 2025. 8. 25.
[Problem Solving] BOJ 17837: 새로운 게임 2 문제 출처: https://www.acmicpc.net/problem/17837 문제 명세를 보고 그대로 구현하면 된다.특별한 알고리즘은 필요하지 않다. 오류없이 실행되도록 유의하면 된다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public static class Piece { public int y; public int x; public int d; public Piece(int y, int x, int d) { thi.. 2025. 8. 24.
[Problem Solving] 프로그래머스 SQL 고득점 Kit: 특정 조건을 만족하는 물고기별 수와 최대 길이 구하기 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/298519 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr LENGTH 가 NULL인 물고기들은 10으로 취급해야 하기 때문에 IFNULL을 사용해서 결측값을 채운다. 물고기를 종류별로 그룹핑해서 평균길이가 33 이상인 것들만 필요로 하기 때문에, GROUP BY로 그룹핑한 후, HAVING 절로 평균 길이가 33 이상인 것 들만 추릴 수 있다. FISH_TYPE 그룹에 대해서 COUNT와 MAX 집계함수를 사용하면 그 그룹에 포함된 물고기의 수와, 가장 긴 물고기의 길이를 구할 수 있다. 정답 .. 2025. 8. 24.
[Problem Solving] BOJ 16566: 카드 게임 문제 출처: https://www.acmicpc.net/problem/16566 철수가 내려는 카드를 아는 민수는 그것보다 큰 카드 들 중에서 가장 작은거를 내면 된다. 철수가 내려는 카드보다 큰 것이 처음 나타나는 지점의 인덱스를 알면 된다. 고른 카드를 정렬하고, 철수가 내려는 카드의 upper_bound를 찾으면 된다. 이제 그 카드를 버려야하는데, 여기서 erase를 해버리면 O(KM)이 되기 때문에, 시간 초과가 난다. M을 log M 연산으로 변환하기 위해 Union Find를 도입할 수 있다. 우선 모든 카드의 parent를 자기 자신의 index로 설정한다. 철수가 내려는 카드보다 큰 것을 찾으려고 할 때, 찾은것의 parent index를 찾고, 그 index가 위치한 곳에 있는 카드 번.. 2025. 8. 23.
[Problem Solving] 프로그래머스 SQL 고득점 Kit: 연간 평가점수에 해당하는 평가 등급 및 성과금 조회하기 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/284528 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr HR_DEPARTMENT 테이블은 HR_EMPLOYEE와 DEPT_ID로 연관되어 있고, HR_EMPLOYEES 테이블은 HR_GRADE 테이블과 EMP_NO로 연관되어 있다. 이 필드들을 사용해서 테이블을 JOIN할 수 있다.JOIN한 테이블에서 EMP_NO과 EMP_NAME으로 그룹핑해서 2022년의 평균 평가점수를 계산할 수 있다. 96점을 넘기면 GRADE를 S로 출력하고, SAL에 0.2를 곱한 것이 BONUS,90점을 넘기면 G.. 2025. 8. 23.
[Problem Solving] BOJ 2608: 로마 숫자 문제 출처: https://www.acmicpc.net/problem/2608 로마숫자를 입력 받아서 합한 다음, 아라비아 숫자와 로마 숫자로 출력하는 문제이다. 먼저 로마 숫자를 아라비아 숫자로 변환할 때, 앞에 두개가 아라비아 숫자로 만들 수 있는 건지 확인먼저 하고 그렇지 않다면 앞에 하나를 아라비아 숫자로 만들 수 있는 건지 확인한다. 아라비아 숫자를 로마 숫자로 변환할 때는, (아라비아 숫자, 로마 숫자) 쌍을 내림차순으로 정렬해 놓고, 큰 수 부터 뺄 수 있는 만큼 빼고 그것의 로마 숫자를 하나씩 추가한다. import sysread = sys.stdin.readlinerom = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, .. 2025. 8. 22.
[Problem Solving] 프로그래머스 SQL 고득점 Kit: 언어별 개발자 분류하기 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/276036 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr GROUP_CONCAT를 활용해야 하는 문제다. SKILLCODES와 DEVELOPERS를 JOIN해서, ID와 EMAIL로 그룹핑한다. 그룹핑 했을 때, 그 그룹의 SKILLCODES.NAME들과 SKILLCODES.CATEGORY들이 각각 문자열로 CONCAT 되어 한 행에 한 개발자의 SKILLCODES.NAME들과 SKILLCODES.CATEGORY가 한번에 보여야 한다. 이를 GROUP_CONCAT를 사용하여 구현할 수 있다. G.. 2025. 8. 22.
[Problem Solving] BOJ 1911: 흙길 보수하기 문제 출처: https://www.acmicpc.net/problem/1911 무수히 많은 널빤지가 준비되어있을 때, 웅덩이를 덮기 위한 널빤지의 최소 개수를 구하는 문제이다. 수직선 위에 웅덩이의 시작과 끝이 표시되어있다고 생각하고, 왼쪽에서 오른쪽 끝으로 이동하면서 널빤지로 덮어줘야 한다. covered라는 변수를 -1로 초기화한다. 이는 널빤지로 가장 최근에 덮힌 좌표를 의미한다.covered가 웅덩이의 시작 지점은 s보다 앞이라면, covered를 s로 변경한다.covered가 웅덩이의 시작 지점과 같거나 뒤라면, covered를 covered + 1로 변경한다. 새로 덮는 널빤지의 개수는 count = ceil((e - covered) / L)가 되고, 덮은 후 널빤지로 가장 최근에 덮힌 좌표는.. 2025. 8. 21.
[Problem Solving] 프로그래머스 SQL 고득점 Kit: 입양 시각 구하기(2) 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/59413 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 시간대 별 입양이 일어난 횟수를 구하는 문제이다. HOUR라는 Column을 만들어야하는데, ANIMAL_OUTS에다가 만들면 입양이 일어나지 않은 시간은 존재하지 않는다. 그러므로 모든 시간이 존재하는 테이블을 만들어서, HOUR(ANIMAL_OUTS.DATETIME)과 LEFT JOIN한다. HOURS라는 테이블을 다음과 같이 재귀 쿼리로 만들 수 있다.WITH RECURSIVE HOURS AS ( SELECT 0 AS HOUR .. 2025. 8. 21.
[Problem Solving] BOJ 1963: 소수 경로 문제 출처: https://www.acmicpc.net/problem/1963 4자리 소수 A에서 4자리 소수 B로 변환하는 최소 단계를 구하는 문제이다. 단계마다 한 자리의 숫자를 바꿀 수 있으며, 바꿔서 만들어진 수는 소수여야 한다. 일단 에라스토테네스의 체로 소수 판별을 위한 isPrime 배열을 만든다. 그 다음 최단 경로를 구하는 BFS를 수행 한다. 바뀌기 전 수를 cur라고 하고,한 자리의 숫자를 바꿔서 바뀐 소수를 next라고 하자.dist[next] > next[cur] + 1이라면 dist[next] = next[cur] + 1로 설정 하고 queue에 넣는다. BFS수행 후에도 dist[B]가 무한대여서 도달 불가능 하다면 Impossible을 출력하고, 도달 가능 하다면 dist[B.. 2025. 8. 20.
[Problem Solving] BOJ 1106: 호텔 문제 출처: https://www.acmicpc.net/problem/1106 호텔의 고객을 적어도 C명 늘이기 위해 투자해야 하는 돈의 최솟값을 구해야한다. 먼저 DP테이블을 정의하자면,DP[i]는 i명의 고객을 늘이기 위해 필요한 돈의 최솟값이다.5명을 늘리는데 3원이 들고, 1명을 늘리는데 1원이 든다면, dp[5]전 까지는, 5명을 늘리는데 사용해야 하는 금액인 3원을 쓰지 않는다. dp[4]를 계산할 때는 굳이 5명을 늘리는데 사용하는 금액은 취급하지 않고, 4이하의 인원수를 늘리는데 사용하는 금액만 쓰기 때문에 dp[4]는 4다. 그리고 적어도 C명 늘이기 위해 투자해야 하는 돈의 최솟값이기 때문에, C명 이상 늘이기 위해 투자해야 하는 금액 중 최솟값을 고르면 된다. 이는 min(DP[C:].. 2025. 8. 18.
[Problem Solving] 프로그래머스 SQL 고득점 Kit: 년, 월, 성별 별 상품 구매 회원 수 구하기 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/131532 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr USER_INFO와 ONLINE_SALE은 USER_ID라는 공통의 Column을 가지고 있기 때문에, 이를 JOIN하는 데 사용할 수 있다.그냥 JOIN해서 년, 월, 성별을 출력하면, 동일한 년, 월에 구매한 회원이 중복으로 출력된다. 그렇기 때문에 USER_ID에 DISTINCT를 걸어서 중복을 제거한다.서브쿼리는 다음과 같다.SELECT DISTINCT UI.USER_ID, YEAR(SALES_DATE) AS YEAR, MONTH(.. 2025. 8. 18.
[Problem Solving] 프로그래머스 SQL 고득점 Kit: 멸종위기의 대장균 찾기 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/301651 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 세대를 알기 위해서 재귀 쿼리를 사용해야하는 문제다.WITH RECURSIVE GENERATIONS AS ( SELECT ID, PARENT_ID, 1 AS GENERATION FROM ECOLI_DATA WHERE PARENT_ID IS NULL UNION ALL SELECT C.ID, C.PARENT_ID, P.GEN.. 2025. 8. 17.

티스토리툴바