본문 바로가기

백준

 (81)
1003)피보나치 함수 https://www.acmicpc.net/problem/1003 단순히 피보나치 수를 구하라는 문제는 아니다. 피보나치 수열은 점화식으로 정의ㅎㄹ 수 있는데 대개 점화식으로 표현된 수열의 일반항은 경계 조건과 함께 재귀 함수로 표현할 수 있다. 문제는 n 번째 피보나치 수를 구하기 위해 1과 0을 몇 번이나 반환했는가 그 수를 세는 것이다. n>=0일때 n번째 피보나치 수를 구하는 재귀 함수는 아래처럼 짤 수 있다. 1234int fibo(int n){ if(n
3023)마술사 이민혁 https://www.acmicpc.net/problem/3023 패턴을 입력받는다. 패턴을 좌상단에 위치시킨 뒤 이리저리 대칭시켜 전체 패턴의 모습을 결정한다.위 그림은 좌상단 패턴을 y축 대칭시켜 우상단 패턴의 모습을 결정했다.좌상단 패턴을 x축에 대칭시켜 좌하단 패턴의 모습을 결정했다. 어떻게 해야 x,y축 대칭시킨 패턴을 얻을 수 있을까? 아래와 같은 반복 구조를 사용하면서 부분 패턴을 대입해 전체 패턴을 채워야 한다. j가 차례대로 증가할 때 부분 패턴의 인덱스(그림에서 '?')는 거울에 비친것처럼 대칭적으로 멀어져야 한다. 부분 패턴의 인덱스를 k라고 할 때 거울에 비친것처럼 j와 대칭적으로 움직이는 관계가 있다. 이 관계를 찾기 위해 j와 k를 표로 나타내자.k와 j의 인덱스 관계를 찾기 위..
2033)반올림 https://www.acmicpc.net/problem/2033 문제를 그대로 따라가면 된다. 예를들어 324가 입력이 되면 324는 10보다 크기 때문에 1의 자리(10으로 나눈 나머지)에서 반올림한다. 320은 100보다 크기 때문에 10의 자리(100으로 나눈 나머지)에서 반올림한다. 300은 1000보다 작기 때문에 위 과정을 끝마친다. 1의 자리 또는 10의 자리라고 말을 꼬아놨지만 사실은 비교할 때 쓰이는 값 10,100,...을 그대로 사용하면 된다. 12345678910111213141516171819202122#include int round(int Q, int R) { if (R>=Q/2) return Q; else return 0;} int main() { int n; int Q =..
1912)연속합 https://www.acmicpc.net/problem/1912 정답률이 보여주듯이 완전 어려운 문제였다. 주어진 예제나 여러 가지 반례는 통과시킬 수 있게 코드를 짰지만 결국 틀렸다. 질문 게시판에 들어가서 힌트를 얻고서야 풀 수 있었는데 완전 심플하고 신박한 방법이라 복습겸 써본다. 1.sum을 0으로 초기화한다. 2.값 하나를 읽어 sum에 더한다. 3-1.값 하나를 더한 sum이 0보다 크면, sum과 maxSum 중 더 큰 것을 maxSum에 저장한다. 3-2.0보다 작으면 sum을 0으로 초기화한다. 4.수열이 끝날 때까지 2~3을 반복한 후 maxSum을 출력한다. 이렇게 하면 음수만 입력되는 경우를 제외한 모든 경우에 최대의 연속합을 구할 수 있다. 왜 그럴까? sum은 계속 값을 더해가..
2804)크로스워드 만들기 https://www.acmicpc.net/problem/2804 문제를 잘 읽어봐야 헷갈리지 않는다. 단어 A,B가 주어지는데 A와 B에서 공통 낱말은 항상 존재한다. 가장 처음으로 나타나는 공통 낱말을 기준으로 A와 B를 교차시켜야 한다.위 그림처럼 공통 낱말이 A에서는 tA에 B에서는 tB에 나타났다고 하자. 그럼 아래 그림처럼 교차시켜야 한다.A와 B를 교차해 이차원 배열 안에 담을 때 이들이 공통 낱말이 위치한 인덱스는 다음 그림처럼 쓰인다. 이중 반복문을 돌리기 위해 i를 고정시키고 j를 하나씩 증가시킬 때, j가 tA인 순간에 wordB의 한 낱말을 꺼내다가 이차원 배열에 저장하는 것이다. i가 tB가 되는 순간에 j를 증가시키며 wordA의 낱말을 이차원 배열에 저장한다. 123456789..
5032)탄산 음료 https://www.acmicpc.net/problem/5032 쉬워보이는 문제지만 쉽지 않다. 예제 입력이 9 0 3이고 예제 출력이 4이다. 총 빈 음료병의 갯수가 9개여서 새 음료수 3개와 교환했다. 그리고 그 음료수를 마셔 빈 음료병 3개가 생겨 새 음료수 하나를 더 교환한 것이다. 빈 음료병을 교환해 생긴 음료수도 빈 음료병 갯수로 고려해야 한다. 이를 위해 4개의 변수를 사용하자. e는 빈 음료병의 갯수, drink는 교환한 총 음료수의 갯수, change는 교환 받은 빈 음료수의 갯수, unchange는 교환 받지 못한 빈 음료수의 갯수다. 빈 병의 갯수가 21개 이고 3개의 빈 병으로 새 음료수와 교환할 수 있을 때, 몇 개의 새 음료수와 교환할 수 있을까? 위 그림은 새 음료수 병을 구..
1026)보물 https://www.acmicpc.net/problem/1026 이 문제를 요약해보면 S+=A[i]*B[i]를 구하는 것인데 S가 최소가 되게 해야 한다. 문제를 읽어 보면 함정이 있는데 A는 재배열해도 되고 B는 재배열하지 말라고 한다. 이 문구를 고려하지 않고 수열 A와 수열 B를 최소가 되게 각 항들을 매칭시키는 방법은 A를 오름 차순으로 정렬하고 B를 내림 차순으로 정렬해 A[i]와 B[i]를 매칭시키는 것이다. 왜냐하면 수열 A의 i번째로 큰 값과 수열 B의 i번째로 작은 값을 매칭하기 때문이다. 그래서 두 항 A[i]와 B[i]의 곱은 항상 i번째로 작을 수 밖에 없다. 12345678910111213141516171819202122232425262728293031323334353637383..
2108)통계학 https://www.acmicpc.net/problem/2108 수열이 주어질 때 4가지 대표값들을 찾는 문제다. 4가지 대표값에는 산술평균값, 중앙값, 최빈값, 범위가 있다. 각 대표값들을 구하기 쉽게 주어진 수열을 정렬한다.(퀵 정렬 사용함) 산술평균값은 값을 입력받는 과정에서 합을 구하고 n으로 나눈뒤 반올림한다. 중앙값은 수열의 갯수가 짝수일 때와 홀수일 때를 나누어 생각해야 한다. 수열 갯수가 짝수 개일 때 중앙값을 갖는 항은 없기 때문에 중앙에 인접한 두 항의 평균이 곧 중앙값이 된다. 수열 갯수가 짝수 개일 때 중앙값을 얻기 위한 두 항은 A[N/2], A[N/2-1]이다. 수열 갯수가 홀수 개일 때 중앙값을 얻기 위한 항은 A[(N-1)/2]이다. 최빈값을 구하는 것은 쉽지 않다. 최빈값..

티스토리툴바