한달꾸 한달꾸

기존에 활동하던 블로그에서 옮겨온 포스팅 입니다. 문자열 집합 link 카카오 기출 중에 Trie자료구조를 활용해 풀어야하는 문제를 접했다. Trie라는 것에 대해 오늘 처음 들어봤기 때문에, 문제를 푸는것을 미루고 이에 대해 먼저 찾아봤다. 우리가 검색을 할 때 볼 수 있는 자동 완성 기능과 같이 문자열을 탐색하는데 특화되어있는 자료구조라고 한다. 각각의 노드들에 자식 노드를 저장시켜 놓고 단어를 탐색한다. 파이썬으로 구현할 때는 dictionary를 활용해 구현한다고 한다. 문제분석 n개의 문자를 입력받고, 다음으로 m개의 문자를 입력받는다. 이때 m개의 문자열 중에 n개의 문자열안에 포함된 문자열이 몇 개인지 알아내서 출력하는 문제이다. 입력범위가 크지 않기 때문에 단순히 배열을 사용해 풀어도 무난..

파이프 옮기기 1 click 내리막길 문제의 응용 버전이다. [내리막길 포스팅] 파이프가 가로로 위치하고 있을 때를 0, 대각선으로 위치하고 있을 때를 1 그리고 세로로 위치할 때 2라고 하자. 가로와 세로인 경우 해당 칸만 빈칸이라면, 위치시킬 수 있다. 하지만, 대각선인 경우, 해당 칸 위쪽과 왼쪽까지 빈칸이어야 위치시킬 수 있다. 가로 세로 대각선인 경우를 각각 탐색해 나가야 함으로, 각 칸에 길이 3인 배열을 추가한 3차원 배열(dp)을 만들었다. 이 배열에는 (n,m)으로 갈 수 있는 경우의 수를 저장할 것이다. 방문여부를 확인하기 위해서 dp배열의 초기값은 모두 -1로 설정했다. 방문한 지점은 0으로 변경해주어 방문 여부를 체크하기 위함이다. dp[n-1][m-1]은 [1,1,1]로 설정해 주..

기존에 활동하던 블로그에서 옮겨온 포스팅 입니다. 내리막 길 click 2020.10.13 오늘 내내 이 문제를 잡고 씨름했다.⚡ 먼저 두 시간 동안은 접근을 잘못해 고생했다. 어설프게 dp 점화식을 찾았다. 입력 받은 리스트의 첫 줄 부터 차근차근 값을 쌓아나가는 방식이었다. 만약에 직사각형의 아래 칸으로만 이동할 수 있고, 윗 행으로는 이동하지 못한다면 맞는 풀이었지만, 문제에서는 그런 조건이 없었기에 당연히 틀렸다. 반례 4 4 16 9 8 1 15 10 7 2 14 11 6 3 13 12 5 4 이 반례처럼 'ㄹ'자로 내려갔다 올라갔다를 반복할 수도 있는 것이다. 결국 검색을 통해 풀이 방법을 찾아보았다... DFS를 통해 길을 탐색하고, 여기에 DP를 이용해 시간을 단축시켜 푸는 문제였다. 예제..

외판원 순회 click 2주일 전에 외판원 순회2를 풀고(외판원 순회2가 더 쉬운 난이도의 문제이다.) 도전해 봤는데, 실패했었다. 이번에는 DP와 비트마스킹을 사용해 풀어야한다는 사실을 인지하고, 풀었고, 칠판에 적으면서 2시간 가량 푼 끝에 정답을 맞출 수 있었다. 비트연산자를 사용해서 사고하기가 아직은 수월하지 않다는 생각이 들었다. 관련 문제들을 수요일까지 4문제 정도 더 풀어볼 예정이다. 문제 분석 비트마스크를 사용해 푸는 문제이다. 비트연산자를 다루는데 아직 익숙하지 않다면, 11723-집합 문제를 먼저 풀어보는 것을 추천한다. 1부터 N까지 번호가 매겨져 있는 도시들을 모두 거쳐 다시 원래의 도시로 돌아오는 최소 비용을 구하는 문제이다. 도시간에 이동하는데 드는 비용은 대칭적이지 않으며, 0..

