꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1405 DFS(Depth First Search) 알고리즘을 이용하여 모든 경우를 탐색하면 되는 문제였습니다.동서남북으로 갈 확률이 자연수로 주어지기 때문에 0.01을 곱해 확률로 만들어 주는 것과 출력할 때 소수점 10의 자리까지 출력해주는 것만 조심하면 어렵지 않게 풀 수 있는 문제인 것 같습니다. 알고리즘은 아래와 같습니다.1. 한 방향으로 최대 14번 움직일 수 있기 때문에 (15, 15)에서 시작하고 판은 적어도 29*29여야 합니다.2. 한번 움직일 때마다 4방향 다 움직이면서 브루트 포스(Brute Force) 알고리즘을 적용하여 답을 탐색합니다. (다른 방향으로 탐색하기 전에 전 방향에서 밟았던 칸을 다시 밟지 않..

문제 링크입니다: https://www.acmicpc.net/problem/1744 간단한 그리디 문제이지만 벡터를 이용하여 구현하기는 힘든 문제였습니다.벡터에 모든 숫자를 넣고 조건문을 통해 그리디하게 접근하려다가 계속 틀려서 최근에 자주 애용하는 우선순위 큐를 이용하여 풀었습니다. 알고리즘은 아래와 같습니다.1. 1과 곱하면은 손해이기 때문에 1은 무조건 더합니다. 따라서, 1의 개수를 더해줍니다.2. 양수는 내림차순으로 저장하고 음수는 오름차순으로 저장해야 두 수를 곱했을 때 최대가 됩니다.3. 무조건 두 수를 곱한다고 가정하기 때문에 우선순위 큐의 크기가 홀수일 경우 오류가 발생합니다.i) 따라서, 양수가 저장되어있는 우선순위 큐 크기가 홀수이면 1을 넣어줘 짝이 없는 양수를 그대로 더해주게 합니..

문제 링크입니다: https://www.acmicpc.net/problem/11559 BFS(Breadth First Search) 알고리즘을 응용하여 푸는 시뮬레이션 문제였습니다. 알고리즘은 아래와 같습니다.1. 필드를 밑에서부터 위로 하나하나 확인하면서 BFS 알고리즘을 적용하여 4개 이상의 같은 색깔 블록이 상하좌우로 연결되었는지 확인합니다i) 4개 이상의 같은 색깔이 연속되어 붙어있으면 터뜨려야하므로 벡터에 넣습니다.ii) 동시에 터뜨릴 수 있다면 하나의 연쇄라고 생각하기 때문에 모든 색깔의 블럭에 대해 고려해줘야합니다.2. 블록을 터뜨렸다면 블록들의 위치가 바뀌기 때문에 while문을 통해 다시 1번을 진행하고 만약 또 터뜨릴 수 있다면 연쇄를 추가해줍니다.3. 터뜨릴 수 있는 모든 블럭을 터뜨..

문제 링크입니다: https://www.acmicpc.net/problem/6593 3차원 공간이지만 기존 방식대로 BFS(Breadth First Search) 알고리즘을 적용하면 쉽게 풀리는 문제였습니다.저 같은 경우에는 '.'을 0으로 '#'을 1로 표시하고 시작점과 도착점을 각각 pair 변수로 표시한 뒤 BFS 알고리즘을 적용했습니다. #include #include #include #include //memset using namespace std; const int MAX = 30; typedef struct { int z, y, x; }Dir; Dir moveDir[6] = { {1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0,..

문제 링크입니다: https://www.acmicpc.net/problem/1201 다음 주차 스터디에는 그리디 알고리즘(Greedy Algorithm)에 집중한다고 했는데 마침 슬랙에서 같은 학교 학우님이 질문하신 글을 보고 풀어본 문제였습니다.여태까지 최대 부분 증가 수열, 최대 부분 감소 수열 관련된 문제는 무조건 DP로 풀었기 때문에 DP 문제인 것처럼 보였지만 사실 그리디 알고리즘을 적용해야 풀 수 있는 문제였습니다. 알고리즘은 아래와 같습니다.1. 최대 증가 부분 수열과 최대 부분 감소 수열은 하나의 요소만 공유하기 때문에 N은 (M + K - 1) 이상이여하고 비둘기집 원리에 의해 숫자가 (M * K + 1)개일 때는 최대 증가 부분 수열의 길이는 M + 1, 최대 감소 부분 수열의 길이는 ..

문제 링크입니다: https://www.acmicpc.net/problem/1357 벡터를 이용하면 쉽게 풀 수 있는 문제였습니다.벡터에 매개변수로 전달받은 숫자를 역순으로 저장하고 해당 순서대로 숫자를 만들어주면 되는 문제였습니다. #include #include #include using namespace std; int Rev(int num) { vector v; //역순으로 벡터에 저장 while (num) { v.push_back(num % 10); num /= 10; } int result = 0; //뒤집은 숫자를 만들어 반환 for (int i = 0; i < v.size(); i++) result += v[i] * pow(10, (v.size() - 1 - i)); return resul..

문제 링크입니다: https://www.acmicpc.net/problem/1074 백준 14956번 Philosopher's Walk(https://www.acmicpc.net/problem/14956)의 쉬운 버전이었습니다. 똑같이 재귀를 이용해야하지만 해당 문제는 모든 사분면이 규칙적인 반면 힐버트 곡선(Hilbert Curve)의 경우 1, 2사분면과 3, 4사분면이 다르기 때문에 상당히 고난이도 문제였습니다.(그래서 아직까지도 못 풀고 있는 문제입니다... BaaaaaaaaaaaaaaaaaaaaaaarkingDog님한테 블로그 댓글을 통해 설명을 듣긴 했지만 구현은 여전히 못하는 상태입니다...ㅠ) 알고리즘은 아래와 같습니다. 1. 2 * 2 모양으로 계속 쪼개나갑니다.(1->2->3->4사분면..

문제 링크입니다: https://www.acmicpc.net/problem/1126 처음 보는 유형의 DP 문제였습니다.확실히 DP 카테고리 첫 페이지 끝에서부터는 능력자분들의 블로그 도움 없이는 못 푸는 것 같습니다 ㅠㅠ더 열심히 공부하면서 내공을 쌓아야겠다고 느낀 문제였습니다. 아래 알고리즘은 junodeveloper님(http://junh0.tistory.com/2)의 포스팅을 참고했습니다.junodeveloper님의 블로그에 그림과 함께 상세한 설명이 적혀있기 때문에 링크 참고하시는 것을 추천드립니다! 각 나무 블럭마다 4가지 경우의 수를 고려해줘야합니다.1. 해당 블럭을 쓰지 않을 경우2. 해당 블럭을 더 높은 탑에 쌓는 경우3. 해당 블럭을 더 낮은 탑에 쌓는 경우i) 해당 블럭이 탑 간의 높..

문제 링크입니다: https://www.acmicpc.net/problem/2229 한명으로 구성된 조도 있다는 것을 고려해준다면 어렵지 않은 DP 문제였습니다. 알고리즘은 아래와 같습니다.1. 조를 나누는데 1 ~ (N - idx)명까지 나눕니다.2. 해당 조의 최대 점수와 최소 점수 차를 더해가며 메모이제이션을 하면 됩니다. #include #include #include //memset using namespace std; const int MAX = 1000; const int INF = 987654321; int N, result; int arr[MAX]; int cache[MAX]; //idx int maxDifference(int idx) { //기저 사례: 범위 초과 if (idx == N..

문제 링크입니다: https://www.acmicpc.net/problem/9372 처음에는 BFS(Breadth First Search) 알고리즘을 적용하려고 했지만 그럴 필요가 없다는 것을 깨달았습니다.최소 스패닝 트리(Minimum Spanning Tree)는 N-1개의 간선으로 이루어져있기 때문에 결국 N-1 개의 간선 즉, N-1 종류의 비행기를 타야지 모든 도시를 방문할 수 있다는 것을 알 수 있습니다. #include #include #include using namespace std; const int MAX = 1000 + 1; int N, M; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); //cin 실행속도 향상 int T; ..