본문 바로가기

Problem Solving173

[Problem Solving] BOJ 19238: 스타트 택시 문제 출처: https://www.acmicpc.net/problem/19238 BFS + 구현 문제이다. 먼저 현재 위치에서 최단거리가 가장 짧은 승객을 골라야한다. 하지만 그런 승객이 여러 명이면 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 열 번호가 가장 작은 승객을 고른다. 이를 위해서 처음에 승객의 위치를 입력 받을 때, 행을 기준으로, 행이 같으면 열을 기준으로 오름차순으로 정렬한다. flag가 true일 동안 다음을 반복한다.BFS를 수행해 현재 택시 지점에서 승객들 까지의 거리를 계산한다.정렬된 승객 리스트에서 가장 택시와 가까운 승객을 골라서 minDist와 idx를 갱신한다.택시와 가장 가까운 승객이 있다면 idx가 -1이 아니다. (idx = -1이면 flag를 false로.. 2025. 8. 15.
[Problem Solving] 프로그래머스 SQL 고득점 Kit: 특정 세대의 대장균 찾기 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/301650 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 3세대 대장균의 ID를 오름차순으로 출력하는 문제이다. 1세대 대장균으로 취급할 테이블, 2세대 대장균으로 취급할 테이블, 3세대 대장균으로 취급할 테이블 3개를 다음 조건으로 JOIN하면 된다. 1. 1세대 대장균으로 취급할 테이블의 PARENT_ID는 NULL이라는 조건2. 2세대 대장균으로 취급할 테이블의 PARENT_ID와 1세대 대장균으로 취급할 테이블의 ID가 같다는 조건3. 3세대 대장균으로 취급할 테이블의 PARENT_ID와.. 2025. 8. 8.
[Problem Solving] BOJ 14786: Ax+Bsin(x)=C ② 문제 출처: https://www.acmicpc.net/problem/14786 A, B, C가 주어졌을 때, 등식 Ax + Bsin(x) = C 를 성립하게 하는 x를 구하면 된다. 말 그대로 매개변수 탐색 문제이다. Ax + Bsin(x)를 반환하는 함수인 func(x)를 만든다. Ax + Bsin(x) = C 를 성립하게 하는 x는 0부터 무한대 사이에 무조건 존재한다.low = 0,high = 987654321로 설정한다. 정답과의 오차는 1e-9까지 허용한다고 문제에 주어졌으므로,abs(high-low)가 1e-9보다 크거나 같은 동안 매개변수 탐색을 수행하면 된다. mid = (low + high) / 2.0 으로 설정하고,이 mid값을 대입했을 때 반환되는 함숫값은 func_val에 저장한다.. 2025. 8. 7.
[Problem Solving] BOJ 15927: 회문은 회문아니야!! 문제 출처: https://www.acmicpc.net/problem/15927 알파벳 대문자로 이루어진 문자열이 주어졌을 때, 팰린드롬이 아닌 가장 긴 부분문자열의 길이를 구하는 문제이다. 주어진 문자열의 길이를 n이라고 하자. 주어진 문자열 자체가 팰린드롬이 아닐 경우 -> n을 그대로 출력한다. 주어진 문자열 자체가 팰린드롬일 경우문자열 안 모든 문자가 같다면 -> -1을 출력한다.문자열 안 모든 문자가 같지 않은 팰린드롬이라면, 양쪽 끝에서 하나만 없애도 팰린드롬이 아니게 된다. -> n - 1을 출력한다. import sysread = sys.stdin.readlines = read().rstrip()n = len(s)if s != s[::-1]: print(n)else: if s.c.. 2025. 8. 6.
[Problem Solving] 프로그래머스 SQL 고득점 Kit: 상품을 구매한 회원 비율 구하기 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/131534 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 일단 2021년에 가입한 회원 중 상품을 구매한 회원수를 먼저 구해야한다. 다음과 같은 쿼리를 일단 작성해볼 수 있다.SELECT YEAR(S.SALES_DATE) AS YEAR, MONTH(S.SALES_DATE) AS MONTH, S.USER_IDFROM USER_INFO AS UJOIN ONLINE_SALE AS SON U.USER_ID = S.USER_IDWHERE YEAR(U.JOINED) = '2021' 그룹핑이 없는 이 쿼리를.. 2025. 8. 6.
[Problem Solving] BOJ 21758: 꿀 따기 문제 출처: https://www.acmicpc.net/problem/21758 N개의 장소가 있을 때,두 꿀벌이 위치할 장소와, 벌통을 지정한다.꿀벌은 벌통 방향으로 날아가면서 꿀을 따는데, 다른 꿀벌이 있던 자리에 있는 꿀은 따지 않는다고 할 때, 벌들이 딸 수 있는 최대 꿀의 양을 구하는 문제이다. 일단 딸 수 있는 최대의 꿀을 얻기 위해서는 양쪽 끝에 꿀벌들이 있거나, 벌통이 있어야 한다.이 때 세 가지 경우가 존재한다.왼쪽 끝, 가운데 어딘가, 오른쪽 끝에꿀벌, 벌통, 꿀벌꿀벌, 꿀벌, 벌통벌통, 꿀벌, 꿀벌로 존재하는 것이다. 1) 꿀벌 - 벌통 - 꿀벌일단 좌,우 에서 꿀벌들이 벌통을 향해 오기 때문에, accSum[N]에 벌통에 위치한 꿀의 양인 arr[i]을 한번 더 더해주고(꿀벌 둘이서.. 2025. 8. 5.
[Problem Solving] BOJ 14442: 벽 부수고 이동하기 2 문제 출처: https://www.acmicpc.net/problem/14442 벽을 최대 K개 부술 수 있을 때, (0, 0)부터 (N - 1, M - 1)까지 도달할 수있는 최단 거리를 구하는 문제이다. 우선 Point를 정의해야하는데, Point는 좌표 y, x와 해당 좌표까지 도달하는데 부순 벽의 개수(counter)다. dist[i][j][k]는 (0, 0)부터 (i, j) 까지 도달 하는데, k개의 벽을 부쉈을 때의 최단 거리이다. 시작점의 Point는 (0, 0, 0)이 된다.시작점에서 BFS를 수행하는데, 인접한 곳이 열린 공간이고, 그 공간 까지의 최단 거리가 현재 지점의 dist에 1 증가시킨 값보다 크다면 counter를 유지한 채로 최단 거리를 갱신한다.인접한 곳이 벽이고, 부술 .. 2025. 8. 4.
[Problem Solving] 프로그래머스 SQL 고득점 Kit: 대장균의 크기에 따라 분류하기 2 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/301649 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 대장균 개체의 크기를 내림차순으로 정렬하였을 때, 4개의 분위로 나누어서, 1분위는 CRITICAL, 2분위는 HIGH, 3분위는 MEDIUM, 4분위는 LOW라고 분류하여 ID와 함께 출력하면 되는 문제다. 대장균 개체의 크기를 내림차순으로 정렬하였을 때의 기준에서 4개의 분위를 나누어야 하므로,CASE NTILE(4) OVER (ORDER BY SIZE_OF_COLONY DESC)를 사용하면 된다. 정답 쿼리는 다음과 같다. SELE.. 2025. 8. 4.
[Problem Solving] BOJ 2240: 자두나무 문제 출처: https://www.acmicpc.net/problem/2240 예제 입력에 대한 DP 테이블은 다음과 같이 구성할 수 있다. 행은 지난 초를 의미하고, 열은 사람이 움직인 횟수를 의미한다. dp[i][j]는 i초까지 j번 움직였을 때, 얻을 수 있는 최대 자두 수를 의미한다. 처음에 사람은 1번 나무에 서있기 때문에 움직이지 않는다(j가 0)면 시간이 지나면서 1번 나무에서 떨어지는 것만 받는다. (t - 1) 시점까지 사람이 w번 움직였을 수도 있고, (w - 1)번 움직였을 수도 있다. t시점까지 w번 움직인 상태라면 "(t - 1) 시점까지 w번 움직이고 그 자리에서 1초 가 지난 것" 일 수도 있고, "(t - 1) 시점까지 (w - 1)번 움직이고 1초가 지나면서 1회 더 움직.. 2025. 8. 3.
[Problem Solving] BOJ 9328: 열쇠 문제 출처: https://www.acmicpc.net/problem/9328 도면이 다음과 같이 주어져있다.*****************.............**$**B*A*P*C**X*Y*.X.*y*x*a*p**$*$**$****************** *은 벽면으로 이동할 수 없는 곳이고, 대문자 알파벳은 문이고, 소문자 알파벳은 대문자 알파벳의 문을 열 수 있는 키가 있는 곳이다. 외곽에서부터 출발 할 수 있다고 할 때, 모을 수 있는 $의 최대 개수를 구하는 문제이다. 일단 주어지는 키 들은 keys라는 해시맵에서 관리한다. 키가 존재하면 true, 존재하지 않는다면 false다. 이 문제는 BFS를 사용해야하는 구현 문제이다. bfs 결과에 따라서 키의 개수와 입구의 개수가 바뀌게 된다.. 2025. 8. 2.
[Problem Solving] BOJ 17951: 흩날리는 시험지 속에서 내 평점이 느껴진거야 문제 출처: https://www.acmicpc.net/problem/17951 배열에 숫자들이 있을 때 순서를 유지한 채로 K개의 그룹으로 분할했을 때의 각각의 그룹에 있는 수의 합을 구해 그 중 최솟값을 최대화 하는 문제이다. low = 0, high = 20 * N으로 설정 하고 low 1. mid = (low + high) / 2로 설정한다.2.2-1. 각각의 그룹에 있는 수의 합이 최소 mid보다 크거나 같게 되어 모두 mid 이상이 될 때, 그 그룹이 K개 이상이 된다면, 일단 answer = mid로 설정하고, low = mid + 1로 설정하여 더 mid값이 주어질 때, 그룹이 K개 이상 형성 되는지 확인한다.2-2. 각각의 그룹에 있는 수의 합이 최소 mid보다 크거나 같게 되어 모두.. 2025. 8. 1.
[Problem Solving] BOJ 1414: 불우이웃돕기 문제 출처: https://www.acmicpc.net/problem/1414 N*N 행렬에 컴퓨터간 연결된 랜선의 길이가 주어진다.a~z는 1~26이고A~Z는 27~52이다. 일단 그래프를 만드는데, 자기 자신으로 다시 돌아오는 엣지는 제외하고, 중복되는 간선이 있다면 가중치가 가장 작은 것을 택한다.이제 이 그래프를 통해, 최소 신장 트리를 만들고, 그 최소 신장 트리에 있는 간선의 가중치의 합만큼을 전체 가중치에서 뺀 값을 출력하면 된다. 모든 컴퓨터가 연결되어있지 않으면 -1을 출력하면 되는데, 한 노드에서 시작하는 BFS를 한번 시행해서 모든 노드 방문을 시도 한다. 그래도 방문하지 않은 노드가 하나라도 있으면 -1을 출력하면 된다. 최소 신장 트리에 관한 포스트: https://junstory.. 2025. 7. 31.
[Probelm Solving] 프로그래머스 SQL 고득점 Kit: 대장균들의 자식의 수 구하기 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/299305 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 대장균의 데이터가 있는 테이블이 있다. 이 테이블에는 대장균의 ID와 부모 대장균의 ID가 있다. 대장균의 자식의 수를 알기 위해서는 해당 대장균이 PARENT_ID에서 몇 번 등장하는지를 세면 알 수 있는 것이다. ECOLI_DATA 두 테이블을 ID와 PARENT_ID로 JOIN해서 ID를 GROUPING해서 COUNT하면 자식의 수가 0이 아닌 대장균들의 자식의 수를 구할 수 있다. SELECT A.ID, COUNT(*) AS CHI.. 2025. 7. 31.
[Problem Solving] BOJ 2457: 공주님의 정원 문제 출처: https://www.acmicpc.net/problem/2457 N개의 꽃이 피고 지는 날을 입력 받는다.3월 1일부터 11월 30일 까지 매일 꽃이 한 가지 이상 피어 있도록 해야한다.이 때 심는 꽃의 수의 최솟값을 구해야한다. 일단 꽃이 피고 지는 날을 정렬해야 하는데, 입력 받은 그대로를 정렬하기에는 어려움이 있다.그래서 1월 1일을 의미하는 1 1 은 101로,5월 31일을 의미하는 5 31은 531로,12월 10일 의미하는 12 10은 1210로 바꿔서 저장한 다음에 정렬할 것이다.다음과 같이 입력이 주어진다고하자.102 15 3 234 12 6 55 2 5 319 14 12 246 15 9 36 3 6 152 28 4 256 15 9 2710 5 12 317 14 9 1 이를 정.. 2025. 7. 30.
[Problem Solving] BOJ 2251: 물통 문제 출처: https://www.acmicpc.net/problem/2251 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하면 된다. 물통의 상태로 BFS를 수행하면.. 2025. 7. 29.

티스토리툴바