https://programmers.co.kr/learn/courses/30/lessons/92341 코딩테스트 연습 - 주차 요금 계산 [180, 5000, 10, 600] ["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"] [14600, 34400, 5000] programmers.co.kr 문제 설명 주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다. 요금표 기본 시간(분) ..
코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같다. 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다. 신고 횟수에는 제한이 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다. 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다. k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든..
1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 힌트 더보기 입력 범위를 보면 M이 1, N이 1,000,000일 때 최악의 경우가 됨을 알 수 있다. 만약 숫자 A를 소수인지 아닌지 판별할 때 1부터 A까지 반복하면서 나누어 떨어지는지 확인한다면 숫자가..
에라토스테네스의 체란? 에라토스테네스의 체란 소수를 판별할 때 사용하는 알고리즘으로 고대 그리스 수학자 에라토스테네스가 발견했다. 여기서 말하는 소수란, 1과 자기 자신만을 약수로 가지는 수를 말한다. 에라토스테네스의 체 원리 1) 아래 그림과 같이 1에서 100까지의 수가 있다. 2) 1은 소수가 아니기 때문에 제외하고 2부터 생각해보자. 2는 소수에 해당하기 때문에 소수임을 체크해주고 2의 배수들은 소수가 아니기 때문에 제외시킨다. 3) 그다음 수인 3을 보면 제외되지 않았기 때문에 소수이다. 그리고 3의 배수를 모두 제외시킨다. 4) 그다음 수인 4는 제외됐으므로 5를 확인한다. 5는 제외되지 않았기 때문에 소수이다. 5의 배수까지 모두 제외시키면 아래와 같다. 5) 이렇게 계속해서 반복하다 보면 ..
2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 힌트 더보기 아직 유클리드 호제법을 잘 모른다면 아래 링크를 통해 유클리드 호제법을 먼저 보고 오자. [알고리즘 기초] 유클리드 호제법, GCD(최대공약수) 구하기 유클리드 호제법이란 무엇인가? 유클리드..
유클리드 호제법이란 무엇인가? 유클리드 호제법(Euclidean Algorithm)은 두 자연수의 GCD(최대공약수 - Greatest Common Devisor)를 구하는 알고리즘이다. 서로 호(互) 덜 제(除) 법 법(法) 유클리드 호제법의 원리 두 개의 자연수 A, B가 있다. (A > B) 그리고 A를 B로 나눈 나머지 R이 있다. R이 0이라면, A와 B의 최대공약수는 B이다. R이 0이 아니라면, A와 B의 최대공약수는 B와 R의 최대공약수와 같기 때문에 A에는 B, B에는 R을 대입한 후 1번으로 돌아간다. 재귀로 구현하기 C / C++ int get_gcd(int A, int B) { int R = A % B; if(R == 0) return B; else return get_gcd(B, ..
2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후..
완전 탐색, 브루트 포스란 무엇인가? 브루트 포스를 사전적 의미로 찾아본다면 아래와 같다. 브루트(Brute) : 무식한 + 포스(Force) : 힘 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. 브루트 포스의 장점 알고리즘을 설계하고 구현하기 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 브루트 포스의 단점 알고리즘의 실행 시간이 매우 오래 걸린다. 메모리 효율면에서 매우 비효율적이다. 브루트 포스의 종류 브루트 포스는 크게 선형구조와 비선형 구조로 나눌 수 있다. 선형 구조 ..
재귀함수란 무엇인가? 자기 자신을 호출하는 함수를 재귀함수(Recursive Function)라고 하며 이때 하는 호출을 재귀호출(Recursive Call)이라고 한다. 팩토리얼, 하노이 탑과 같은 문제에서 많이 사용된다. 재귀 함수의 장점 직관적이며 간단하게 구현할 수 있다. 깊이 우선 탐색, 백트래킹, 분할 정복 등 많은 알고리즘에서 사용되기도 해서 기초가 되는 개념이다. 재귀 함수의 단점 재귀함수의 종료 조건을 잘 설정해주지 않으면 재귀함수를 빠져나오지 못하게 되면서 무한루프에 빠질 수 있다. 재귀 호출의 깊이가 너무 깊어지면 너무 많은 메모리를 사용한다. 불필요한 반복 연산을 하게 될 가능성이 있다. 팩토리얼 문제 재귀함수로 해결하기 팩토리얼을 구하는 함수가 있다고 생각해보자. 5팩토리얼을 재귀..
코딩테스트 연습 - 스타 수열 programmers.co.kr 문제 설명 다음과 같은 것들을 정의합니다. 어떤 수열 x의 부분 수열(Subsequence)이란, x의 몇몇 원소들을 제거하거나 그러지 않고 남은 원소들이 원래 순서를 유지하여 얻을 수 있는 새로운 수열을 말합니다. 예를 들어, [1,3]은 [1,2,3,4,5]의 부분수열입니다. 원래 수열에서 2, 4, 5를 제거해서 얻을 수 있기 때문입니다. 다음과 같은 조건을 모두 만족하는 수열 x를 스타 수열이라고 정의합니다. x의 길이가 2 이상의 짝수입니다. (빈 수열은 허용되지 않습니다.) x의 길이를 2n이라 할 때, 다음과 같은 n개의 집합 {x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]}의 교집합의 ..