Algorithm
벨만-포드 알고리즘 이해하기 ([백준] 11657번 타임머신)
벨만-포드 알고리즘 이해하기 ([백준] 11657번 타임머신)
2022.09.29벨만-포드 알고리즘이란? 벨만-포드 알고리즘은, 한 노드에서 다른 노드까지의 거리를 구하는 알고리즘이다. 다익스트라 알고리즘이 모든 비용(가중치)가 양수인 경우에만 사용할 수 있는 반면에 벨만-포드 알고리즘은 노드 간의 간선 비용(가중치)가 음수인 경우에도 사용할 수 있다. 다만, 시간 복잡도는 벨만-포드가 더 크기 때문에 비용(가중치)가 모두 양수라면 굳이 벨만-포드를 사용할 필요는 없다. 음수 사이클이 문제가 되는 이유 단순 음수 간선일 경우 : 단순 경로이므로 그대로 비용을 계산. 사이클이 존재하나 양수값이 더 클 경우 : 사이클을 순환하여도 이득이 없으므로 그대로 진행. 사이클이 존재하고 음수값이 더 클 경우 : 사이클을 순환할 수록 비용이 감소해 최소 비용을 찾는 입장에서 사이클을 무한히 순환하..
[이코테] Chapter7-3 / 떡볶이 떡 만들기
[이코테] Chapter7-3 / 떡볶이 떡 만들기
2022.03.20오늘 민교는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 민교네 떡볶이 떡은 재밋게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm 가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻..
[이코테] Chapter7-2 / 부품 찾기
[이코테] Chapter7-2 / 부품 찾기
2022.03.19민교네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 민교는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N = 5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M = 3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를 , 없으면 no를 출력한다. 구분은 공백으로 한다. [입력 조건] 첫째 줄에 정수..
[이코테] Chapter7-1 / 범위를 반씩 좁혀가는 탐색
[이코테] Chapter7-1 / 범위를 반씩 좁혀가는 탐색
2022.03.18순차 탐색 이번 장에서는 리스트 내에서 데이터를 매우 빠르게 탐색하는 이진 탐색 알고리즘에 대해서 공부하겠다. 이진 탐색에 대해 알아보기 전에 가장 기본적인 탐색 방법인 순차 탐색에 대해 먼저 이해할 필요가 있다. 1장부터 차례대로 읽은 독자라면 이미 자연스럽게 순차 탐색의 원리를 익혔다. 사실 지금까지 예제 문제에서 N개의 데이터가 있을 때, 그 데이터를 차례대로 하나씩 확인하여 어떠한 처리를 해준 경우가 많았는데 그 자체로도 이미 순차 탐색이라고 할 수 있다. 예를 들어 3장의 '거스름돈'문제에서 가장 큰 화폐단위부터 확인(탐색)해서 각 단위에 대하여 처리한 것을 기억해보자. 이와 같이 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하..
[이코테] Chapter6-4 / 두 배열의 원소 교체
[이코테] Chapter6-4 / 두 배열의 원소 교체
2022.03.12민교는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 민교는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 민교의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 민교를 도와야 한다. N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오. 예를 들어 N = 5, K = 3 이고, 배열 A와 B가 다음과 같다고 하자. 배열 A = {1, 2, 5, 4, 3} 배열 b =..
[이코테] Chapter6-3 / 성적이 낮은 순서로 학생 출력하기
[이코테] Chapter6-3 / 성적이 낮은 순서로 학생 출력하기
2022.03.11N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학새의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오. [입력 조건] 첫 번째 줄에 학생의 수 N이 입력된다. (1