python에서는 trie가 class로 구현된 경우가 많아 꺼렸는데... 배열로 구현하는 법을 익혀서 기록해보기 https://deepdata.tistory.com/659 문자열 자료구조 Trie 알고리즘 기본기 배우기1. 문자열 단어 저장 'hello', 'hi', 'hey' 등을 저장하고자 할때, 생각할 수 있는 방법중 하나는 dictionary에 저장하는 것이다 d = {'hello':1, 'hi':1, 'hey':1} 단어를 key값으로 저장해두면, 특정 단어를 찾고자deepdata.tistory.com https://blog.encrypted.gg/1059 [실전 알고리즘] 0x1F강 - 트라이안녕하세요, 드디어 마지막 강이라니 가슴이 웅장해집니다. 마지막인만큼 난이도도 끝판왕일 수 있지만 개..
1. 컬렉션 하나의 이름으로 여러개의 데이터를 묶어서 관리하는 것 배열과 비슷한데, 크기가 정해져 있지 않다 실시간으로 크기를 변화시킬 수 있다 배열은 다음과 같이 중간에 어디를 제거하면, 나머지 원소들은 그대로 있다 컬렉션은 중간에 원소를 지우면 뒤에 있는 원소가 앞으로 온다 컬렉션에 해당하는 자료구조는.. Dictionary, List, Queue, SortedList, Stack, ArrayList, Hashtable, ... 2. List List는 배열에 컬렉션으로서의 특징을 더한 형태 배열과는 다르게 개수가 정해져있지 않은 데이터의 목록을 저장하기에 적절 ArrayList와 비슷한데, ArrayList는 저장할 데이터의 타입이 고정이 안된다. List는 어떤 타입의 데이터를 저장할지 미리 지정..
dict에서 key에 접근하는 시간과 list에서 index로 접근하는 시간은 O(1)인데, dict의 경우 hash로 구현되어 있어서 key,value가 많은 경우 hash collision으로 인해 list indexing보다 시간이 더 걸릴 수 있다. 만약 시간초과 판정을 받는다면 dict indexing을 list indexing으로 바꿀 수 있는지 체크해보자. https://deepdata.tistory.com/960 문자열 해싱(hashing) 기본 개념 배우기 String Hashing - Algorithms for Competitive Programming (cp-algorithms.com) String Hashing - Algorithms for Competitive Programming..
E - Insert or Erase (atcoder.jp) E - Insert or Erase AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 수열 A의 원소들이 모두 서로 다른 원소이며, 삽입하는 연산과 삭제하는 연산을 수행한다. 연산을 수행할 때마다 A의 원소들은 모두 서로 다르다는 것이 보장된다. 연산은 2가지이다. x 원소 바로 뒤에 y를 삽입하는 연산 x를 삭제하는 연산 연결리스트로 접근해야지 생각하긴 했는데... x를 어떻게 바로 찾아야 하나 고민하다가 실패했다.. 연결리스트는 접근하는데 O(N)이라서.. 분명..
1. 문제 C - Loong Tracking (atcoder.jp) C - Loong Tracking AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 1번부터 N번까지 좌표가 있고, 1번 좌표는 쿼리에 의해 움직이게 된다. 1번 좌표가 움직이면, 2번,3번,4번,...,N번 좌표는 각각 1번,2번,3번,...,N-1번 좌표가 된다. 쿼리가 20만개이고 좌표수도 최대 100만개라 단순하게 접근하면 시간초과를 받을 것인데 그림으로 생각해보면 접근법을 생각할 수 있다 처음에 배열에 1번부터 N번까지 좌표가 있는데, ..
1. 문제 11429번: Tree (acmicpc.net) 11429번: Tree The input file contains the description of the tree. The first line of the input file contains one integer N, 2
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
