[C언어] 백준 1003번: 피보나치 함수
·
백준
문제백준 1003번: 피보나치 함수https://www.acmicpc.net/problem/1003 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. - fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. - fibonacci(2..
동적 계획법(Dynamic Programming, DP)
·
알고리즘 & 자료구조
설명다이나믹 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 간단한 하위 문제들로 나누어 해결하는 알고리즘 설계 기법이다. DP는 주로 중복된 하위 문제들이 존재할 때 효율적으로 문제를 해결하는 데 사용된다. 핵심 개념은 "작은 문제들을 먼저 풀고, 그 결과를 이용해 더 큰 문제들을 해결"하는 것이다.접근 방근1. 상향식 접근 (Bottom-Up Approach): 작은 하위 문제들로부터 해결해 나가며 점점 큰 문제를 해결하는 방법이다. 일반적으로 반복문을 사용해 테이블을 채워가며 문제를 해결한다. ex) 피보나치 수열을 계산할 때, 피보나치 수 F(n)을 계산하기 위해 F(0) 부터 F(n - 1)까지 차례로 계산하고, 이를 통해 F(n)을 계산한다. 2. 메모이제이션(Memoi..
[C언어] 백준 1002번: 터렛
·
백준
문제백준 1002번: 터렛https://www.acmicpc.net/problem/1002 문제조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다.이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.  조규현의 좌표  (x1, y1)와 백승환의 좌표  (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리  r1과 백승환이 계산한 류재명과의 거리  r1가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수  T가 주어진다. 각 테스트 케이스는 다..
[C언어] 백준 2578번: 빙고
·
백준
문제백준 2578번: 빙고https://www.acmicpc.net/problem/2578 문제빙고 게임은 다음과 같은 방식으로 이루어진다.  25개의 칸으로 이루어진 빙고판에 1부터 25까지 자연수를 한 칸에 하나씩 쓴다.숫자를 하나씩 불러 3 빙고가 먼저 되는 사람이 이 게임의 승자가 된다. 철수는 친구들과 빙고 게임을 하고 있다. 철수가 빙고판에 쓴 수들과 사회자가 부르는 수의 순서가 주어질 때, 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지를 출력하는 프로그램을 작성하시오. 입력첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 한 줄에 다섯 개씩..
[C언어] 백준 1051번: 숫자 정사각형
·
백준
문제백준 1051번: 숫자 정사각형https://www.acmicpc.net/problem/1051 문제N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다. 입력첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다. 출력첫째 줄에 정답 정사각형의 크기를 출력한다.코드#include // 백준 1051번: 숫자 정사각형int main(){ int n,m; scanf("%d %d", &n, &m); int arr[n][m]; char temp[m + 1]; ..
[C언어] 백준 1735번: 분수 합
·
백준
문제백준 1735번: 분수 합https://www.acmicpc.net/problem/1735 문제분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.  두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다. 입력첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. 출력첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다.코드#include // 백준 1735: 분수 합// 유클리드 호제법int g..
[C언어] 백준 2161번: 카드1
·
백준
문제백준 2161번: 카드 1https://www.acmicpc.net/problem/2161 문제N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면,..
[C언어] 2822번: 점수 계산
·
백준
문제백준 2822번: 점수 계산https://www.acmicpc.net/problem/2822 문제상근이는 퀴즈쇼의 PD이다. 이 퀴즈쇼의 참가자는 총 8개 문제를 푼다. 참가자는 각 문제를 풀고, 그 문제를 풀었을 때 얻는 점수는 문제를 풀기 시작한 시간부터 경과한 시간과 난이도로 결정한다. 문제를 풀지 못한 경우에는 0점을 받는다. 참가자의 총 점수는 가장 높은 점수 5개의 합이다.  입력8개 줄에 걸쳐서 각 문제에 대한 참가자의 점수가 주어진다. 점수는 0보다 크거나 같고, 150보다 작거나 같다. 모든 문제에 대한 점수는 서로 다르다. 입력으로 주어지는 순서대로 1번 문제, 2번 문제, ... 8번 문제이다. 출력첫째 줄에 참가자의 총점을 출력한다. 둘째 줄에는 어떤 문제가 최종 점수에 포함되는..
[C언어] 백준 2839번: 설탕 배달
·
백준
문제https://www.acmicpc.net/problem/2839코드#include // 백준 2839번: 설탕 배달int main(){ int n; // 설탕 킬로그램 scanf("%d", &n); int count = 0; // 설탕 봉지 수 while(n != 0){ if((n >= 5) && ((n - 5 >= 3) || (n - 5 == 0)) && (n - 5 != 4) && (n - 5 != 7)){ n = n - 5; count++; } else if(n >= 3){ n = n - 3; count++; } else{ ..
[C언어] 백준 2485번: 가로수
·
백준
문제https://acmicpc.net/problem/2485코드#include // 유클리드 호제법int gcd(int a, int b){ return b ? gcd(b, a%b) : a;}int main(){ int n; scanf("%d", &n); int arr[n]; for(int i = 0; i 문제풀이방법배열에 이미 심어진 가로수의 위치를 저장한다.1. 에서 저장한 인접한 가로수들의 위치 차이 중 최솟값을 찾아낸다.찾아낸 최솟값이 인접한 가로수들의 위치 차이의 공약수인지 확인한 후 만약 아니라면 최솟값과 가로수의 차이의 최대 공약수를 최솟값으로 업데이트한다. (최대 공약수 구하는 방법은 '유클리드 호제법' 참조)반복문을 돌면서 인접한 가로수들의 위치 차이가 최솟값이 아닐..
[C언어] 백준 10815번: 숫자 카드
·
백준
문제https://www.acmicpc.net/problem/10815코드#include #include // 백준 10815번: 숫자 카드int compare(const void *a, const void *b){ return (*(int*)a - *(int*)b);}int BinarySearch(int arr[], int size, int target){ int left = 0; int right = size - 1; while(left 문제풀이방법n개와 m개의 카드를 각각 배열에 저장한다. (이하 arr1, arr2라고 칭함)C언어 내장함수인 qsort를 활용하여 arr1을 오름차순으로 정렬한다.arr2에 있는 숫자 카드 하나씩 이분 탐색을 이용하여 arr1에 있나 확인한다.만..
이분 탐색 (Binary Search)
·
알고리즘 & 자료구조
이분 탐색(Binary Search)이분 탐색은 정렬된 배열에서 값을 찾는 효율적인 알고리즘이다. 어릴 적 친구와 1부터 100까지의 수 중 숫자 맞추기를 할 때 똑똑한 친구들은 50보다 커?(ㅇㅇ) 75보다 커?(ㄴㄴ) 이런 식으로 반 씩 줄여서 질문을 했을 것이다. 이것이 이분 탐색이다. 이 알고리즘은 배열을 차례대로 탐색하는 것이 아니라, 중간 값을 기준으로 탐색 범위를 계속해서 반으로 줄여나간다. 이로 인해 시간복잡도가 O(log n)으로 효율적이다. 아래 표에서 2를 찾아보겠다.123456789 먼저 중간 값인 5를 탐색한다. 2는 5보다 작기에 5보다 큰 값들은 신경 쓰지 않는다.12345     남은 값들 중 중간 값인 3을 탐색한다. 2는 3보다 작기에 3보다 큰 값들은 신경 쓰지 않는다...
d0ng2
'분류 전체보기' 카테고리의 글 목록
상단으로

티스토리툴바