특정한 정점들을 반드시 포함하는 최소 정점 트리 만들기 - list말고 반드시 set을 사용해야하는 경우

https://atcoder.jp/contests/abc368/tasks/abc368_d D - Minimum Steiner TreeAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  1부터 n까지 번호를 가진 정점을 가진 트리에서 어떤 정점들을 제거할때, 특정한 정점 v1,v2,...,vk를 반드시 포함하게 하는 트리를 만들고 싶다면, 그러한 트리의 최소 정점 수는? 예를 들어 왼쪽 트리에서 1,3,5를 반드시 포함하는 트리를 만들고 싶을때, 4번, 6번, 7번을 제거하면 된다     사실 테크닉에 감탄해서 복기하는거긴 한..

• format_list_bulleted 알고리즘/애드 혹 알고리즘
• · 2024. 8. 31.
• textsms

Unity 기본7 - foreach, 연습문제 풀기

1. foreach 배열이나 컬렉션에서 모든 원소 각각을 한번씩 꺼내서 쭉 써보겠다는 의미의 반복문 foreach ((데이터타입) (변수명) in (컬렉션명)){반복 실행할 명령} 1) 배열 using System.Collections; using System.Collections.Generic; using UnityEngine; public class HelloWorld : MonoBehaviour { // Start is called before the first frame update void Start() { int[] a = { 2, 4, 6, 8, 10 }; foreach (int number in a) { Debug.Log(number); } } // Update is called once ..

• format_list_bulleted 프로그래밍/Unity&C#
• · 2024. 4. 21.
• textsms

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

알고리즘 문제를 풀기위해 2차원 배열에서 이해해야할 테크닉들

1. 2차원 배열 선언 1-1) 일반적으로 [ [0,1,2,3], [1,2,3,4] ] 과 같이 [0,1,2,3], [1,2,3,4]는 각각 행을 나타내고 (0,1), (1,2), (2,3), (3,4)는 각각 열을 나타냄 세로의 길이(행의 개수), 가로의 길이(열의 개수)를 필요로 한다 1-2) 입력을 받을때 1 2 3 4 5 6 7 8 9 는 '1 2 3'을 리스트로 바꿀려면, input().split() 123 456 789 는 '123'을 리스트로 바꿀려면 list(input()) 2. 2차원 배열 순회하기 2-1) 행 우선 순회 2차원 배열 각 칸의 좌표를 (x,y)라고 하면, arr[y][x]로 접근할 수 있다 n*m 배열에서 for y in range(n): for x in range(m):..

• format_list_bulleted 알고리즘/알고리즘 일반
• · 2022. 9. 11.
• textsms

코딩테스트를 위한 스택과 큐 기본 이론

1. 탐색(search) 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 코딩테스트를 통과하기 위해 그래프, 트리 등의 자료구조 안에서 탐색을 할줄 알아야한다 이를 위한 대표적인 탐색 알고리즘이 바로 DFS/BFS 2. 자료구조 데이터를 표현하고 관리하고 처리하기 위한 구조 스택(stack)과 큐(queue)는 자료구조의 기초 개념 3. 스택과 큐에서 고려해야할 부분 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성 삽입(push): 데이터를 삽입한다 삭제(pop): 데이터를 삭제한다 실제 스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로우와 언더플로우도 고민해야함 오버플로우(overflow): 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산..

• format_list_bulleted 알고리즘/알고리즘 일반
• · 2022. 6. 29.
• textsms