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

특정한 정점들을 반드시 포함하는 최소 정점 트리 만들기 - 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
코딩테스트를 위한 스택과 큐 기본 이론

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

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

  • format_list_bulleted 알고리즘/알고리즘 일반
  • · 2022. 6. 29.
  • textsms
DFS/BFS 완전 정복하기 - 트리구조를 탐색하는 방법

DFS/BFS 완전 정복하기 - 트리구조를 탐색하는 방법

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return하도록 solution함수를 완성하세요 2. 제한사항 모든 공항은 알파벳 대문자 3글자 주어진 공항 수는 3개..

  • format_list_bulleted 알고리즘/DFS BFS 정복기
  • · 2022. 6. 24.
  • textsms
순서 찾기 알고리즘 문제

순서 찾기 알고리즘 문제

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크> 라이트닝볼트> 썬더 일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크>힐링> 라이트닝볼트> 썬더와 같은 스킬트리는 가능하지만 썬더>스파크나 라이트닝볼트>스파크>힐링>썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skil..

  • format_list_bulleted 알고리즘/알고리즘 일반
  • · 2022. 1. 18.
  • textsms
코딩테스트에서 유용한 Counter와 deque

코딩테스트에서 유용한 Counter와 deque

1. Counter 시퀀스 타입 데이터의 원소 개수를 dict형으로 반환해주는 아주 유용한 함수 from collections import Counter로 불러온다 집합 연산도 가능함 근데 큰 의미가 있을까? 리스트 내에서 개별 원소들의 빈도수를 세는 것에는 분명히 의미 있다 2. deque 스택과 큐를 동시에 구현한 자료형 from collections import deque로 불러온다 append, extend, pop 등을 모두 지원하는데 list가 $O(n)$이라면 deque는 $O(1)$이라는 점에서 유용하다 append로 오른쪽에 데이터를 넣어주고 appendleft로 왼쪽에 데이터를 넣어준다 extend로 오른쪽에 리스트 데이터를 넣어주고 extendleft로 왼쪽에 리스트 데이터를 넣어준다..

  • format_list_bulleted 프로그래밍/Python
  • · 2022. 1. 12.
  • textsms
deque를 사용해야할때는?

deque를 사용해야할때는?

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어 사람들의 몸무게가 [70,50,80,50]이고 구명보트의 무게 제한이 100kg이면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합..

  • format_list_bulleted 알고리즘/알고리즘 일반
  • · 2021. 11. 8.
  • textsms