결국 빛나리라

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

▶ 코사인 유사도란? 우리는 벡터 간 유사도를 측정함으로써 두 벡터가 얼마나 비슷한지를 알 수 있다. 그 유사도를 측정하는 방법 중 하나가 코사인 유사도이다. 벡터가 "유사하다"는 것은 두 벡터의 길이와 방향이 비슷한 방향과 길이를 가진다는 의미이다. 코사인 유사도는 두 벡터의 방향, 즉 각도에 기초해서 유사도를 측정한다. 다음과 같은 좌표들을 가진 세 벡터가 있다고 해보자. 그림을 보면 A벡터와 B벡터가 A와 C벡터는 유사할 것으로 보인다. 코사인 유사도로 측정하였을 때에도 우리의 추측과 일치하는지 알아보자. ▶ 코사인 유사도 공식 이때 각도 theta, 즉 v1과 v2 사이의 각도가 0에서 90도 사이이면 코사인 값이 +값이 나오고 90에서 180도 사이로 둔각이면 -값이 나온다. 따라서 코사인 유사..

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

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 다이나믹 프로그래밍이란? 메모리를 적절히 사용하여 수행시간의 효율성을 향상시키는 방법이다. 즉 한번 계산된 결과는 별도 메모리 영역에 저장해 다시 계산하지 않도록한다. 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용한다. 1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있어 작은 문제를 모아 큰 문제를 해결할 수 있을 때 2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결할 때 현재 주어진 문제가 다이나믹 프로그래밍 유형인지 아닌지 고민하여 파악한느 것이 중요하다. 문제를 보고 위의 조건들..

▶ 입국심사 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr > 이진탐색 활용 나와있는 문제보다 더 쉬운 예제를 들어보자. time= [2,3] n= 3이라고 해보자 이때 탐색가능한 범위로는 3분에 3을 곱한 9분이 된다. [1,2,3,4,5,6,7,8,9] - left=1, right= 9, mid= 5이다. 5이하의 수 중 2와 3의 배수로는 3개가 있다. 즉 5분이면 3명의 입국심사를 마칠 수 있다. 그러..