목록PS (97)
Koo's.Co
2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 위상정렬을 이용한 기본 문제입니다. 1) 진입 차수를 저장할 리스트 2) graph의 형태를 저장할 리스트 진입차수 진입 차수는 간선의 화살표를 받는 개수를 의미합니다. (도착지가 되는 횟수) 1은 0 2는 1에서부터 오므로 1 3은 1에서부터 오므로 1 4는 2와 3으로부터 오므로 2 5는 2와 4로부터 오므로 2 구하고자 하는 진입차수는 [0, 1, 1, 2, 2] 가 됩니다. 1) queue를 생성하고 진입차..
2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이 위상 정렬과 dp를 이용해 풀 수 있는 문제입니다. ACM Craft 문제와 거의 동일한 문제인 것 같습니다. 먼저 위상 정렬을 이용해 각 값들의 진입 차수를 구해준 후 bfs를 사용했습니다. 작업을 하기 위해서는 선행 작업들을 모두 수행해야 하기 때문에 dp리스트를 만들어 이전 작업들 중 가장 시간이 오래 걸린 값들만 저장해줍니다. -> max를 이용해 노드에 한 번 도착할 때마다 값을 갱신! 모든 작업이 완료된 시간을 구해야하기 때문에 max를..
1. 1, 2, 3 더하기 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 새로 오는 수는 그 전의 숫자들에 각각 1, 2, 3을 더해 만들 수 있다. 4의 경우 이전 3개의 숫자에 1, 2, 3을 더해 만들 수 있다. 그러므로 구하고자 하는 점화식은 위와 같다. import sys read = sys.stdin.readline dp = [0, 1, 2, 4] + [0] * 7 for i in range(4, 11): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] for _ in range(int(read())): print(dp[int(read())]) 2. 1, 2, 3 더하기 2..
16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 bfs를 사용해서 푸는 문제입니다. 문제의 조건이 많은데 하나씩 살펴보며 풀어보겠습니다. 상하좌우 이동 가능 -> directions = [(-1, 0), (0, -1), (1, 0), (0, 1)] 상어와 물고기는 크기를 갖고 있음 처음 상어 크기 = 2 -> shark_size = 2 물고기의 크기 = 1 ~ 6 상어보다 "작은" 물고기만 먹을 수 있다 상어와 크기가 "같은" 물고기는 지나갈 수 있다 상어보다 크기가 "큰" 물고기는 지나갈 수 없다..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr PRODUCT ORDER 문제 PRODUCT 테이블과 OFFLINE_SALE 테이블에서 상품코드 별 매출액(판매가 * 판매량) 합계를 출력하는 SQL문을 작성해주세요. 결과는 매출액을 기준으로 내림차순 정렬해주시고 매출액이 같다면 상품코드를 기준으로 오름차순 정렬해주세요. SELECT P.PRODUCT_CODE, SUM(P.PRICE * O.SALES_AMOUNT) AS SALES FROM PRODUCT AS P INNER JOIN OFFLINE_SALE AS O ON P.PRODUCT_ID = O.PRODU..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ONLINE_SALE 문제 ONLINE_SALE 테이블에서 동일한 회원이 동일한 상품을 재구매한 데이터를 구하여, 재구매한 회원 ID와 재구매한 상품 ID를 출력하는 SQL문을 작성해주세요. 결과는 회원 ID를 기준으로 오름차순 정렬해주시고 회원 ID가 같다면 상품 ID를 기준으로 내림차순 정렬해주세요. SELECT USER_ID, PRODUCT_ID FROM ONLINE_SALE GROUP BY USER_ID, PRODUCT_ID HAVING COUNT(*) >= 2 ORDER BY USER_ID ASC, ..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr APPOINTMENT 문제 APPOINTMENT 테이블에서 2022년 5월에 예약한 환자 수를 진료과코드 별로 조회하는 SQL문을 작성해주세요. 이때, 컬럼명은 '진료과 코드', '5월예약건수'로 지정해주시고 결과는 진료과별 예약한 환자 수를 기준으로 오름차순 정렬하고, 예약한 환자 수가 같다면 진료과 코드를 기준으로 오름차순 정렬해주세요. SELECT MCDP_CD AS "진료과코드", COUNT(MCDP_CD) AS "5월예약건수" FROM APPOINTMENT WHERE LEFT(APNT_YMD, 7) ..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr FIRST_HALF ICECREAM_INFO 문제 상반기 동안 각 아이스크림 성분 타입과 성분 타입에 대한 아이스크림의 총주문량을 총주문량이 작은 순서대로 조회하는 SQL 문을 작성해주세요. 이때 총주문량을 나타내는 컬럼명은 TOTAL_ORDER로 지정해주세요. SELECT IC.INGREDIENT_TYPE, SUM(FH.TOTAL_ORDER) AS TOTAL_ORDER FROM FIRST_HALF AS FH INNER JOIN ICECREAM_INFO AS IC ON FH.FLAVOR = IC.FLAVOR ..