문제 길 찾기 게임 접근 문제를 최대한 꼼꼼히 읽고, 정확히 이해하는게 얼마나 중요한지 알게된 문제이다. 전위, 후위 순회는 쉽지만, 주어진 정보들로 어떻게 트리를 만드느냐가 관건이다. 문제를 다풀고 찾아보니 굉장히 간결하게 트리를 만들어내는 고수분들이 정말 많은 것 같다.. 나는 그냥 정석대로 만들었다. 루트 노드를 붙이고, 크기를...

문제 징검다리 건너기 접근 그냥 풀었다가 시간초과가 났다. 1명씩 건너보는 방법으로는 제시간에 풀 수 없다. 특정 x명이 건널 수 있는지 없는지 판단하는 것에 O(n)의 시간이 걸린다. 그럼 x를 조절하면서 건널 수 있는 최대값을 찾는 문제가 되는데, 이는 이분 탐색을 이용하면 건널 수 있는 최대 x를 찾는 시간은 O(logn)의 시간이 ...

문제 보석 쇼핑 접근 처음에 방향을 잘못 잡아서 조금 돌아갔다. 시작과 끝쪽에 포인터를 하나씩 두고 이동한다면 O(n) 안에 탐색할 수 있는 것 같다. 투포인터 알고리즘이라고 한다. 우선 시작점 s와 끝점 e를 모두 0에 둔다. e를 하나씩 옮기며 해당 점에 있는 보석을 담아준다. 모든 종류의 보석이 담기면 이제 s을 하나씩 이동하며 해...

문제 숫자 게임 접근 두 배열을 정렬해놓고 문제를 풀면 쉬워진다. 현재 배열에서 가장 큰 값끼리 비교를 하고, B가 더 크다면 두 최대값을 없애고 승점을 1점 올린다. 만약 작다면, B의 최대값은 승리를 위해 아껴두고, 최소값을 이용해서 패배한다고 생각하면 된다. 실제 구현에서 최소값을 사용하여 패배할 필요는 없다. 어떤 경우든 A의 최대...

문제 베스트앨범 접근 해시 문제이다. 우선 장르별 재생횟수를 통합해주는 딕셔너리 gen_cnt를 만들자. gen_cnt는 각 장르 이름을 key로 가지며, 재생횟수를 value로 가진다. 재생횟수로 정렬해서 어떤 장르를 먼저 뽑을지 만들어놓는다. gen_rank에 정렬된 딕셔너리가 담기며, 이제 이를 바탕으로 각 장르별로 노래와 트랙을 ...

문제 정수 삼각형 접근 동적계획법이라면 동적계획법인 문제이다. 꼭대기에서 시작해서 아래로 내려가면서 현재 위치에서 가장 큰값을 찾으면된다. 좌,우 끝부분은 자기자신에 바로 위를 더하면 되고, 중앙에 위치한 부분들은 자기와 연결된 위에 둘 중 큰값을 더해주면 된다. 코드 파이썬 코드 def solution(triangle):...

문제 네트워크 접근 간단한 BFS 문제이다. 코드 파이썬 코드 def solution(n, computers): visit = [0] * n answer = 0 for i in range(n): if visit[i] == 0: visit[i] = 1 ...

문제 풍선 터트리기 접근 최초 접근 방법은 최후까지 남는지 확인할 풍선이 i 번째 풍선이라면, i 번째를 기준으로 좌,우로 나누어 확인하고자 했다. 왼쪽에서 최소값과 오른쪽에서 최소값을 구했을 때, i번째의 값이 이 3개의 값 중 가장 크다면, 무슨 수를 써도 살아남을 수 없다. 번호가 더 작은 풍선은 한번만 터트릴 수 있기 때문! 또한...

강의 시계열 데이터(Time series data) 특징들이 순서를 가지기 때문에, 단순히 공간적인 측면이외에도, 순서에 따른 특징이 중요함 시계열 데이터는 보통 동적이며 길이가 가변적임 $$RNN(Recurrent neural networks) RNN은 시계열 정보를 처리하는데 효과적인 학습 모델이다. 매우 긴 시계열 데이터를 처리할 때는,...

Contents 병행성(Concurrency) \(\rhd\)경쟁 상태(Race Condition) \(\rhd\)임계 자원(Critical Resource)과 임계 영역(Critical Section) \(\rhd\)상호 배제(Mutual exclusion) \(\rhd\)상호 배제 기법 ...