algorithm
-
[Python] 위상정렬algorithm/개념 2023. 6. 16. 19:49
🔎 위상 정렬 이란? 사이클이 없는 방향 그래프 (DAG) 의 방향에 맞게 모든 노드를 순서대로 나열하는 것 진입 차수 : 특정한 노드로 들어오는 edge 의 수 진출 차수 : 특정한 노드에서 나가는 edge 의 수 작동 순서 1. 진입 차수가 0인 모든 노드를 큐에 넣는다. 2. 큐가 빌 때 까지 다음을 반복한다 큐에 우너소를 꺼내 해당 노드에서 나가는 간선 제거 새롭게 진입 차수가 0이 된 노드를 큐에 삽입 큐에 들어온 순서 = 위상 정렬 결과 📋 example) 📜 code from collections import deque # 노드의 개수와 간선의 개수를 입력 받기 v, e = map(int, input().split()) # 모든 노드에 대한 진입차수는 0으로 초기화 indegree = [0]..
-
[Python] 크루스칼 알고리즘 / MST / 최소 신장 트리algorithm/개념 2023. 6. 16. 18:47
🔎 크루스칼 알고리즘이란? 대표적인 최소 신장 트리 알고리즘이다. 그리디 알고리즘으로 분류된다. 신장트리란? 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프이다. 최소신장트리란? 하나의 그래프에서 많은 신장트리 중에 최소한의 비용으로 구성된 신장트리이다. 동작 과정 1. 간선 데이터를 비용에 따라 오름차순 정렬 2. 간선을 하나씩 확인하면서 현재의 간선이 사이클을 발생시키는지 확인 사이클 발생 O > 최소 신장 트리에 포함 X 사이클 발생 X > 최소 신장 트리에 포함 O 3. 모든 간선에 대하여 2를 반복 cost 가 낮은 edge 부터 차례대로 사이클이 발생하는지 확인합니다. 이때 union-find 가 활용되는데 아래 게시물을 참고해주세요. 2023.06.16 - [algori..
-
[Python] 백준 1717번/집합의 표현/유니온파인드 Union Findalgorithm/문제 2023. 6. 16. 17:55
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net ⚡️ 문제 설명 전형적인 Union Find 문제! union find 개념을 안다면 바로 풀 수 있는 문제다. 2023.06.16 - [algorithm/개념] - [Python] Union - Find 유니온 파인드/서로소 집합 [Python] Union - Find 유니온 파인드/서로소 집합 🔎 Union Find (서로소 집합) 란? 서로소 부분 집합들..
-
[Python] Union - Find 유니온 파인드/서로소 집합algorithm/개념 2023. 6. 16. 17:32
🔎 Union Find (서로소 집합) 란? 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 1. 합집합 (Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 Union (A,B) : A와 B를 하나의 집합으로 합치는 연산 1) A와 Bdml 루트 노트 A', B' 를 각각 찾는다. 2) A'를 B'의 부모 노드로 설정 모든 합집합 연산을 찾을 때까지 위 과정을 반복한다. 2. 찾기 (Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 📋 example) Union(1,4) Union(2,3) Union(2,4) Union(5,6) 을 해보자 - 유니온 파인드는 루트 노드에 즉시 접근할 수 없고 부모 테이블을 계속 확인해서 거슬러 올라가야 ..
-
[Python]프로그래머스/베스트앨범/해시algorithm/문제 2023. 5. 26. 21:07
https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ⚡️ 문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는..
-
[Python]프로그래머스 N으로 표현/dpalgorithm/문제 2023. 4. 28. 14:39
https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ⚡️ 문제 설명 ⚡️ 해결 방법 5를 1번 사용해서 만들 수 있는 수 set {5} 5를 2번 사용해서 만들 수 있는 수 set {0, 1, 10, 55, 25} 5를 3번 사용해서 만들 수 있는 수 set = 5를 2번 사용해서 만들 수 있는 수 set 과 5를 1번 사용해서 만들 수 있는 수 set 의 사칙연산 한 set {0, 2, 4, 5, 6, 555, -20, -4, -50, 15, 1..
-
[Python]백준 9663번/N-Queen/백트래킹algorithm/문제 2023. 3. 31. 16:02
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ⚡️ 문제 설명 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제 퀸을 놓는 방법의 수를 구하는 프로그램 ⚡️ 해결 방법 퀸이 서로 공격할 수 없도록 하는 방법 1. 같은 행에 위치하면 안됨 2. 같은 열에 위치하면 안됨 3. 대각선상에 위치하면 안됨 graph_col 은 X행에서 퀸이 놓인 열의 위치를 저장할 것이다. queen을 놓은 뒤 이 queen의 자리가 p..
-
[자료구조] 우선순위 큐와 힙 / 최소 힙 / 최대 힙 / heap /algorithm/개념 2023. 3. 31. 00:21
우선순위 큐 Queue 자료구조는 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 구조로 저장 우선순위큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터 먼저 나온다. 힙 (Heap) 이란? Heap은 우선순위큐(priority queue)의 구현과 일치 Heap은 완전이진트리 구조 최소 힙 : 각 node에 저장된 값은 child node들에 저장된 값보다 작거나 같다 최대 힙 : 각 node에 저장된 값은 child node들에 저장된 값보다 크거나 같다 파이썬 힙 함수 heapq.heappush(heap, item) : item을 heap에 추가 heapq.heappop(heap) : heap에서 가장 작은 원소를 pop + 리..