결국 빛나리라

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 사이클 판별 서로소 집합 알고리즘을 무방향 그래프 내에서 사이클이 발생하는지(서로 연결되어 순환할 수 있는 구조인지) 판별하는데 사용할 수 있다. ▶ 작동 과정 step 1. 각 간선을 확인하며 루트노드를 보았을 때 루트 노드가 같다면 사이클이 발생한 것이고, 같지 않으면 두 노드에 대한 union연산을 수행한다. step 2. 모든 간선에 대해 step1을 반복한다. ▷ 예시 아래와 같은 그래프가 있다고 해보자. 1,2,3 노드에서 사이클이 발생하고 있으므로 사이클이 존재하는 그래프이다. 작동 과정을 경로 ..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 경로압축기법을 사용한 서로소 집합 알고리즘 특정 원소의 루트노드를 찾기 위해 경로 압축 기법을 사용하여 효율적으로 문제를 해결할 수 있다. 이전 방식에서 루트 노드를 구하는 함수에선 부모노드 테이블의 원소가 루트 노드가 아닌 바로 위에 존재하는 부모노드의 루트노드로 설정하였지만 경로압축기법을 사용하면 부모노드 테이블의 원소를 해당 원소의 루트노드로 바로 갱신시켜줄 수 있다. 즉 경로압축기법을 사용하면 이전 포스팅의 예시에서 다뤘던 결과 테이블이 다음과 같은 형태로 바뀐다. 해당 방법을 사용하면 계속해서 루트노..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 서로소 집합이란 공통원소가 없는 두 집합을 의미한다. 서로소 집합은 서로소 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 자료구조로, 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 Union, 특정 원소가 속한 집합은 어느 집합인지 알려주는 Find 연산을 수행할 수 있다. ▶ 트리자료구조를 이용한 서로소 집합 계산 알고리즘 step 1. 서로 연결된 두 노드 A,B를 확인한다. 두 노드의 루트 노드 A'과 B'을 찾는다. step 2. 일반적으로 두 루트 노드 중 더 번호가 작은 원소의 부모노..

https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr > 완전탐색 yellow의 약수가 될 수 있는 경우의 수 중 조건문을 만족하는 수가 있으면 해당 수들을 반환하는 함수로 작성하였다. 결과를 도출하기까지 다음 세가지 조건을 걸었다. 1) yellow의 약수가 되는 조건- yellow이하의 수 중 yellow의 약수가 되는 수가 있으면 그 수와 함께 짝을 이루는(곱했을 때 yellow가 나오는) 수를 j로 지정..

https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr > 그리디알고리즘 활용 최소값에서부터 시작해서 반복문을 돌리며 end값과 최소값과 더했을 때 limit을 넘어가는지 안넘어가는 지를 그때그때마다 체크해서 limit을 안넘어가게 될 때 최소값을 올려줘서 계속 탐색함 -> 현재 주어진 상황에서 가장 좋은것만 고르는 그리디 알고리즘 활용 def solution(people, limit): ..

https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr > 힙활용 힙을 활용해서 scoville에서 최소값을 뽑아 계산을 수행하도록 했다. https://docs.python.org/3/library/heapq.html heapq — Heap queue algorithm — Python 3.9.6 documentation heapq — Heap queue algorithm Source code: Lib/..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 플로이드 워셜 알고리즘이란? 모든 노드에서 다른 모든 노드까지의 최단경로를 계산하는 알고리즘으로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 2차원 테이블에 최단거리 정보를 저장하고 점화식에 따라 거리 정보를 갱신하는 원리로 다이나믹 프로그래밍 유형에 속한다. 점화식은 각 단계 즉 k의 노드를 점검할 때마다 a에서 b로 가는 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧을 때 해당 값으로 거리정보를 갱신하는 원리를 사용한다. 따라서 점화식은 다음과 같다. Dab= min(Dab, Dak+ Dk..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 힙이란? 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 최소 힙은 가장 작은 우선순위부터 꺼내는 방식이고 최대 힙은 값이 높은 데이터부터 꺼내는 방식이다. 리스트를 사용하는 경우 삽입시간은 O(1), 삭제는 O(N)시간이 걸리는 반면 힙을 사용하는 경우 삽입하고 삭제하는데 O(logN)만큼의 시간을 보장한다. ▷구현 >최소힙 구현 > 최대힙 구현 ▶ 힙을 활용한 다익스트라 알고리즘 힙을 사용하여 개선된 다익스트라 알고리즘을 구현할 수 있다. 알고리즘이 동작하는 원리는 이전 포스팅에서 기록한 ..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 최단경로 알고리즘이란? 최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘으로 한 지점에서 다른 지점, 모든 지점에서 다른 모든 지점까지의 최단 경로 등을 구하는 등 여러 유형의 문제가 있다. 각 지점은 노드로 표현되고 지점 간 연결된 선은 간선으로 표현한다. ▶ 다익스트라 최단 경로 알고리즘이란 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 계산한다. 현실세계의 간선은 음의 부호를 가진 간선으로 표현되지 않기 때문에 이러한 음의 간선이 없을 때 정상적으로 작동한다. 해당 알고리즘은 매 상황에서 가..

https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr > 큐 활용 from collections import deque def solution(priorities, location): loc=[x for x in range(len(priorities))] lst= deque(list(zip(priorities, loc))) answer= 0 while True: # 리스트의 튜플에서 첫번째 요소(priorities)의..