본문 바로가기

분류 전체보기

 (141)
[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..
[TIL] 24.01.18 1. 알고리즘 문제 해결 N과 M (5)~(8) (백준 15654, 15655, 15656, 15657): 문제들이 다 골자는 같고 상세 조건만 조금씩 다른 유형이라 이미지는 하나만 업로드 했다. 보고 있던 강의에선 재귀를 이용한 순열, 조합 문제라고 했는데, 백트래킹의 기초에 가깝다. N이 충분히 작기 때문에 메모리 스택 걱정 없이 재귀로 편하게 구현하면 된다. 트리의 부모 찾기(백준 11725): 브루트 포스는 O(n^2)로 시간 초과이고, 인접행렬을 이용하면 메모리가 초과될 것이다. 그래서 각 vertex에 대해 인접 리스트를 사용해야 한다. 이후에는 BFS로 풀면되는데, 처음 제출했을 때 1%에서 바로 틀렸다. 대체 왜 틀렸나 싶어서 꽤 오래 고민한 것 같다. 다시보니 이진 트리가 아니라 그냥 트..
[TIL] 24.01.17 1. 알고리즘 문제 해결 스택 수열(백준 1874): 스택 자료구조를 이용한 단순 구현 문제. 외계인의 기타 연주(백준 2841): 처음에 기타 줄을 누르는 손가락이 5개라고 생각해서 조금 복잡한 구현 방식을 떠올렸는데, 다시보니 손가락이 수십억개인 외계인이 기타를 치는 문제였다. 음의 수가 500,000개가 최대고 줄의 수도 6개 밖에 되지 않아서 그냥 스택 6개짜리 벡터 생성해서 풀었다. C++ 기준으로는 빈 스택의 top을 참조하지 않도록 조금 신경써줘야 한다. 오큰수(백준 17298): 단순하게 브루트 포스로 접근하면 O(n^2)가 되어 시간초과가 날 것이다. 처음엔 i+1~n번째에 해당하는 부분 수열에 대해 인덱스를 포함한 pair로 만들고, 값과 인덱스 둘 모두 이용하는 우선순위 큐를 만들까 ..
[TIL] 24.01.16 1. 알고리즘 문제 해결 키로거(백준 5397): 자료 구조 기반 단순 구현문제. 커서 좌우 부분을 각각 스택으로 나누어 해결했다. 링크드 리스트로 해결해도 무난할 것 같다. PPAP(백준 16120): 처음에는 KMP 알고리즘이나 보이어-무어 알고리즘 같은 스트링 매치 알고리즘을 이용하려고 했다. 문자열 내에서 "PPAP"를 찾아 "P"로 변경하려는 생각이었다. 그런데 입력으로 들어오는 문자열의 최대 길이가 1,000,000인데, 변경된 문자열을 계속해서 탐색-변경 해줘야해서 시간 초과가 날 것 같았다. 그리고 문자열의 대부분이 같은 글자이고, 탐색해야 하는 Substring의 접두사와 접미사가 같기 때문에 스트링 매치 알고리즘들이 큰 효과를 보이지 않을 거 같기도 했다. 그래서 스택을 이용했다. 스택..

티스토리툴바