[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

[백준] 그리디 기초 문제풀이 ③ - 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일 때(..

[백준] 10699 오늘 날짜(C언어)

https://www.acmicpc.net/problem/10699 10699번: 오늘 날짜 서울의 오늘 날짜를 출력하는 프로그램을 작성하시오. www.acmicpc.net 서울의 오늘 날짜 출력 - YYYY-MM-DD 형식으로 출력해야 함 풀이1) 그냥 오늘 날짜 때려박기 #include int main() { printf("2022-07-24"); return 0; } 풀이2) time.h 헤더 내장 함수 사용해 범용 코드 짜기 C 에서는 , C++ 에서는 사용 time() 함수로 현재 날짜, 시간 얻어와 저장 time_t t = time(NULL); time() 함수를 호출하면 time_t 타입을 반환. 결과값은 1970년 1월1일 0시0분0초 기점으로 현재까지 흐른 시간을 초단위로 나타낸 것 lo..

[백준] 삼성 SW 역량 테스트 기출 - 2048 (Easy) (C언어)

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 해석 최대 20 * 20 의 2차원 공간에 상하좌우로 보드를 이동할 수 있고, 규칙에 따라 숫자가 이동 or 합산된다. 최초 입력되는 보드에서 최대 5번만 이동해 보드에서 가장 큰 블록의 값을 출력하는 문제이다. 1회 움직임에서 선택할 수 있는 경우는 상하좌우 4가지다. 최대 5번의 움직임만 생각하면 되므로 다해보면 되는 DFS 문제. 4 ^ 5 = 1024(움직..

[백준] 삼성 SW 역량 테스트 기출 - 구슬탈출2 (C언어)

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 해석 최대 10*10 크기인 보드가 있고, 빨간 구슬, 파란 구슬, 구슬이 통과할 수 있는 구멍이 각각 1개씩 있다. 보드를 기울임에 따라 구슬이 직선으로 움직이게 되고, 목적은 빨간 구슬을 10번 이내에 구멍을 통해 빼내는 것이다. 이 때 파란 구슬은 구멍으로 나오면 안된다. 출력은 목적을 달성하는 최소 기울임 횟수를 출력하고, 10번이 넘..