꾸준함

문제 링크입니다: 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; ..

삼성 SDS에서 주관하는 알고리즘 특강 대상자들이 대학교 3~4학년 학생들이여서 사전 테스트를 치뤘습니다.딱히 시간 제한이 없었기 때문에 마음 편히 풀었던 것 같습니다.B 난이도 4 번째 문제는 접근 방법도 알고 정해도 이미 봐버렸기 때문에 풀지는 않을 예정입니다.반면, A 난이도 4 번째 문제는 정답률만 봐도 어렵다는 것을 알 수 있습니다. 도대체 어떻게 접근해야할지 모르겠습니다... 브루트 포스 + 그리디로 접근해도 계속 틀리거나 시간초과가 떴기 때문에 현재는 포기한 상태입니다.

문제 링크입니다: https://www.acmicpc.net/problem/2250 중위 순회(Inorder Traversal) DFS(Depth First Search) 알고리즘을 적용하여 푸는 문제였습니다.알고리즘은 아래와 같습니다.1. 트리를 입력 받을 때 pair형 배열에 인덱스를 부모로 하고 자식들을 입력받습니다. 부모가 항상 1이 아니기 때문에 입력받는 노드를 세서 한번만 입력되는 노드를 루트로 정합니다.2. 중위 순회 DFS를 실행합니다. 이 때, 해당 높이에서 제일 좌측에 있는 노드와 제일 우측에 있는 노드를 업데이트합니다.3. 각 레벨을 탐색하면서 제일 긴 길이를 구하고 해당 높이와 길이를 출력합니다. 주의할 점은, 1번에서도 언급했듯이 1번 노드가 항상 루트가 아니라는 점입니다! #in..

문제 링크입니다: https://www.acmicpc.net/problem/3653 난이도가 높은 세그먼트 트리 응용 문제였습니다.많은 사람들이 펜윅 트리로 풀었지만 세그먼트 트리 알고리즘으로는 풀리지만 펜윅 트리 알고리즘으로는 풀리지 않는 문제들이 존재하기 때문에 세그먼트 트리 알고리즘을 이용하여 풀었습니다. 알고리즘과 코드는 lyzqm(https://lyzqm.blogspot.com/2017/07/segment-tree-3653.html?showComment=1531981580261#c7391195554365601508)님의 블로그를 참고하여 풀었습니다.기본적인 알고리즘은 아래와 같습니다.1. 배열을 M + N 크기로 설정하고 (M ~ N - 1)까지 1로 표시하고 (0 ~ M - 1)까지는 0으로 ..