본문 바로가기

BOJ

 (30)
[코드트리] Greedy - 그리디 알고리즘 / 동전 연습문제 1, 4, 5 동전을 이용하여 8원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요. 위 문제를 보면 당연히 큰 동전부터 쓰는 것이 좋아 보입니다. 하지만 큰 동전부터 사용하게 되면 5 + 1 + 1 + 1이므로 4개의 동전이 필요하지만, 4 + 4 역시 8 이므로 최소 동전의 수는 2가 됩니다. 그런데 다음 경우는 어떨까요? 1, 5, 10, 20 동전을 이용하여 78원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요. 이 경우에는 큰 동전부터 거슬러주는 것이 항상 좋습니다. 그 이유는 주어진 동전들이 전부 배수관계에 놓여있기 때문입니다. 그렇기에 큰 동전이 사용이 가능하다면, 작은 동전을 사용하는 것보다 항상 좋은 선택이 되는 것입니다. 따라서 배수 ..
[C++/백준] 11052 : 카드 구매하기 문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. (카드 종류는 생략) 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다. 민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다. 예를 들..
[C++/백준] 9095 : 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 백준 실버 3 티어. DP 문제였고 DP는 점화식을 찾는게 항상 어렵다; 1은 1로만 표현 가능. (1) 2는 1+1, 2로 표현 가능. (2) 3은 1+ (2의 경우의 수)..
[PGS] Lv.0 (코딩테스트 입문) 12일차 문제 프로그래머스 레벨 0 문자열, 정렬, 사칙연산, 수학 ✍🏻 문자열 대체 → my_string.replace(j,1,""); : 인덱스 j의 원소부터 길이 1만큼을 “”로 대체 ✍🏻 문자 내용이 숫자인지? → isdigit(c) : 숫자면 양수, 아니면 0을 리턴함 ✍🏻 vector to set → set s(v.begin(), v.end()); ✍🏻 set to vector → vector v(s.begin(), s.end()); 모음 제거 string solution(string my_string) { string m = "aeiou"; for(int i=0; i
[PGS] Lv.0 (코딩테스트 입문) 11일차 문제 프로그래머스 레벨 0 수학, 반복문 주사위의 개수 int solution(vector box, int n) { int a = box[0]/n; int b = box[1]/n; int c = box[2]/n; int answer = a*b*c; return answer; } 합성수 찾기 int solution(int n) { int answer = 0; for(int i=4; i
[PGS] Lv.0 (코딩테스트 입문) 10일차 문제 ✍🏻 벡터 numbers 와 tmp 연결하기 (합치기) → numbers.insert( numbers.end(), tmp.begin(), tmp.end() ) ✍🏻 벡터의 첫 원소 삭제하기 → v.erase( v.begin() ) 프로그래머스 레벨 0 조건문, 배열, 수학, 시뮬레이션 점의 위치 구하기 int solution(vector dot) { if(dot[0]>0 && dot[1]>0) return 1; if(dot[0]0) return 2; if(dot[0]
[C++/백준] 1026 : 보물 문제 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0] × B[0] + ... + A[N-1] × B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다. S의 최솟값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다. 출력 첫째 줄에 S의 최솟값을 출력한다. 실버..
[C++/백준] 25178 : 두라무리 휴지 문제 기령이는 어느 날 캠릿브지 대학의 연결구과에 대해 알게 되었다. 캠릿브지 대학의 연결구과란, 단어를 이해함에 있어 한 단어 안에서 글자들이 어떤 순서로 배열되어 있는지는 중요하지 않고, 양 끝의 글자가 올바른지만 중요하다는 이론이다. 즉 단어의 글자가 섞이더라도 양 끝의 글자만 그대로라면 원래의 단어를 쉽게 유추하여 이해할 수 있다는 것이다. 그러나 기령이는 "durumari"와 같은 단어를 "daumurri"로 바꾸게 된다면 원래의 단어를 유추하기 매우 어려워진다는 사실을 발견했다. 몇 날 며칠의 고민을 거듭한 끝에 위의 이론이 잘 작동할 수 있는 조건을 새롭게 찾아냈다. 한 단어를 재배열해 다른 단어를 만들 수 있어야 한다. 두 단어의 첫 글자와 마지막 글자는 서로 동일해야 한다. 각 단어에서 ..
728x90

티스토리툴바