알고리즘,PS

https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 문제 풀이 단순 그리디 접근 방법으로 풀 수 있다. 1. 상자랑 크레인을 입력받아 무거운 순 으로 정렬 2. 크레인 갯수 만큼 상자를 순회하여 만약 크레인이 이 상자를 적재 가능하면 상자리스트에서 제거 3. 다음 크레인으로 상자를 순회하여 적재가능하면 또 제거 .. 이런식으로 반복 4. 크레인을 순회할때마다 시간1초씩 늘려주고 , 상자리스트가 is.Empty()면 끝 1 2 3 4..

https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 문제 풀이 학생들이 각자 받고싶은 책의 범위들에서 적절하게 분배 해 줘야하는데 만약 1번 학생이 1,2,3 의 책 번호를 골랐고 2번 학생이 2,3 책 번호를 골랐다고 하면 2번 학생은 1번책을 받지 못하기때문에 1번 학생에게 우선 1번책을 주고 그다음 2번학생에게 2번 or 3번의 책을 줘야한다. 다른예시로 1번학생이 1,2의 책 번호를 골랐고 2번학생이 2,3의 책 번호를 3번 학생이 2,3을 골..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 풀이 처음엔 한 가방에 하나의 보석밖에 못넣는다고 적힌것 못 보고 Knapsack 문제 + 가방이 여러개 ..? 라고 접근할 뻔 했다가 산으로 갈 뻔 했다.. 접근방법 용량이 작은 가방과 무게가 작은 보석 순으로 천천히 순차적으로 보고 , 조건에 맞으면 그 가방에 보석을 넣는 방식으로 하면 된다. => 그리디 접근 가령 , 예제 2..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 풀이 그냥 완전 그리디 노가다.. 1보다 큰 수들 => 높은 수 순으로 2개씩 묶음 , 나머지들은(1이 있거나 하나 남았거나) 그냥 합산 0보다 작은 수들 => 2개씩 묶으면 양수가 되기때문에 제일 작은 수 순으로 2개씩 묶음. 하나 남은 음수는 0 이 있으면 그냥 패스 하거나 0이 없으면 그냥 더해주면 끝 1보다 큰수 , 0 , 0보다 작은수를 list 3개 만들어서 각각 따로 넣어주고 ..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 풀이 카드뭉치가 여러개 있고 한 뭉치씩 차례대로 합칠 때 카드의 갯수가 적은 순서로 합치면 된다. 카드 갯수가 적은 뭉치 2개를 하나로 만들고 , 만들어진 하나의 뭉치를 또 비교대상으로 쓰면 된다는 것 예를들어 30 40 50 60 이 있다고 가정하면 30+40 = 70 이 되고 , 70장의 하나의 뭉치를 50장짜리 뭉치랑 합치는 것이아닌 50 60 70 중에 갯수가 적은 순의..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제 풀이 수학적으로 더 쉽게 풀 순 있지만 , 완전탐색 그리디를 연습중이므로 완전탐색으로 접근하였다. 주어진 단어들의 알파벳들이 몇 가지인지 리스트에 저장. 알파벳에 0~9 까지의 숫자들을 완전탐색으로 매핑 탐색이 진행될때마다 depth 카운트를 하나씩 증가시키면서 주어진 단어의 길이와 depth가 같아질 때 탐색을 그만하고 계산해서 제일 높은 값이 나오면 끝 1 2 3 4 5 6 7 8 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 12주차 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 풀이 입장 피로도와 소모피로도 두 가지가 있는데 만약 입장컷이 큰 순서대로 간다면 .. ? => 예제에서 3번째 던전을 못 돌기때문에 fail 그렇다고 작은 순서대로 간다면 .. ? => 입장컷이 큰 것이 나중에 나오면 못 돌기때문에 fail 결론 => 완전탐색 던전의 방문여부를 visit , 던전을 통과한 시점으로 남은 피로도를 tired , 던..

https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 문제 풀이 첫번째. 1면, 2면, 3면 인 경우의 최소합을 각각 구하기 두번째. N개 일때 1,2,3 면이 각각 몇개 나오는지 구하기 1. 3면이 나와야 하는 경우 - 맨 윗면 꼭지점 부분 4군데 : 4 2. 2면이 나와야 하는 경우 - 전체 모서리 수에서 육면체 꼭지점 부분을 뺀 값 + 맨 아래 꼭지점부분 4 : 8(N-2)+4 3. 1면이 나와야 하는 경우 - 각 면마다..