알고리즘 풀이
-
백준(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와 동일..
-
회전초밥 SUSHI알고리즘 풀이/알고리즘 해결전략 연습 2019. 8. 16. 17:34
문제: https://algospot.com/judge/problem/read/SUSHI 문제문제 풀이 내기에서 모인 벌금이 많이 쌓여서 알고스팟 운영진들은 회식을 하러 회전초밥집에 갔습니다. 회전초밥집에 들어선 운영진들은 초밥은 먹지 않고 전략 회의를 시작했습니다. 회전초밥집에는 n종류의 메뉴가 있는데, 운영진들은 각 메뉴에 대해 선호도를 매겼습니다.초밥계란연어장어대뱃살스테이크후라이드 치킨가격25003000400050001000015000선호도791012201운영진들은 주어진 예산 안에서 선호도의 합을 최대한으로 하도록 초밥을 먹고 싶습니다. 각 종류의 초밥은 무한정으로 공급된다고 가정합시다. 이 때 얻을 수 있는 최대한의 선호도는 얼마일까요? 코드 ( C ++ ) 종만북 참조 #include #inc..
-
백준(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){..
-
소방차 FIRETRUCKS알고리즘 풀이/알고리즘 해결전략 연습 2019. 8. 15. 01:09
문제 : https://algospot.com/judge/problem/read/FIRETRUCKS 문제한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 위해 가능한 한 빠르게 소방차를 파견해야 합니다. 서울 시내에는 m개의 소방서가 있습니다. 화재 장소에서 가장 가까운 소방서에서 소방차를 보낸다고 할 때, 각 화재 장소에 소방차가 도달하기까지 걸리는 시간의 합을 계산하는 프로그램을 작성하세요. 각 소방서에는 소방차가 충분히 많습니다.이 문제에서 서울 시내는 1부터 V까지 번호 붙여진 V개의 장소들과 이들을 연결하는 E개의 양방향 도로로 구성됩니다. 모든 도로에 대해 도로가 연결하는 두 장소의..
-
백준(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의 수 +..