전체 글
-
회전초밥 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++ ..
-
문제 11-1 이진 탐색 트리의 조건Data Structure/윤성우의 열혈 자료구조 2019. 8. 16. 06:29
이진 탐색 트리가 되기 위한 조건 정리 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다 2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다 3. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다 4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 2와 3의 조건을 다음과 같이 바꾼다면 부모 노드의 키가 왼쪽 자식 노드의 키보다 크다. 부모 노드의 키가 오른쪽 자식 노드의 키보다 작다. 이는 모든 이진 탐색 트리가 만족하는 조건이긴 하지만, 이진 탐색 트리만 만족하는 조건은 아니기에 이렇게 대채하는 것은 불가능하다. 위의 두가지 조건을 만족하지만 이진 탐색 트리가 아닌 '이진 트리의 예'는 ? 루트 노드인 10보다 큰 값이 왼쪽 서브 트리에 존재한다. ..
-
에라토스테네스의 체알고리즘 이론/알고리즘 구현 2019. 8. 15. 18:55
에라토스테네스의 체 에라토스테네스의 체는 소수 관련 문제를 풀 때 가장 자주 사용되는 방법입니다. 소수란 '양의 약수를 두개만 가지는 자연수' 를 의미합니다. 이러한 소수를 대량으로 빠른 시간 내에 구하는 방법이 에라토스 테네스의 체 입니다. -지워지지 않는 수를 찾을때는 루트 n까지만 찾습니다. 소수 판정 알고리즘과 동일한 최적화. - 배수들을 지울 때 i*i에서 시작합니다. 2*i는 이미 2의 배수를 지워졌을때 지워 졌을것 3*i도 마찬가지 코드 ( C++ ) #include #include #include using namespace std; int n;// 소수인지 아닌지// IsPrime[i] = i 가 소수인가?bool IsPrime[101];void eratosthenes() {// 1로 I..
-
백준(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의 수 +..