꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1727 문제가 분류되어있는대로 정렬 + 다이나믹 프로그래밍으로 푼 문제였습니다. 알고리즘은 아래와 같습니다.1. 남여 수치를 입력받고 오름차순 정렬을 합니다.2. 다이나믹 프로그래밍을 진행하는데 아래와 같이 세가지 경우가 있습니다.i) i == j인 경우 커플이 되었으므로 해당 커플의 수치 차의 절대값을 cache[i][j]에 저장해줍니다.ii) i > j인 경우 남자가 더 많으므로 해당 커플의 수치 차의 절대값 혹은 i번째 남자를 솔로로 둡니다.iii) i < j인 경우 여자가 더 많으므로 해당 커플의 수치 차의 절대값 혹은 j번째 여자를 솔로로 둡니다.3. 2번을 진행한 뒤 cache[N][M]을 출력해줍니다. #includ..

문제 링크입니다: https://www.acmicpc.net/problem/1525 재미있는 브루트 포스(Brute Force) + BFS(Breadth First Search) 문제였습니다.핵심은 비어있는 칸 0을 9로 바꿔주는 것이였습니다! 알고리즘은 아래와 같습니다.1. 3*3칸에 존재하는 숫자들을 좌상단부터 우하단까지 이어지는 숫자로 표현할 것이기 때문에 퍼즐을 입력받을 때 비어있는 칸 0을 9로 바꿔줍니다.2. 전형적인 BFS처럼 큐에 시작하는 숫자 조합을 넣어 TARGET(123456789)이 나오거나 혹은 큐가 빌 때까지 빈 칸을 동서남북으로 swap 하며 숫자의 조합을 확인합니다.3. TARGET이 나왔었다면 몇 번 swap했는지 출력하고 나오지 않았다면 -1을 출력해줍니다. #includ..

문제 링크입니다: https://www.acmicpc.net/problem/10971 Algospot TSP1(http://jaimemin.tistory.com/304)과 유형이 같은 브루트 포스(Brute Force) 문제였습니다. 알고리즘은 아래와 같습니다.1. 외파원은 0번째 도시에서부터 시작한다고 가정하고 나머지 도시들의 모든 순서를 next_permutation을 이용하여 조합해봅니다.2. 모든 도시를 방문했다면 방문하는데 걸었던 거리를 현재 result와 비교해서 업데이트해줍니다.-> 다시 0번째 도시까지 돌아오는 거리도 더해줘야합니다!!3. result를 출력해줍니다. #include #include #include #include using namespace std; const int MA..

문제 링크입니다: https://www.acmicpc.net/problem/10819 next_permutation을 이용하여 쉽게 풀 수 있는 문제였습니다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; vector v(N); for (int i = 0; i > v[i]; int result = 0; sort(v.begin(), v.end()); do { int temp = 0; for (int i = 0; i < v.size() - 1; i++) temp += abs(v[i] - v[i + 1]); r..

문제 링크입니다: https://www.acmicpc.net/problem/15684 백준 15683번 감시(http://jaimemin.tistory.com/1070)와 유형이 비슷한 브루트 포스(Brute Force) 문제였습니다. 알고리즘은 아래와 같습니다.1. 사다리를 표시할 때 ladder[y][x] = true라고 하면 y번째 높이에서 x ~ (x+1)을 이어주는 다리를 놓는다고 표시해줍니다.2. 사다리를 0개부터 3개까지 설치해보고 설치할 때마다 DFS 함수를 호출해줍니다.i) 현재 높이에서부터 (H-1)번째 높이까지 다리를 하나하나 설치해보며 DFS 함수를 재귀호출합니다.ii) 기저 사례로 설치하고자 하는 사다리의 개수가 DFS 함수를 호출하면서 설치한 사다리의 개수가 같아지면 i번째 사다..

문제 링크입니다: https://www.acmicpc.net/problem/1213 문자열의 최대 길이가 50이기 때문에 브루트 포스(Brute Force)로 접근해도 무방한 문제였습니다. 팰린드롬을 만들 수 있는 조건은 아래와 같이 두 종류가 있습니다.1. 모든 문자가 짝수개 있다.2. 하나의 문자가 홀수개 있고 나머지 문자들이 짝수개 있다. 1번의 경우 문자열을 사전순으로 정렬한 상태에서 새로운 문자열에 (각 문자의 개수의 반)만큼 문자열을 추가해주고 출력한 뒤 거꾸로 출력해주면 팰린드롬이 완성됩니다.2번의 경우 1번의 경우와 똑같은데 거꾸로 출력해주기 전에 홀수개였던 문자 하나를 추가해주고 거꾸로 출력해주면 됩니다! #include #include #include using namespace std..

문제 링크입니다: https://www.acmicpc.net/problem/10827 kks227님의 깃헙을 참고해서 푼 문제입니다.kks227님이 C++에서 bigInteger 연산 구현을 정말 잘 정리하셨기 때문에 그대로 사용했습니다. #include #include #include using namespace std; //kks227님 출처 //bigInteger 덧셈 구현 string Add(string &s1, string &s2) { string result(max(s1.size(), s2.size()), '0'); bool carry = false; for (int i = 0; i < result.size(); i++) { int temp = carry; carry = false; if (i..

문제 링크입니다: https://www.acmicpc.net/problem/1780 백준 1992번 쿼드트리(http://jaimemin.tistory.com/1072)와 비슷한 문제였습니다.4분할을 하는 대신 9분할을 하면 되는 문제였습니다. #include using namespace std; const int MAX = 2187; //3^7 int N; int arr[MAX][MAX]; int result[3]; void func(int n, int y, int x) { //기저 사례 if (n == 1) { result[arr[y][x] + 1]++; return; } bool minus = true, zero = true, plus = true; for(int i=y; i N; for (int ..

문제 링크입니다: https://www.acmicpc.net/problem/11729 백준 1914번 하노이 탑(http://jaimemin.tistory.com/732)의 쉬운 버전이었습니다. #include #include using namespace std; int N; vector v; void Hanoi(int num, int from, int by, int to) { if (num == 1) v.push_back({ from, to }); else { Hanoi(num - 1, from, to, by); v.push_back({ from, to }); Hanoi(num - 1, by, from, to); } } int main(void) { ios_base::sync_with_stdio(0);..

문제 링크입니다: https://www.acmicpc.net/problem/16528 다익스트라(Dikjstra) 문제인데 조금 꼬아서 낸 문제였습니다.전형적인 다익스트라 문제와 다르게 '고속도로 유지 비용'이라는 변수도 추가되었습니다. 알고리즘은 아래와 같습니다.1. 고속도로 유지 비용이 추가되었기 때문에 pair 대신 Edge 구조체를 정의해줍니다.-> 우선순위 큐를 사용할 것이기 때문에 < 연산자도 정의해줍니다.a) 거리가 가까울수록b) 거리가 같다면 가격이 저렴할수록c) 우선순위가 높습니다.2. 전형적인 다익스트라 알고리즘을 진행합니다.i) e.city에서 next.city로 가는 거리가 기존에 저장된 거리보다 가깝다면 거리를 업데이트하고 유지 비용도 업데이트해주고 우선순위 큐에 해당 정보를 넣어..