Unity 기본6 - C#의 컬렉션 List, Dictionary

1. 컬렉션 하나의 이름으로 여러개의 데이터를 묶어서 관리하는 것 배열과 비슷한데, 크기가 정해져 있지 않다 실시간으로 크기를 변화시킬 수 있다 배열은 다음과 같이 중간에 어디를 제거하면, 나머지 원소들은 그대로 있다 컬렉션은 중간에 원소를 지우면 뒤에 있는 원소가 앞으로 온다 컬렉션에 해당하는 자료구조는.. Dictionary, List, Queue, SortedList, Stack, ArrayList, Hashtable, ... 2. List List는 배열에 컬렉션으로서의 특징을 더한 형태 배열과는 다르게 개수가 정해져있지 않은 데이터의 목록을 저장하기에 적절 ArrayList와 비슷한데, ArrayList는 저장할 데이터의 타입이 고정이 안된다. List는 어떤 타입의 데이터를 저장할지 미리 지정..

• format_list_bulleted Unity&C#
• · 2024. 4. 20.
• textsms

Python dict indexing보다는 list indexing을 사용해야하는 이유

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..

• format_list_bulleted 알고리즘 일반
• · 2024. 4. 12.
• textsms

ABC 344 E번 복기 - 원소에 바로 접근할 수 있는 연결리스트 구현하는 법

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)이라서.. 분명..

• format_list_bulleted 연결리스트
• · 2024. 3. 14.
• textsms

ABC 335 C번 복기 - 놓치기 쉬운 deque를 사용할 때 주의할 점(deque indexing is 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번까지 좌표가 있는데, ..

• format_list_bulleted Atcoder
• · 2024. 1. 7.
• textsms

트리 필수 테크닉3 - 모든 정점들 각각 가장 먼 거리를 2번의 DFS로 구하는 방법

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

• format_list_bulleted DFS BFS 정복기
• · 2023. 12. 21.
• textsms

ABC 333 D번 복기 - 리프 노드부터 특정 노드까지 최소로 지우는 법

1. 문제 D - Erase Leaves (atcoder.jp) D - Erase Leaves AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 리프 노드부터 차례대로 지울 수 있을때, 1번 노드를 지우기 위해서 최소로 지워야하는 노드의 개수는 몇개인가? 평소에 골드3정도 트리 DP 문제를 연습했더니.. 해법이 보이긴 하더라 리프 노드라는 것은 자식이 없는 노드인데, 목표로 하는 노드가 1번 노드니까, 1번 노드를 루트라고 생각한다면.. 다음과 같은 트리는 다음과 같이 바꿀 수 있는데, 이런 경우에 리프 노드부터..

• format_list_bulleted Atcoder
• · 2023. 12. 17.
• textsms