CodeDrive

문제:

Day of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의  가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력:

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

풀이방법:

여러 개의 기타줄에서 패키지 가격이 가장 작은 값과, 낱개 가격이 가장 작은 값만 필요하다. 이 두 개의 가격을 비교했을 때, 만약 낱개로 6개를 사는 것이 패키지 가격보다 싸다면 모든 기타줄을 낱개로 사는 것이 이득이다.

만약 그렇지 않다면 사야하는 기타줄을 6으로 나눴을 때 그 몫만큼은 패키지로 사는 것이 이득이다. 그 뒤로는 남은 나머지를 낱개로 샀을 때와 패키지로 샀을 때(적어도 N개를 구매하면 되므로 초과해서 사도 괜찮다.) 어떤 것이 이득인지 알아보고 그에 맞게 구매를 해야 한다. (ex 패키지 7 낱개 2면 패키지가 더 이득)  

문제링크:

https://www.acmicpc.net/problem/1049

문제:

풀이방법:

나갈 때 정보, 들어올 때의 정보가 둘 다 있는 테이블이 필요하므로 둘을 INNER JOIN을 하도록 한다. 그 뒤에 WHERE 절로 IN일 때는 Intact라는 단어를 포함하도록 하고, OUTS일 때는 Intact라는 단어가 없는 경우에 대해서만 출력하도록 했다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59045

문제:

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 상근이의 동기의 수 n(2<=n<=500)이 주어진다. 둘째 줄에는 리스트의 길이 m(1<=m<=10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai,bi가 주어진다. (1<=ai<bi<=n) ai와 bi가 친구라는 뜻이며, bi 와 ai도 친구관계이다.

출력:

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

풀이방법:

우선 입력으로 받은 값들을 그래프 형식으로 정리를 하는 작업을 거친다. 이후 BFS 방식을 사용해서 level이 2까지 가는 친구들(친구의 친구)을 찾는다. 항상 시작은 1이므로 queue에 1을 넣고 BFS 탐색을 두번 한다. 그렇게 탐색을 마치고 1을 제거한 뒤에 배열의 길이를 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/5567

문제:

풀이방법:

이전 입양 시각 구하기에는 테이블에 있는 시간만 해도 상관이 없었으나 이번에는 전체 시간대를 표현해야 한다. 따라서 테이블에 없는 시간들을 만들어 줘야 한다. 그래서 시간 정보를 가지고 있는 새로운 테이블을 만들어서 이와 조인해서 표현하도록 한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59413

문제:

상근이는 농구의 세계에서 점차 영향력을 넓혀가고 있다. 처음에 그는 농구 경기를 좋아하는 사람이었다. 농구에 대한 열정은 그를 막을 수 없었고, 결국 상근이는 농구장을 청소하는 일을 시작했다. 상근이도 농구장을 청소하면서 감독이 되기 위해 가져야할 능력을 공부해나갔다. 서당개 3년이면 풍월을 읊듯이 상근이는 점점 감독으로 한 걸음 다가가고 있었다. 어느 날 그에게 지방의 한 프로농구팀을 감독할 기회가 생기게 되었다. 그는 엄청난 지도력을 보여주며 프로 리그에서 우승을 했고, 이제 국가대표팀의 감독이 되었다.

내일은 일본과 국가대표 친선 경기가 있는 날이다. 상근이는 내일 경기에 나설 선발 명단을 작성해야 한다.

국가대표팀의 감독이 된 이후에 상근이는 매우 게을러졌다. 그는 선수의 이름을 기억하지 못하고, 각 선수의 능력도 알지 못한다. 따라서, 누가 선발인지 기억하기 쉽게 하기 위해 성의 첫 글자가 같은 선수 5명을 선발하려고 한다. 만약, 성의 첫 글자가 같은 선수가 5명보다 적다면, 상근이는 내일 있을 친성 경기를 기권하려고 한다.

상근이는 내일 경기를 위해 뽑을 수 있는 성의 첫 글자를 모두 구해보려고 한다.

입력:

첫째 줄에 선수의 수 N(1<=N<=150)이 주어진다. 다음 N개 줄에는 각 선수의 성이 주어진다. (성은 알파벳 소문자로만 이루어져 있고, 최대 30글자이다)

출력:

상근이가 선수 다섯 명을 선발할 수 없는 경우에는 "PREDAJA" (따옴표 없이)를 출력한다. PREDAJA는 크로아티아어로 항복을 의미한다. 선발할 수 있는 경우에는 가능한 성의 첫 글자를 사전순으로 공백없이 모두 출력한다.

풀이방법:

딕셔너리 자료형을 사용해서 해시 방법으로 풀었다. 맨 앞글자를 키로 하고 그에 따른 value는 나타낸 횟수로 지정했다. 이렇게 모든 이름을 다 한번씩 탐색해 딕셔너리로 정리를 마친다. 이를 items으로 가져와서 정렬한 뒤에 5이상인 값만 answer에 붙이도록한다. 만약 5이상인 값이 없었다면 answer는 빈 문자열일것이다.

문제링크:

https://www.acmicpc.net/problem/1159

문제:

풀이방법:

NULL이 필요한 문제가 아니므로 기본 조인인 INNER JOIN을 사용해도 상관이 없다. 따라서 두 테이블을 INNER JOIN 했다. 그 다음에 보호 기간이 가장 길었다는 것은 O.DATETIME과 I.DATETIME의 차이가 크다는 것이다. 따라서 이 연산을 ORDER BY에다가 DESC 조건을 넣어서 찾도록 한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59411

문제:

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱 ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱 ㄴㄴ수가 몇 개 있는지 출력한다.

입력:

첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000.000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 [min,max]구간에 제곱ㄴㄴ 수가 몇 개인지 출력한다.

풀이방법:

어떤 수 X가 한 제곱수로 나누어지는지 확인하는 것 보다 제곱수가 나누어 떨어지게 만들 수 있는 수들을 지워나가는 것이 시간복잡도를 줄일 수 있다.(에라토스테네스의 체와 비슷)

문제링크:

https://www.acmicpc.net/problem/1016

문제:

풀이방법:

조인을 통해서 NULL 값을 만들어야 한다면 LEFT JOIN이나 RIGHT JOIN을 써야 하는 것 같다. 따라서 '입양을 못 갔다' 라는 것은 INS에는 있지만 OUTS에는 없어야 하는 값들이다. 따라서 INS에 OUTS에 붙임으로써 입양을 못 간 동물들을 만들어 낸다. 이는 WHERE절로 O.ANIMAL_ID가 NULL인 값으로 찾을 수 있다. 그리고 3마리만 출력을 해야 하므로 LIMIT 3을 사용한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59044

문제:

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

 1. 2부터 N까지 모든 정수를 적는다.

 2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.

 3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.

 4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

입력:

첫째 줄에 N과 K가 주어진다. (1<=K<,max(2,K) < N <=1000)

출력:

첫째 줄에 K번째 지워진 수를 출력한다.

풀이방법:

우선 N까지 수가 있는 배열을 만들고 이를 에라토스테네스의 체 규칙에 따라서 하나씩 지워나간다. 이 때마다 하나씩 count를 늘려주면서 K번째가 되면 현재 지운 값을 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/2960

문제:

풀이방법:

OUTS에 있는 값의 DATETIME과 INS의 DATETIME의 값 차이를 비교해야 하는 문제이다. 두 테이블에 공통된 값인 ANIMAL_ID으로 INNER JOIN을 한다. 조인을 한 뒤에 IN의 DATETIME이 OUTS의 DATETIME보다 큰 값을 찾아주도록 한다. 

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59043