[C_C++]코딩테스트 연습

[백준] 에라토스테네스의 체 기초 문제풀이 - 1978, 1929, 6588, 4673

1978 소수 찾기 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 풀이 1000까지의 모든 숫자에 대해 소수인지를 미리 판별해놓고 입력이 들어왔을 때 소수면 카운트해준다. #include #define MAX 1001 int a[MAX]; int main() { //1은 소수가 아니므로 따로 판별 a[1]++; int n, tmp, result=0; scanf("%d", &n); for(int i=2; i

[그리디 문제풀기] Google Code Jam 2018 - Qualification Round (문제 B) (C/C++)

문제 B: 트리플 버블 정렬(Trouble Sort) Code Jam - Google’s Coding Competitions Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD. codingcompetitions.withgoogle.com 간략한 문제 해석 원래 버블 정렬 알고리즘은 앞뒤의 두 원소를 비교해 크기가 더 작은 것이 앞으로 오도록 순서를 정렬하는 것이다. 이 문제에서는 인접한 두 원소가 아니라, 가운데에 어떤 원소를 기준으로 양옆의 원소를 비교해 크기가 작은 것이 앞..

[C++] 프로그래머스 - 체육복 (그리디)

그리디의 대표 문제 중 하나인 체육복이다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 전체 학생 n(2~30)명 중 체육복을 도난당한 학생들(lost)이 있다. 체육복이 없는 학생의 앞뒤 번호 중 여벌을 가져온 학생(reserve)이 있으면 체육복을 빌린다. 도난은 1개씩만 당하며, 여벌을 가져온 학생도 도난 당해서 여벌이 없어졌을 수 있다. 이렇게 빌려서 수업을 들을 수 있는 학생 수의 최대값을 반환하면 된다. 내 풀이 학생수만큼 각 번호에 1을 담은 배열을 두고, 도난을 당했으면 1을 빼고 여벌을 가져왔으면 1을 더해준다. lost를 정..

[그리디 문제풀기] Google Code Jam 2018 - Qualification Round (문제 A) (C/C++)

Code Jam - Google’s Coding Competitions Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD. codingcompetitions.withgoogle.com 문제 A: 다시 우주를 구하기 (Saving The Universe Again) ↓ 문제 캡처 간략한 문제 해설 공격(Shoot)과 기 모으기(Charge)가 있다고 했을 때, Charge 시 데미지가 2배가 되어 공격력이 높아지고, Shoot 시 높아진 공격력으로 맞게 된다. 초기 데미지는 1이..

[백준] 그리디 기초 문제풀이 ③ - 2437, 1783, 1969, 2812 (C/C++)

2437 저울 문제 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 입력 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 ..

[백준] 그리디 기초 문제풀이 ② - 1138, 1541, 10610, 1946 (C/C++)

1138 한 줄로 서기 문제 N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다. 어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다. 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다. 각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다..

[백준] 그리디 기초 문제풀이 ① - 5585, 11047, 11399, 2217 (C언어)

5585 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다. 출력 제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오. 풀이 입력으로 들어온 수를 1000에서 빼고, 큰 화폐단위부터 차례대로 거슬러준다. #include int main() { int n, result = 0; scanf("%d"..

[백준] 11726, 11727, 14852 2xn 타일링, 2133 3xn 타일링 (C, DP)

DP 개념 [알고리즘 공부] 다이나믹 프로그래밍(DP, 동적 계획법) 다이나믹 프로그래밍(Dynamic Programming) 하나의 문제를 단 한번만 풀도록 하는 알고리즘 컴퓨터적인 사고력을 물어보기 적합해서 자주 출제되므로 확실하게 알아야 함. DP, 동적 계획법이라고도 함 coding-maggot.tistory.com 11726 2xn 타일링 1 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 i) n이 1일 때(..