컴굥일지

문제 https://www.acmicpc.net/problem/11582 문제 내용 하나의 배열을 정렬하는데, 이때 중간단계를 출력하는 문제이다. 참고로 여기서 쓰인 정렬의 방식은 합병 정렬이다. (합병 정렬에 대한 설명은 더보기에 있다.) 더보기 더보기 합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 방식이다. 합병 정렬은 분할 정복이라는 기법에 바탕을 두고 있다. 분할 정복 기법은 문제를 작은 2개의 문제로 분할하고, 각각을 해결한 뒤에, 결과를 모아서 원래의 문제를 해결하는 방식이다. 문제 풀이 문제에서 설명한 방식대로 정렬을 진행한다. (sort 함수 이용) 이때, k명이 정렬을 하..

문제 https://www.acmicpc.net/problem/11656 문제 내용 문자열을 입력받아, 접미사를 사전 순으로 정렬하여 출력하면 된다. 문제 풀이 이 문제에서 그나마 가장 까다로운 부분은 접미사를 만들어내는 부분이다. string 클래스의 substr(시작 지점, 문자 개수) 함수를 사용하면 쉽게 해결할 수 있다. 이 문제에서는 반복문을 n부터 시작해서 1씩 감소시켰다. 이는 첫번째 인자를 n-i로 하여 0부터 n-1까지 증가하도록 했으며, 두 번째 인자는 i로 하여 n부터 1까지 감소하도록 했다. ex) [school] => school, chool, hool, ool, ol, l 순으로 저장된다. 코드 #include #include #include #include using names..

문제 https://www.acmicpc.net/problem/20044 문제 내용 학생들의 코딩 역량을 입력받아 두명씩 팀을 짠다. 이때, 팀의 코딩 역량의 차이가 최소화 되어야 한다. 문제 풀이 학생들의 코딩 역량을 입력받아 값을 정렬한다. 그리고 배열의 양쪽 끝에서부터 팀을 만들어가면 된다. (가장 작은 값과 가장 큰 값을 이어주는 것) 코드 #include #include #include using namespace std; int n, a, num, mmin; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 cin >> n; //팀의 개수 vectorv; for (int i = 0; i < 2*n; i++) { /..

문제 https://www.acmicpc.net/problem/16206 문제 내용 롤케이크를 잘라서 길이가 10인 롤케이크를 최대한 많이 만드는 문제이다. 문제 풀이 Q) 롤케이크의 길이가 [10,34,20,14,20]이고, 자를 수 있는 횟수가 2번이라면 어떻게 해야 할까? 1) 그냥 정렬한 뒤에 순서대로 자른다. - 먼저 정렬하면 [10,14,20,20,34]가 된다. 여기서 10은 칼질하지 않아도 되고, 14는 한번, 20도 한 번의 칼질이 필요하므로 10 / 14(10,4) / 20(10,10)으로 총 4개의 길이가 10인 롤케이크가 나온다. 2) 정렬을 하긴 하되, 10 단위의 롤케이크 부터 먼저 처리하는 경우 - 10단위의 길이가 먼저 오도록 정렬을 하면 [10,20,20,14,34]가 된다..

문제 https://www.acmicpc.net/problem/14659 문제 내용 아래와 같이 봉우리들에 활잡이들이 한 명씩 있다. 모든 활잡이는 자신의 오른쪽으로 활을 쏠 수 있으며, 자신보다 낮은 위치의 적만 잡을 수 있다. 최고의 활잡이가 처치할 수 있는 적의 최대 숫자를 출력하면 된다. 문제 풀이 반복문과 조건문을 통해 봉우리의 높이를 비교해야 한다. 위의 사진을 보면, 봉우리가 0번부터 시작한다고 했을 때, 2번과 3번 봉우리를 비교하면 2번이 더 높다. 그렇기 때문에 3번은 자신보다 낮은 봉우리의 개수가 몇 개인지를 구할 필요가 없다. 즉, 자신보다 낮은 봉우리의 개수를 카운트 하다가 자신보다 높은 봉우리를 만나면 지금까지 지나온 낮은 봉우리 개수와, 이전에 카운트했던 개수를 비교하여 max..

