꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/14651 백준 14650번 걷다보니 신천역 삼(Small)(http://jaimemin.tistory.com/774)와 달리 단순 브루트 포스로는 풀 수 없는 문제였습니다.DP(Dynamic Programming)을 적용시킬 수 없을까라고 생각하는 와중에 단순한 점화식이 보였습니다.점화식은 아래와 같습니다.1. 길이가 1일 때는 0, 길이가 2일 때는 2, 길이가 3일 때는 6, 길이가 4일 때는 18, ...2. 따라서 cache[2]=2로 저장하고 길이가 3일 때부터 cache[i]=(cache[i-1]*3) % MOD 연산을 통해 계산하면 되는 문제였습니다. #include #include //memset using nam..

문제 링크입니다: https://www.acmicpc.net/problem/14650 N의 범위가 작기 때문에 해당 문제는 브루트 포스(Brute Force) 방식으로 풀어도 되는 문제였습니다. 알고리즘은 아래와 같습니다.1. 각 자리 수에 숫자를 추가합니다.2. 마지막 자리 수에 숫자를 추가했을 때 조건을 살핍니다.i) 각 자리 수의 합이 3으로 나누어 떨어지면 3의 배수ii) 이외의 경우는 3의 배수가 아닙니다. #include using namespace std; int N; long long multipleOfThree(int num, int sum, int length) { //조건 충족 if (length == 1 && sum % 3 == 0) return 1; //조건 불충족 else if ..

문제 링크입니다: https://www.acmicpc.net/problem/1194 백준 9328번 열쇠(http://jaimemin.tistory.com/692)처럼 열쇠가 주어진 BFS(Breadth First Search) 알고리즘 문제였습니다.하지만 9328번과 다르게 해당 문제에는 열쇠가 6개 밖에 없고 한 열쇠를 한 번 이상 사용할 수 있기 때문에 비트를 이용해 열쇠를 표현하는 것이 바람직합니다. 알고리즘은 아래와 같습니다.1. 미로를 입력받고 출발점을 찾습니다.2. 출발점으로부터 전형적인 BFS 탐색을 시작합니다.i) 열쇠를 얻는 순간 다시 모든 곳을 탐색할 수 있어야하므로 visited를 key, y, x에 대해 삼차원 배열로 선언합니다.ii) 열쇠를 주우면 OR 연산을 통해 소지한 열쇠를..

문제 링크입니다: https://www.acmicpc.net/problem/10775 Union Find(=Disjoint Set) 자료구조를 사용하는 알고리즘 문제였는데 기존에 풀었던 문제들보다 난이도가 있는 문제였습니다.저도 kks227(https://kks227.blog.me/220791837179?Redirect=Log&from=postView)님의 포스팅을 보고나서야 풀 수 있었습니다. 문제에서 요구하는 바는 최대한 많은 비행기를 배치하되 게이트 당 하나의 비행기를 배치하는 것이였습니다.상당히 간단해보이지만 매 쿼리마다 모든 게이트를 확인한다면 TLE가 발생하는 것이 자명하기 때문에 구현이 어려운 문제였습니다. kks227님의 알고리즘은 아래와 같습니다.1. 모든 비행기가 게이트(1~G) 중 한..

문제 링크입니다: https://www.acmicpc.net/problem/4195 Union Find(=Disjoint Set) 자료구조를 통해 풀 수 있는 문제였습니다. 기존의 문제들과 비교해서 까다로웠던 점은 원소가 인덱스로 주어지지 않고 사람 이름으로 주어진다는 점이였습니다. 따라서 map를 통해 사람 이름에 인덱스를 부여하여 문제를 푸는 것이 핵심이였습니다. 알고리즘은 아래와 같습니다. 1. 두 사람 이름을 입력 받습니다. i) 기존에 등장한 이름이라면 map에서 인덱스를 찾습니다. ii) 새로 나온 이름이라면 새로운 인덱스를 부여하고 map에 저장합니다. 2. 두 사람의 루트를 탐색합니다. i) 같은 집합 내에 있다면 해당 집합의 크기를 출력해줍니다. ii) 다른 집합에 있다면 두 집합을 합쳐..

https://www.acmicpc.net/problem/1976 Union Find(=Disjoint Set) 자료구조를 사용하는 쉬운 난이도의 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 초기에는 모든 도시의 부모가 자기 자신입니다.2. 인접한 도시끼리 집합을 합쳐줍니다.(merge 함수를 통해)3. 마지막에 M개의 도시들이 모두 같은 집합 내에 속해 있는지 확인합니다.i) 모두 같은 집합이면 여행을 갈 수 있습니다.ii) 하나라도 다른 집합에 있다면 여행을 갈 수 없습니다. #include #include #include using namespace std; const int MAX = 200 + 1; int N, M; int arr[MAX]; //부모 찾는 연산 int findParen..

문제 링크입니다: https://www.acmicpc.net/problem/1717 카카오 Code Festival 예선에서 Union Find(=Disjoint Set) 자료구조를 사용하는 문제들에서 막혔기 때문에 풀어봤던 문제였습니다. 알고리즘은 아래와 같습니다.1. 초기에는 0~N까지의 집합의 부모는 자기 자신입니다.(-1로 표현)2. 0이 입력되면 합치는 연산입니다.i) 같은 원소에 대해 합치거나, 부모가 동일한 원소를 합칠 필요가 없습니다.ii) 집합의 크기가 큰 쪽에 작은 쪽을 합쳐줍니다.->여기서 집합의 크기는 abs(arr[parent]) 즉, 부모 인덱스에 있는 값의 절대값으로 표현합니다.3. 1이 입력되면 탐색하는 연산입니다.i) 같은 원소이거나, 부모가 동일한 원소이면 같은 집합 내에..

문제 링크입니다: https://www.acmicpc.net/problem/15961 슬라이딩 윈도우(Sliding Window) 기법을 적용하는 문제였습니다. 알고리즘은 아래와 같습니다.1. 첫 번째 스시부터 K개의 스시를 덱에 집어넣고 종류를 셉니다.2. N - 1번 반복문을 돌리면서 맨 앞에 있는 스시를 빼고 다음 스시를 덱에 집어넣습니다.i) 뺀 스시의 종류가 덱에 더 이상 없을 경우 cnt를 빼줍니다ii) 집어 넣은 스시의 종류가 기존 덱에 존재하지 않았을 경우 cnt를 더해줍니다iii) 덱에 쿠폰으로 제공되는 스시의 종류가 없을 경우 cnt를 하나 더해줍니다.3. 1, 2번에서 구한 값들 중 최대를 출력해줍니다. 회전초밥집이기 때문에 더해주는 스시 인덱스를 (i+K)%N으로 해주는 것이 핵심이..

문제 링크입니다: https://www.acmicpc.net/problem/8979 정렬(Sorting) 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. pair형 배열을 선언하여 국가번호, 금, 은, 동 순으로 입력받습니다.2. 정렬 조건을 위해 cmp 함수를 작성하는데 아래와 같이 작성합니다.i) 금을 기준으로 내림차순 정렬ii) 금이 같을 때 은을 기준으로 내림차순 정렬iii) 금, 은이 같을 때 동을 기준으로 내림차순 정렬iv) 금, 은, 동이 같을 때 K번째 나라가 제일 앞에 오도록3. 배열을 탐색하면서 국가번호가 K번째인 나라의 인덱스를 출력해주면 됩니다. #include #include using namespace std; const int MAX = 1000 + 1; int N, K..

문제 링크입니다: https://www.acmicpc.net/problem/8980 KOI 초등부 문제이지만 제 기준 접근 방법이 어려웠던 그리디(Greedy) 문제였습니다. 알고리즘은 아래와 같습니다.1. 트럭은 한번 방문한 도시를 다시 방문하지 않고 1번 도시부터 출발하기 때문에 1번 도시와 가까운 순으로 박스를 옮기는 것이 최적입니다.2. 따라서 도착 도시를 기준으로 오름차순 정렬을 해주고 도착 도시가 같다면 시작 도시를 기준으로 오름차순 정렬을 해줍니다.3. 시작도시부터 도착도시까지 가장 많이 적재된 박스 양을 구합니다.4. 3번에서 구한 값에 대해 더 적재할 수 있는 양을 파악하고 결과 값에 더해줍니다.5. 해당 구간에 4번에 구한 값만큼 더해줍니다.6. 3~5번을 M번 반복합니다. 결국 이 문..