본문 바로가기

분류 전체보기

 (160)
[TIL] 24.01.29 1. 알고리즘 문제 해결 2022는 무엇이 특별할까?(백준 24268): 간단한 백트래킹 문제이다. 브루트 포스가 아닌 어떤 수학적인 솔루션이 있지 않을까 계속 고민하다가 오히려 애를 먹었다. 한참 구현하다보니 코드 분기 처리가 너무 난잡해져서, 그제서야 브루트 포스로 구현했다. 단순하게 모든 경우를 고려하려고 하면 d^d 개의 케이스를 탐색해야해서 시간 초과가 난다. 처음에 이 생각 때문에 곧장 브루트 포스로 풀지 않았던건데, 다시 생각해보니 등장한 숫자들을 따로 저장해주는 배열이 있다면 d! 개의 케이스로 줄어들어서 충분히 풀 수 있었다. 또, d^(d-1) 자리는 문제 조건에 의해 0이 들어갈 수 없기 때문에 더 줄일 수 있다. 저정도 조건만 가지치기 해주고 백트래킹으로 풀었더니 무난하게 통과했다...
[TIL] 24.01.26 1. 알고리즘 문제 해결 Z(백준 1074): 간단한 분할 정복 문제, 한번 분할 할 때마다 크기가 4분의 1로 줄어든다. 먼저 배열의 중심을 기준으로 좌상단, 우상단, 좌하단, 우하단으로 나누어 찾으려는 좌표가 어디에 속하는지 찾는다. 이제 기준이 되는 배열 좌표를 수정하고, 좌표가 속한 위치에 따라 order값을 더해둔다(ex - 좌하단이었다면 변의 길이*변의 길이*2). 변의 길이를 절반으로 줄이고, 변의 길이가 1이 될 때까지 반복한다. 반복이 끝나면 order값을 출력한다. 시간복잡도는 O(N). 쿼드트리 (백준 1992): 마찬가지로 간단한 분할정복 문제이다. 재귀를 이용해서 문제 내용을 그대로 구현하면 쉽게 해결된다. 압축 함수를 만들고 전달받은 범위 내 원소가 모두 같은지 확인해서 같다면 ..
[TIL] 24.01.25 1. 알고리즘 문제 풀이 순열장난(백준 10597): 백트래킹으로 구현하는 문제. 주어지는 수열의 길이로 N을 알아낼 수 있고, 조금 신경써서 백트래킹 조건을 설정해주면 된다. 나는 수열의 끝까지 탐색이 끝났을 때를 base condition으로 설정했고, 여러 복구 수열이 나왔을 때 중복 출력을 방지하기 위해 checkFlag를 두었다. 그리고 탐색 중인 경우라면, 수열 내에서 현재 탐색중인 index에 대해 한 자릿수로 볼 때와 두 자릿수의 일부로 볼 때로 나누어 recursive하게 구현했다. #include #include using namespace std; string s; bool checkFlag=false; int n; vector isUsed; vector ans; void solve(..
[TIL] 24.01.24 1. 알고리즘 문제 풀이 알파벳(백준 1987): 기본적인 DFS, 백트래킹 문제이다. DFS로 탐색하되 인접 칸이 모두 유효하지 않을 경우, 현재까지의 이동 칸 수를 가지고 최대 이동 칸 수를 갱신한 뒤 백트래킹으로 돌아간다. 원래 탐색 알고리즘에서는 노드의 방문처리가 필요한데, 이 문제에선 방문한 알파벳을 확인해야하므로 이를 통해 노드의 방문처리도 가능하다. 비트마스크를 이용하면 좀 더 최적화가 가능할 것 같긴하다. #include #include #include using namespace std; int dx[4] = {1, 0 , -1, 0}; int dy[4] = {0, 1, 0, -1}; vector matrix; vector isVisited(26, false); int w, h, maxN..
[TIL] 24.01.23 1. 알고리즘 문제 해결 외판원 순회 2(백준 10971): 외판원 순회 문제(TSP) 문제는 이미지의 문제 설명에서도 나와있듯이, 굉장히 유명한 문제이다. 내 기억으로 NP-hard에 속하는 문제인데, 근사해를 찾는 것이 아닌 최적해를 찾는 알고리즘의 경우 가장 빨라도 지수시간이 걸렸던 것으로 기억한다. DP로 푸는 것과 Branch and Bound로 푸는 것을 배웠었는데, 두 쪽다 실제 코드로 구현하는 것은 만만하지 않다. 이 문제는 도시의 수 범위가 최대 10개까지이므로, 사실 순열 문제로 치환해서 풀게 되면 (10-1)! 만큼의 탐색이 필요하므로, 무난하게 통과할 수 있을 것이다. 하지만 예전에 배웠던 것을 한 번 리마인드할 겸, DP와 비트마스킹을 이용해 풀기로 했다. #include #inc..
[TIL] 24.01.22 1. 알고리즘 문제 해결 부분수열의 합 2(백준 1208): 저번에 풀었던 부분수열의 합 문제와 유사한데, N이 40개까지 주어질 수 있다는 점이 다르다. 순수하게 조합되는 경우의 수만 따져도 2^40이기 때문에 저번에 풀었던 방법으로는 풀 수 없다. 처음에는 dp를 이용해서 풀려고 했다. 주어진 수열에서 나올 수 있는 값들에 대한 카운트 배열을 두 개 만들어두고, 원소 1개를 선택할 때부터 시작해서 배열을 번갈아가며 선형 탐색 및 업데이트 하는 방식이었다. 근데 이때 나올 수 있는 값의 범위가 [-100,000 * 40, 100,000 * 40]이기 때문에 이 배열을 n번 탐색하는 것은 시간이 초과된다. 그래서 수열을 분할하여 풀었다. 수열을 절반으로 나누어 왼쪽 수열 에 대해 나올 수 있는 합 별로 ..
[TIL] 24.01.20 1. 안드로이드 공부 오늘은 어제 해결하지 못한 에러가 너무 신경쓰여서, 안드로이드 쪽을 켰다. 한시간 넘게 끙끙대면서 하나 해결하면 또 다른 에러가 생기고, 다시 해결하면 또 다른 에러가 생기고를 반복했다. 일단 어제 라이브러리와 플러그인 버전들을 모두 최신화 시키거나, 버전에 관한 문서들을 뒤져가며 모두 맞춰두었다. 그래서 처음의 오류는 해결을 한 상태였다. 그런데 앱을 실행하면, MainActivity를 띄우지 못하고 바로 죽으면서 java.lang.RuntimeException: Unable to start activity ComponentInfo{앱 패키지명/앱 패키지명(디렉토리).MainActivity}: android.view.InflateException: Binary XML file li..
[TIL] 24.01.19 1. 알고리즘 문제 해결 트리와 쿼리(백준 15681): 임의의 루트와 간선의 정보가 주어지기 때문에, DFS나 BFS로 트리 내의 부모 자식 관계는 찾아낼 수 있다. 물론 그 정보를 바탕으로 각 쿼리에 대해 매번 탐색을 통해 서브트리의 정점 수를 세면 O(N*Q)로 당연히 시간 초과가 난다. 그래서 DP 문제를 풀듯이 각 정점을 루트로하는 서브트리의 정점 수를 저장해놓고, 쿼리들에 대해 바로 답을 출력해주도록 해야한다. 나는 그 값들을 트리를 구축하면서 함께 구해버리기 위해 재귀를 통한 DFS를 사용했다. 유의해야하는건, 서브트리를 구성하는 정점의 수에 본인도 포함해야 한다. #include #include using namespace std; vector adjacentList; vector subt..

티스토리툴바