백준
-
백준(BOJ) 2644번 촌수계산알고리즘 풀이/백준(Boj) 2019. 8. 18. 02:42
문제 : https://www.acmicpc.net/problem/2644 문제우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 나의 풀이: 구하고자 하는 촌수 두사람을 child 와 parent 라고 두자. child의 인접한 사람을 처음 발견한 상태 ..
-
백준(BOJ) 1707번 이분 그래프알고리즘 풀이/백준(Boj) 2019. 8. 17. 16:29
문제 : https://www.acmicpc.net/problem/1707 문제그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 나의 풀이: 이분 그래프가 되려면 DFS를 했을 시 현재 노드가 0 이라면 인접한 노드들은 1이여야 한다. 따라서 biGraph 배열을 추가로 하나 만들어서 한 노드의 인접한 노드들은 1 - (현재노드의 Bi값) 로 정의해줌으로써 현재 노드의 biGraph 값이 0 이라면 인접한 노드들은1을 1이라면 0을 반환하도록 해 주자 기존 DFS와 동일..
-
백준(BOJ) 1049번 기타줄알고리즘 풀이/백준(Boj) 2019. 8. 16. 16:03
문제 : https://www.acmicpc.net/problem/1049 문제Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오. 나의 풀이: 우선 각각 6묶음 배열과 낱개 묶음 배열을 만들어서 오름차순으로 정렬한다. 그 후 그림과 같이 알고리즘을 세운다. 코드 ( C++ ..
-
백준(BOJ) 1543번 문서 검색알고리즘 풀이/백준(Boj) 2019. 8. 15. 17:58
문제 : https://www.acmicpc.net/problem/1543 문제세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오. 나의풀이: 주의할점은 첫째로 cin 으로 입력시 enter까지 포함되 공백문자가 포함되기 때문에 getline 으로 문자를 받아야 ..
-
백준(BOJ) 11650번 좌표 정렬하기알고리즘 풀이/백준(Boj) 2019. 8. 15. 03:25
문제 : https://www.acmicpc.net/problem/11650 문제2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 나의 풀이 : pair를 통해 x와 y를 함께 저장하는 배열 S를 만들자 입력을 다 받은 후 sort를 통해 오름차순정렬한다면 기본적으로 처음 x와 대소 비교 후 같다면 y와 대 소비교를 해 주어서 반환해주기 때문에 sort정렬후 출력해주기만 하면 된다. 코드 ( C++ ) #include #include using namespace std; int N; pair S[100001]; int main(){cin >> N;for (int i = 0; i < N; ++i){..
-
백준(BOJ) 2231번 분해합알고리즘 풀이/백준(Boj) 2019. 8. 14. 14:26
문제 : https://www.acmicpc.net/problem/2231 문제어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 나의 풀이: N의 가장 작은 생성자를 구해야 하고 N이 100만 까지이니 1부터 시작하는 완전 탐색으로 충분히 시간 내에 가능하다. i를 1부터 시작해서 i의 수 +..
-
백준(BOJ) 2294번 동전 2알고리즘 풀이/백준(Boj) 2019. 8. 13. 16:27
문제 : https://www.acmicpc.net/problem/2294 문제n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 나의 풀이:반복적 동적 계획법을 통해 해결해보자 . cache[i] 는 i 원을 만들 수 있는 최소 동전의 수로 놓고 동적 계획법을 짜보자 예제 ) 코드 ( C++ ) #include #include using namespace std;int n, k;int coin[101];int cache[10001];const int INF = 987654321;int solve()..
-
백준(BOJ) 1620번 나는야 포켓몬 마스터 이다솜알고리즘 풀이/백준(Boj) 2019. 8. 12. 15:13
문제 : https://www.acmicpc.net/problem/1620 문제 오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네. 나의 풀이: N과 M이 10만 이기때문에 완전탐색으로는 10만 * 10만이 되어서 시간 내에 불가능하다. 이분탐색으로 접근하여야 가능하다. 그런데 숫자가 주어젔을 경우 에는 이분탐색으로 접근하지 않고 바로 인덱스로 접근해도 해결이 가능하다. 따라서 숫자시 인덱스로 바로 접근 , 알파벳일시 이분 탐색으로 접근해주자. ..