평범한 배낭 _ 시간복잡도 개선 click 포스팅 했던 평범한 배낭 문제를 시간 복잡도가 낮은 방법으로 다시 풀어 보았다. 3960ms는 기존 코드, 1508ms는 이번에 다시 푼 코드이다. 먼저 기존에 포스팅 했던 방식의 코드는 어떻게 작동하는지 되짚어 보자. dp 배열에 무게 별로 담을 수 있는 최대 가치를 저장한다. 초기 dp 값은 모두 0이다. w의 무게와 v의 가치를 가지는 물건이 있을 때, 0 부터 k(버틸 수 있는 무게)-w 까지의 i에 대해서 dp[w+i] = max(dp[i] + v, dp[w+i])를 통해 업데이트 해 나간다. 모든 물건에 대해 위와 같은 과정을 거치고, dp값들 중 최대값을 구하면 된다. 문제의 예제 입력에 대해서 배낭에 넣을 수 있는 물건들의 가치의 최대값을 구하는 ..

🧀치즈 click 이 문제도 두 달에 걸쳐 시도했지만, 풀지 못했던 문제였다. 두달여 만에 시도했더니 생각보다 수월하게 풀 수 있었다. 그새 실력이 성장한 것 같다. 앞으로도 꾸준히 풀어나가자! 문제 분석 문제를 풀면서 가장 고민이었던 부분 두 가지는, 내부 공기를 어떻게 처리해야 하는지와 치즈들을 어떻게 탐색해 나갈지 였다. 내부 공기 먼저, 내부 공기와 외부 공기를 다른 문자(혹은 숫자)로 표시한다. 녹을 치즈들에 대해 내부 공기와 동일한 문자로 변경해둔다. 한 사이클을 모두 돌고난 후에 녹은 치즈들을 시작으로 BFS탐색을 하며 외부 공기와 닿은 내부 공기도 모두 외부 공기로 변경한다. 치즈 탐색 치즈들을 모두 deque에 추가해둔 후에, 각 치즈들에 대해 탐색을 한다. 이때, 녹은 치즈면 deque..

벽 부수고 이동하기 click 두 달 동안 고통받았던 문제를 (힌트를 조금 얻긴 했지만)오늘 드디어 풀 수 있었다. 기본적인 컨셉은 이해하고 있었는데, 시간초과의 벽에 부딛혀 힘들어 했었다. 기본 BFS를 별 생각없이 너무 많이 풀다보니, 내 코드에 틀을 정해놓고 적용시키는 느낌이 든다. 유연한 사고를 방해하는 원인인 것 같다. 알파벳 문제도 그렇고 조금 더 높은 난이도의 문제를 풀며 응용력을 키워나가야 겠다. 문제 분석 맵에서 0은 이동할 수 있는 곳을 나타내고 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 다른 BFS문제와 다른 점은 벽을 한 번 부수고 이동할 수 있다는 것이다. 이때, 벽을 부쉈는지 혹은 부수지 않았는지에 상관 없이 최단거리로 도달하는 경우를 구해야 한다. BFS를 진행하며 현재 ..

알파벳 click 풀릴것 같으면서도 메모리 초과와 시간초과에 시달렸던 문제였다. BFS를 하면서 set자료구조를 사용할 생각을 한 번도 해본적이 없었는데, 이 문제에서 처음으로 set을 사용해서 풀었다. 탐색을 하면서 중복을 제거해 주는 부분이 정말 중요했다. 문제 분석 문제에 명시되어 있듯이, 새로 이동하는 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 하지만, 이 조건만 적용해 dfs를 수행하면 시간초과가 발생하게 된다. Code - 시간초과 발생 import sys from collections import deque read=sys.stdin.readline n,m = map(int,read().split()) board = list(list(read()...