한달꾸 한달꾸

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

컴퓨팅 사고로의 전환 4주차 주차별 키워드 - 동적 프로그래밍, 그리디 알고리즘 더 고민해볼 키워드 - 비트필드를 이용한 다이나믹 프로그래밍 풀어보자 문제를 설명하는 능력이 아주 부족하다는 생각은 하고 있었지만, 이번 기회에 다시 한번 느낄 수 있었다. 설명하는 연습도 꾸준히 해 나가도록 하자. 문제 정의 문제 해결 방안 구현 방법 SW사관학교 정글 WEEK04 시험 - 계단 오르기 click - 내리막길 click [포스팅] - 보석 도둑 click 보석 도둑💎 이번 주의 3번 문제였던 보석 도둑에 대해 알아보자. 도둑에게는 가방이 k개 있고, 각 가방에는 가방에 담을 수 있는 최대 무게보다 작거나 같은 보석을 1개씩 담을 수 있다. 이때, 훔칠 수 있는 보석 가격들의 합의 최대값을 구해야 한다. 단순..

Variable Scope 파이썬의 변수는 해당 변수가 선언된 범위 내의 범위에서만 유효하다. 이를 Scope라고 부른다. Local Scope, Enclosed Scope, Global Scope 그리고 Built-in Scope 이렇게 네가지 종류의 Scope가 있다. 각각의 Scope들은 아래와 같은 범위를 가진다. 각각의 Scope들에 대해 알아보자. Local Scope Local Scope는 현재 컴퓨터가 실행중인 함수의 Scope이다. 변수를 찾을 때, 가장 먼저 해당 변수가 Local Scope에 존재하는지 확인한다. locals()로 현재 local variable을 확인할 수 있다. x = 1 def func(): x = 2 print(locals()) func() 위의 코드를 실행하면..

파이프 옮기기 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..

컴퓨팅 사고로의 전환 3주 차 주차별 키워드 - 그래프 탐색 기본, BFS, DFS, DFS(위상정렬) 더 고민해볼 키워드 - 벨만 포드 알고리즘 - SPFA SW사관학교 정글 WEEK03 시험 - 단지 번호 붙이기 click - 숨바꼭질 click - 트리의 지름 click 트리의 지름 이번 주의 3번 문제였던 트리의 지름에 대해서 알아보자. Tree(사이클이 없는 무방향 그래프)의 지름을 구하는 문제이다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이때 양끝을 이루는 두 노드 사이의 거리를 트리의 지름이라고 한다. 트리의 지름을 어떻게 구할 수 있을까? 아래의 방법으로 트리의 지름을 찾을 수 있다. 트리 내의 임의의 점 A로부터 가장 먼 점 B를..

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