티스토리

복습노트

검색하기

블로그 홈

복습노트

riveroilstone.tistory.com/m

컴퓨터 공학과 복전생 복습노트

구독자: 0

방명록 방문하기

주요 글 목록

카테고리 별 상품개수 구하기 (oracle) 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.krPRODUCT 테이블에서 상품 카테고리 코드(PRODUCT_CODE 앞 2자리) 별 상품 개수를 출력하는 SQL문을 작성해주세요. 결과는 상품 카테고리 코드를 기준으로 오름차순 정렬해주세요. SELECT SUBSTR(PRODUCT_CODE, 1, 2) CATEGORY, COUNT(*) productsFROM PRODUCTGROUP BY SUBSTR(PRODUCT_CODE, 1, 2)ORDER BY CATEGORY PRODUCT_CODE의 앞 두 자리를 뽑아내기 위해 SUBSTR함수를 사용했다. GROUP BY.. 공감수 0 댓글수 0 2024. 5. 11.
도둑질 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr n개의 집이 있으면 각각 돈이 있다. 서로 이웃하지 않는 선에서 돈을 훔칠 때 가장 최댓값을 구하라. 단순히 생각하면 dp[i] = Math.max(dp[i-1], dp[i-2] + money[i]) 라고 점화식을 세울 수 있다. 하지만 집이 원형으로 이뤄져 있다는 점에서 다르게 생각해 주어야 한다. 즉, 첫번째 집을 선택하면 맨 마지막 집을 선택할 수 없습니다. 반대로 첫번째 집을 선택하지 않고 두번째 집을 선택하면 마지막 집까지 선택할 수 있습니다. 이를 dp 식으로 표현하면 아래와 같다. class.. 공감수 0 댓글수 1 2024. 4. 18.
백준 2294 (동전 2) <배낭> 문제 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 예를 들어 동전이 3개 주어지고, 각각 1, 5, 12 이고, k = 15이면 정답은 3이다. 전형적인 배낭 문제이다. int []coin = new int[n+1]; int []dp = new int[k+1]; for(int i=.. 공감수 0 댓글수 0 2024. 4. 17.
백준 19236 (청소년 상어) 문제 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 4 * 4 크기의 칸에서 1 ~ 16번까지의 물고기가 들어간다. 처음 상어는 [0][0]에서 물고기를 먹고 물고기는 이동한다. 물고기가 이동하면 상어는 방향에 따라 갈 수 있는 공간에서 물고기를 하나 먹을 수 있다. 이러한 반복을 상어가 물고기를 못먹을 때 까지 반복한다. 정리하면 다음과 같다. 1. 상어는 물고기를 먹을 수 있으면 먹는다. 2. 1번 물고기 부터 시작해서 16번 물고기 까지 이동을 한다. 만약 이동을 못하게 되면 45도 반.. 공감수 0 댓글수 1 2024. 4. 5.
디스크 컨트롤러 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 작업 순서를 설정해 작업 시간을 최소로 하는 문제이다. 예를 들어 - 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청 그림으로 표현하면 아래와 같다. 이것을 차례대로 처리하면 아래 그림과 같다. 이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 된다. 하지만 A → C → B 순서대로 처리하면 이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료.. 공감수 0 댓글수 0 2024. 3. 21.
백준 9084 (동전) <배낭 문제> 문제 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net n개의 서로 다른 금액의 동전이 주어지면 동전을 조합해서 m의 금액이 나올 수 있는 경우의 수를 구하는 문제이다. 예를 들어 n은 3이고 서로다른 동전은 2, 3, 5라고 할 때 m = 10이면 정답은 4가 된다. {2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 3, 5}, {5, 5} 여러 규칙을 찾으려 노력했지만 이러한 문제 유형은 배낭 문제이다. 위에 예시를 기반으로 표를 만들면 다음과 같다. 이를 코드로 구현하면 아래와.. 공감수 0 댓글수 0 2024. 3. 21.
백준 9489 (사촌) <부모 노드 활용> 문제 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 왼쪽 그림과 같이 n개의 노드가 주어지면 트리를 형성할 수 있다. 트리는 연속된 숫자여야 한다. 연속된 숫자는 하나의 집합이다. 연속된 숫자가 아니면 다음 집합으로 넘어간다. 이 때 K가 주어지는데 K의 사촌 수를 구하는 문제이다. 사촌 이란 두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라고 한다. n개의 수는 오름차순으로 주어진다. 왼쪽의 예시는 1, 3, 4, 5, 8, 9, 15, 30, 3.. 공감수 0 댓글수 0 2024. 3. 20.
백준 18116 (로봇 조립) 문제 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 www.acmicpc.net 명령어는 I 또는 Q가 주어진다. I가 주어질 경우 노드 2개가 추가로 주어진다. 예를 들어 I 1 2 라면 1번 노드와 2번 노드를 연결한다는 것이다. Q가 주어질 경우 노드 1개가 추가로 주어진다. 예를 들어 Q 1이라면 1번 노드가 포함된 그래프의 노드 개수를 구해주면 된다. 즉 1번과 2번이 연결되있으므로 정답은 2가 된다. 노드를 서로 합치는 것이기 때문에 union-find 알고리즘을 사용하였다. 연결하는 것은 쉬운데 어떻게 같은 집합의 노드 개수를 .. 공감수 0 댓글수 0 2024. 3. 20.
백준 21939 (문제 추천 시스템 Version 1) 문제 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 처음에 n개의 {문제번호, 문제 난이도} 가 주어진다. 위에 규칙에 따라 구현해주면 된다. 명령어 recommend는 추천 문제 리스트에 문제가 하나 이상 있을 때만 주어진다. 명령어 solved는 추천 문제 리스트에 문제 번호가 하나 이상 있을 때만 주어진다. 먼저 생각난것이 이중 우선순위큐를 돌리자고 생각했다. 새로운 클래스를 만드는 것이다. class Hard implements Comparable { int num; in.. 공감수 0 댓글수 0 2024. 3. 20.
백준 1647 (도시 분할 계획) 문제 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 임의의 두 노드에서 모두 도달할 수 있는 그래프가 주어지고 각 노드 사이에는 비용이 있는 간선이 주어진다. 이 때 그래프를 둘로 나눈다. 나눈 각각의 그래프는 서로 연결되어 있어야 하고 간선의 합이 최소여야 한다. 두 그래프의 각각의 간선의 합이 최솟값을 구해라. 그래프는 최소 1개의 노드가 존재해야 한다. 문제를 잘보면 크루스칼 알고리즘을 사용하는 것을 알 수 있다. 하지만 어떻게 2개로 나눌까?? 잘 생각해보면 간단.. 공감수 0 댓글수 0 2024. 3. 19.
식품분류별 가장 비싼 식품의 정보 조회하기 (oracle) 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr FOOD_PRODUCT 테이블에서 식품분류별로 가격이 제일 비싼 식품의 분류, 가격, 이름을 조회하는 SQL문을 작성해주세요. 이때 식품분류가 '과자', '국', '김치', '식용유'인 경우만 출력시켜 주시고 결과는 식품 가격을 기준으로 내림차순 정렬해주세요. SELECT category, MAX(price) MAX_PRICE, product_name from food_product where category in ('과자', '국', '김치', '식용유') group by category order b.. 공감수 0 댓글수 0 2024. 3. 12.
가격대 별 상품 개수 구하기 (oracle) 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr PRODUCT 테이블에서 만원 단위의 가격대 별로 상품 개수를 출력하는 SQL 문을 작성해주세요. 이때 컬럼명은 각각 컬럼명은 PRICE_GROUP, PRODUCTS로 지정해주시고 가격대 정보는 각 구간의 최소금액(10,000원 이상 ~ 20,000 미만인 구간인 경우 10,000)으로 표시해주세요. 결과는 가격대를 기준으로 오름차순 정렬해주세요. SELECT floor(price/10000)*10000 price_group, count(product_code) products from product g.. 공감수 0 댓글수 0 2024. 3. 12.
자동차 종류 별 특정 옵션이 포함된 자동차 수 구하기 (oracle) 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr CAR_RENTAL_COMPANY_CAR 테이블에서 '통풍시트', '열선시트', '가죽시트' 중 하나 이상의 옵션이 포함된 자동차가 자동차 종류 별로 몇 대인지 출력하는 SQL문을 작성해주세요. 이때 자동차 수에 대한 컬럼명은 CARS로 지정하고, 결과는 자동차 종류를 기준으로 오름차순 정렬해주세요. SELECT car_type, count(car_type)CARS from car_rental_company_car where options LIKE '%통풍시트%' or options LIKE '%열선시트.. 공감수 0 댓글수 0 2024. 3. 12.
진료과별 총 예약 횟수 출력하기 (oracle) 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr APPOINTMENT 테이블에서 2022년 5월에 예약한 환자 수를 진료과코드 별로 조회하는 SQL문을 작성해주세요. 이때, 컬럼명은 '진료과 코드', '5월예약건수'로 지정해주시고 결과는 진료과별 예약한 환자 수를 기준으로 오름차순 정렬하고, 예약한 환자 수가 같다면 진료과 코드를 기준으로 오름차순 정렬해주세요. SELECT MCDP_CD AS "진료과코드", COUNT(*) AS "5월예약건수" FROM APPOINTMENT WHERE to_char(APNT_YMD,'YYYY-MM') = '2022-.. 공감수 0 댓글수 0 2024. 3. 12.
상품 별 오프라인 매출 구하기 (oracle) 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr PRODUCT 테이블과 OFFLINE_SALE 테이블에서 상품코드 별 매출액(판매가 * 판매량) 합계를 출력하는 SQL문을 작성해주세요. 결과는 매출액을 기준으로 내림차순 정렬해주시고 매출액이 같다면 상품코드를 기준으로 오름차순 정렬해주세요. 각 상품 별 총 판매량과 판매가는 다음과 같습니다. PRODUCT_CODE 가 A1000011인 상품은 총 판매량이 6개, 판매가가 15,000원 PRODUCT_CODE 가 A1000045인 상품은 총 판매량이 2개, 판매가가 8,000원 PRODUCT_CODE 가.. 공감수 0 댓글수 0 2024. 3. 12.
백준 157877 (기차가 어둠을 헤치고 은하수를) 문제 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net N개의 기차가 어둠을 헤치고 은하수를 건너려고 한다. 기차는 20개의 일렬로 된 좌석이 있고, 한 개의 좌석에는 한 명의 사람이 탈 수 있다. 기차의 번호를 1번부터 N번으로 매길 때, 어떠한 기차에 대하여 M개의 명령이 주어진다. 명령의 종류는 4가지로 다음과 같다. 1 i x : i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 태워라. 이미 사람이 타있다면 , 아무런 행동을 하지 않는다. 2 i x : i번째 기차.. 공감수 0 댓글수 0 2024. 3. 12.
백준 22869 (징검다리 건너기 (small)) 문제 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 왼쪽부터 차례대로 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 www.acmicpc.net N개에 돌에 부여된 수 A1, A2, A3, ... An 이 있다. 여기서 맨 왼쪽 돌부터 오른쪽 방향으로만 이동하여 An에 도달할 수 있는지 구하는 문제이다. 문제의 조건은 다음과 같다. 돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 K이다. i번째 돌에서 j(i < j)번째 돌로 이동할 때 (j - i) × (1 + |Ai - Aj|) 만큼 힘을 쓴다. 내가 처음에 접근한 방법은 다음과 같다. d.. 공감수 0 댓글수 0 2024. 3. 9.
백준 2243 (사탕 상자) <세그먼트 트리> 문제 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 사탕상자에서 조건에 따라 사탕을 꺼내고 사탕의 맛을 출력하는 문제이다. 사탕의 맛은 1 ~ 100000 이고, 1이 제일 맛있는 맛이다. 입력은 처음에 n이 주어진다. n은 쿼리를 수행할 횟수이다. 이제 n번의 쿼리가 나온다. a = 1 일경우 a b가 입력으로 들어오고 순위가 b인 사탕으로 꺼내고 해당 사탕의 맛을 출력하는 것이다. a = 2 일 경우 a b c가 입력으로 들어오고 맛이 b인 사탕 c개를 추가해준다. 예를 들어 .. 공감수 0 댓글수 1 2024. 2. 25.
백준 6549 (히스토그램에서 가장 큰 직사각형) <세그먼트 트리> 문제 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net n개의 밑변의 길이가 1이고 높이가 다른 직사각형이 주어지면, 가장 큰 직사각형을 구하는 문제이다. 이전에 스택으로 푼 문제지만, 이번에는 세그먼트 트리를 이용해 문제를 풀어보겠다. 중요한 것은 0 ~ n-1 의 구간이 있으면, 구간을 돌아보면서 만들 수 있는 가장 큰 직사각형을 return 한다. 따라서 구간의 가장 큰 직사각형의 넓이는 구간 중 가장 작은 높이와 구간의 길이를 곱해주면 된다. 이를.. 공감수 0 댓글수 0 2024. 2. 22.
백준 11049 (행렬 곱셈 순서) <구간 DP> 문제 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net N개의 행렬이 주어지면 주어진 순서대로 행렬 곱을 할때 가장 적은 연산횟수를 구하는 문제이다. 예를 들어 A = (5, 3), B = (3, 2), C = (2, 6) 으로 주어졌다고 하면 AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다. BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 12.. 공감수 0 댓글수 0 2024. 2. 19.
백준 2423 (전구를 켜라) 문제 2423번: 전구를 켜라 첫째 줄에 문제의 정답을 출력한다. 전구에 불을 켜는 것이 가능하면, 몇 개의 칸을 돌려야 하는지를 출력하고, 불가능할때는 "NO SOLUTION"을 따옴표 없이 출력한다. www.acmicpc.net N * M의 직사각형이 주어진다. 또한 전선의 정보도 위와 같이 주어진다. 여기서 전선은 90도 회전할 수 있다. 이때 맨 왼쪽 상단에서 부터 시작해서 맨 오른쪽 하단에 도달할 때 전선의 회전횟수가 최소로 가게끔 하여 맨 아래 우측에 도달하는 전선의 최소 회전횟수를 구하는 문제이다. 위 예시에서 보면 4번째 열에 해당하는 모든 전선들은 90도 회전하면 전구에 도달할 수 있다. 입력 3 5 \\/\\ \\/// /\\\\ 정답 1 여기서 입력이 위와 같이 / 나 \ 로 주어지기.. 공감수 0 댓글수 1 2024. 2. 13.
백준 10844 (쉬운 계단 수) 문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 규칙을 찾아보자. N = 1이면 1, 2, 3, 4, 5, 6, 7, 8, 9 즉, 9개이다. N = 2이면 10, 12, 21, 23, 32, 34, ...78, 87, 89, 98 즉, 17개 이다. N = 3이면 101, 121, 123, 210, 212, .....878, 879, 898, 987, 989 즉, 32개이다. 규칙이 보이지 않는다. 처음에는 점.. 공감수 0 댓글수 0 2024. 2. 10.
백준 1890 (점프) 문제 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net N * N의 2차원 배열이 있으면 arr[0][0] 부터 시작해서 현재 위치한 값에 해당하는 만큼 오른쪽 과 아래로 점프할 수 있다. 이 때 arr[N-1][N-1]로 도달 할 수 있는 경우의 수를 구하는 문제이다. 예를 들어 그림 1과 같은 상황이 주어진다면 정답은 3이다. 먼저 dp식을 세울 수 있었다. dp[i][j] = x arr[i][j]에 도달할 수 있는 경우의 수는 x 개이다. 점화식을 세우는것은 어렵지 않았지만, 현재 위치에서 칸에.. 공감수 0 댓글수 0 2024. 2. 10.
백준 1912 (연속합) 문제 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net N개의 수열이 주어지면, 연속합이 가장 큰 최댓값을 구하는 문제이다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. dp를 사용할 것이다. dp[i] = i번째 인덱스까지 탐색한 최댓값이다. 따라서 처음 base case는 dp[0] = arr[0]이다. public class Main { public static void main(String[] args).. 공감수 0 댓글수 0 2024. 2. 8.
백준 12869 (뮤탈리스크) 문제 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net SCV가 최대 n명 주어진다. 뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다. 첫 번째로 공격받는 SCV는 체력 9를 잃는다. 두 번째로 공격받는 SCV는 체력 3을 잃는다. 세 번째로 공격받는 SCV는 체력 1을 잃는다. SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다. 남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟.. 공감수 0 댓글수 0 2024. 2. 6.
백준 1339 (단어 수학) 문제 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net n개의 영어 대문자로 주어진 문자열이 주어진다. 문자열의 알파벳에 0 ~ 9 까지의 숫자를 부여한뒤 n개의 문자열을 더했을 때 가장 큰 수가 나오게 하는 문제이다. 0~9 까지 이기 때문에 주어지는 모든 문자열의 알파벳은 최대 10가지이다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. 처음.. 공감수 0 댓글수 1 2024. 2. 5.
백준 11000 (강의실 배정) 문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net N개의 강의 시작 시간과 끝나는 시간이 주어진다. 강의를 모두 다 수용하는 최소한의 강의실의 개수를 구하는 문제이다. 만약 어떤 강의 시간이 끝나는 시간과 시작하는 시간이 같을 때 해당강의실은 동시에 사용이 가능하다. 전형적인 그리디 방법이다. 먼저 강의가 시작하는 시간을 기준으로 오름차순으로 정렬해주었다. class Class implements Comparable{ int start; int end; Class(int start, int end){ this.start = start; this.end =.. 공감수 0 댓글수 0 2024. 2. 2.
백준 9466 (텀 프로젝트) 문제 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net N개의 노드의 단방향 그래프 정보가 주어지면 사이클을 포함한 노드를 제외하고 노드가 몇개 있는지 구하는 문제이다. 노드는 항상 한개의 노드만 가리킬 수 있다. 처음 접근은 다음과 같다. N개의 노드마다 dfs를 진행하고, 처음 시작한 노드 번호가 사이클을 이룰 수 있는지 없는지 판단하는 것이다. 따라서 최악의 경우 N^2의 시간 복잡도를 갖게 된다. public class Main { private static int []list; private static i.. 공감수 0 댓글수 0 2024. 2. 2.
백준 11581 (구호물자) 문제 11581번: 구호물자 서기 2050년 엄청나게 강력한 폭풍이 인천을 강타했다. 강력한 폭풍의 영향으로 모든 사람은 대피소로 대피하였으며, 많은 도로가 유실되었다. 그나마 남아있는 도로도 모든 표지판과 가로등이 www.acmicpc.net N개의 정점이 주어지면 1번 부터 시작하여 N번까지 가는제 Cycle이 있는지 없는지 판별하는 문제이다. 위에 예시는 N = 3일 경우이다. 처음에는 BFS로 쉽게 구현하였다. boolean[]visit = new boolean[n+1]; Queueq = new LinkedList(); q.add(1); visit[1] = true; boolean check = false; while(!q.isEmpty()){ int curNode = q.peek(); q.rem.. 공감수 0 댓글수 1 2024. 2. 1.
백준 28066 (타노스는 요세푸스가 밉다) <Deque, Queue 최적화> 문제 28066번: 타노스는 요세푸스가 밉다 $N$마리의 청설모가 $1$번부터 $N$번까지 순서대로 시계 방향으로 원을 이루면서 앉아있다. 타노스는 손을 튕겨서 순서대로 두 번째 청설모를 제거해 왔는데, 옆 나라의 수학자 요세푸스도 이미 www.acmicpc.net 원형태로 앉아 있는 N 마리의 청설모가 있다. N 마리의 청설모는 각각 1 부터 N까지 번호가 매겨져 있다. 여기서 맨 첫번째 청설모를 제외한 2 ~ K 번째 청설모를 모두 제거한다. 제거한 후 청설모의 수가 2 이상이면 첫번째 청설모의 오른쪽에 있는 청설모가 첫번째 청설모가 된다. 청설모의 수가 K보다 작으면 첫번째 청설모를 제외한 나머지 청설모를 모두 제거한다. 단순한 원형큐 문제였지만, 큐를 사용했을 경우 큐의 맨 앞에 숫자를 삽입하는것.. 공감수 0 댓글수 0 2024. 1. 30.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.