문제 https://www.acmicpc.net/problem/2847 문제 내용 각 레벨에서 얻을 수 있는 점수를 오름차순으로 만들어야 한다. 즉, 최고점을 기준으로 각 단계를 몇 번 감소시켜야 할지를 계산하면 된다. 항상 답이 존재하는 경우만 입력으로 주어진다고 되어있으므로, 점수를 감소시키다가 음수가 되는 일은 발생하지 않는다. 문제 풀이 그렇게 어려운 문제는 아니다. 배열을 뒤에서부터 반복문을 돌면서 i번째 값과 i-1의 값을 비교하면 된다. 조건문을 통해 i번째 값이 큰 경우는 별다른 처리 없이 넘어가면 된다. i번째 값이 작은 경우 i-1번째 값과 i번째 값이 적어도 1은 차이가 나야 하기 때문에 (두 값의 차이 -1)를 구하여 계산하면 된다. 코드 #include #include #inclu..

문제 https://www.acmicpc.net/problem/2839 문제 내용 Nkg의 설탕을 3kg 또는 5kg 봉지로 나누어 담아야 한다. 이때, 정확하게 Nkg을 만들면서 봉지의 개수를 최소화하는 것이 목표이다. 문제 풀이 Greedy를 사용하여 문제를 풀었다. 설탕이 15kg가 있다면 3kg 5봉지와 5kg 3봉지로 채울 수 있다. 이 경우, 5kg 3봉지로 채우는 것이 정답이다. 즉, 5로 나눌 수 있다면 5kg을 사용하고, 그렇지 않다면 3kg을 사용하면 된다. 코드 #include using namespace std; int n, cnt; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 cin >> n; /..

문제 https://www.acmicpc.net/problem/1931 문제 내용 회의의 시작시간과 종료시간을 입력 받아서, 회의실을 최대로 사용할 수 있는 회의의 개수를 출력하는 문제이다. 문제 풀이 Greedy를 사용하여 문제를 풀었다. 문제를 보고 떠올릴 수 있는 선택은 3가지 정도 있었다. 회의 시작 시간이 빠른 순서 / 회의 시간이 짧은 순서 / 회의가 빨리 끝나는 순서 각각의 경우에 대해 설명해보자면 1) 회의 시작 시간이 빠른 순서의 경우 - 회의를 아무리 빨리 시작해도 회의시간 자체가 길면 그 사이에 회의들이 여러개 들어가지 못하게 된다. 2) 회의 시간이 짧은 순서 - 회의 시간이 짧은 순서대로 먼저 집어넣다보면, 아래와 같은 경우가 생긴다. 3) 회의가 빨리 끝나는 순서 - 회의가 빨리..

1. 프로젝트 주제 어릴 때, 동화책을 읽다 보면 부모님이 옆에서 "이다음엔 어떻게 되었을까?" 라던가 "여기서 다른 선택을 했으면 어땠을까?"와 같은 질문을 던지곤 합니다. 그러면 어렸던 저는 이제 질문을 듣고 막 상상을 하면서 뒷 이야기를 생각하곤 했습니다. 저희 팀의 프로젝트 주제(참여형 동화 서비스)는 이러한 경험으로부터 나오게 되었습니다. 현재 저희 팀은 5~7세 대상의 동화책을 dataset으로 모으고 있습니다. 이 dataset으로 학습을 시킬 예정입니다. 제가 이번에 맡은 부분은 동화를 생성하는 파트입니다. 기술 조사에서 동화 생성을 맡는 기술로 GPT3와 KoGPT2가 거론되었습니다. 그러나 GPT3가 유료이기 때문에 일단은 KoGPT2를 사용해보기로 했습니다. 2. 진행 내용 프로젝트 ..