[Programmers] Level 1. 모의고사 (C++)
2019. 7. 25. 23:24
알고리즘/Programmers
정리 수포자 3명이 있고, 3명이 각각 정해진 규칙에 맞춰 답을 작성해서 제출한다. 1번부터 답이 정해져있기 때문에 규칙적으로 반복되는 정답의 갯수를 이용해 정답을 체크해준다. 정답의 갯수가 정해져 있어 그 수만큼 반복되기 때문에 나머지를 구해서 맞은 정답의 갯수를 구해준다. 정답일 때, 카운트를 세어주고 문제에서 가장 많은 정답을 맟춘 학생을 출력해야하기 때문에 카운트가 많은 수포자를 answer 에 넣어준다. 따라서, 이 문제는 이렇게 풀어보았다. 1) 수포자가 정해진 답을 계속해서 반복한다는 점. 그리고 수포자는 어떤 문제가 나와도 이 정답만 제출한다. 2) 정답이 반복되기 때문에 반복되는 정답의 갯수를 구한다. 3) 반복되는 정답의 갯수가 5개이고, 7번 문제라면 7를 5로 나눈 나머지인 2 번째..
[Programmers] Level 1. 소수의 합 (C++)
2019. 7. 25. 22:50
알고리즘/Programmers
정리 소수를 구하는 문제였다. 소수를 구하는 방법 중 가장 많이 알려져있는 알고리즘은 에라토르테네스의 체 다. 에라토스테네스의 체를 간단하게 설명해보면, 2부터 시작한다. 그리고 2부터 자신을 제외한 자신의 배수를 제거한다. 2를 제외한 2의 배수를 제거하고, 3을 제외한 3의 배수를 제거하고, 4는 2의 배수이기 때문에 이미 제거가 되어있다. 이미 제거가 되어있는 수들은 건너뛰고 진행한다. 위와 같은 과정을 반복하면 남아있는 숫자는 소수가 될 것이다. 따라서, 에라토스테네스의 체를 이용해서 풀면 쉽게 풀 수 있는 문제였다. 소스 코드 #include using namespace std; long long solution(int N) { long long answer = 0; vector m; for(i..
[백준 알고리즘] 4948번 : 베르트랑 공준
2019. 7. 21. 16:09
알고리즘/BaekJoon
문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하며, 한 줄로 이루어져 있다. (n ≤ 123456) 입력의 마지막에는 0이 주어진다. 출력 각 테스트 케이스에 대..
[백준 알고리즘] 1476번 : 날짜 계산
2019. 7. 21. 14:35
알고리즘/BaekJoon
문제 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다. 예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. ..
[백준 알고리즘] 1094번 : 막대기
2019. 7. 21. 14:15
알고리즘/BaekJoon
문제 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다. 막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다. 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다. 이제, ..
[백준 알고리즘] 1085번 : 직사각형에서 탈출
2019. 7. 21. 14:09
알고리즘/BaekJoon
문제 한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 x y w h가 주어진다. w와 h는 1,000보다 작거나 같은 자연수이고, x는 1보다 크거나 같고, w-1보다 작거나 같은 자연수이고, y는 1보다 크거나 같고, h-1보다 작거나 같은 자연수이다. 출력 첫째 줄에 문제의 정답을 출력한다. 예제 입력 1 6 2 10 3 예제 출력 1 1 내가 작성한 코드 (C++ 성공) #include #include using namespace std; int so[250000]; int main() { int x, y, w, h; cin >> x..
[백준 알고리즘] 1076번 : 저항
2019. 7. 21. 14:07
알고리즘/BaekJoon
문제 전자 제품에는 저항이 들어간다. 저항은 색 3개를 이용해서 그 저항이 몇 옴인지 나타낸다. 처음 색 2개는 저항의 값이고, 마지막 색은 곱해야 하는 값이다. 저항의 값은 다음 표를 이용해서 구한다. 색 값 곱 black 0 1 brown 1 10 red 2 100 orange 3 1000 yellow 4 10000 green 5 100000 blue 6 1000000 violet 7 10000000 grey 8 100000000 white 9 1000000000 예를 들어, 저항에 색이 yellow, violet, red였다면 저항의 값은 4,700이 된다. 입력 첫째 줄에 첫 번째 색, 둘째 줄에 두 번째 색, 셋째 줄에 세 번째 색이 주어진다. 색은 모두 위의 표에 쓰여 있는 색만 주어진다. 출..
[백준 알고리즘] 1057번 : 토너먼트
2019. 7. 21. 14:03
알고리즘/BaekJoon
문제 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를..