유니온 파인드 알고리즘의 응용문제이다.가장 먼저 든 생각은 전체 네트워크에 몇명이 존재하는지 어떻게 구해야 하는지에 대해서였다.그런데 잘 생각해보니 유니온 파인드 알고리즘에서 find 함수는 항상 노드의 가장 위쪽 부모노드를 찾아주기 때문에 그냥 하나의 dict를 더

풀이 과정 배낭 문제인데 중복해서 물건이 여러개가 있을 수 있는 경우이다. 맨처음에는 재귀를 사용해서 구현하는데 재귀함수에 매개변수를 3개(무게, 만족도, 개수)를 넣어주면 되지 않을까..? 라고 생각을 했다. 그러나 이렇게 구현하는 경우 dp 배열을 3차원으로 해야

위상정렬을 사용해서 푸는 문제이다.주의해야 할 점은 각 노드에서 우선순위가 있기 때문에 일반 큐가 아닌 우선순위 큐를 사용하여 구현해야한다.우선순위 큐를 사용한다는 아이디어만 생각해내면 정말 편하게 풀 수 있는 문제 !문제집 문제 출처GitHub 코드

문제가 숫자의 합 중에 최대를 구하는 문제였다면 훨씬 쉽게 풀었을 것이다. 그러나 이 문제에서 중요한 점은 숫자의 합 중 최대값을 나타내는 경로의 수를 구하는 것이다.이것을 해결하는데 시간이 많이 들었다.일단 최대값을 나타내는 경로를 구하기 위해서는 먼저 최대값을 구하

S 지점에서 A,B 지점까지 도착하는데 소요되는 최소 비용을 구하는 문제이다.처음에는 문제를 대충읽고 S->A->B로 가는 비용과 S->B->A로 가는 비용만 비교하면 되는줄 알았는데, 그게 아니라 S에서 출발해서 따로 따로 A, B로 가는데 경로가 중복되는 부분이 있

모든 도시 쌍에 대하여 필요한 최소 비용을 구하는 문제이므로 플로이드-워셜 알고리즘을 사용하면 된다.어차피 모든 경우에 대해 필요한 최소 비용을 구해야하기 때문에 graph를 따로 두지 않고, 처음부터 distance 배열에 거리를 저장하는 방식으로 구현하였다.플로이드

이전에 풀었던 타임머신 문제와 유사하게 벨만-포드 알고리즘을 사용하면 간단하게 해결할 수 있는 문제이다.단, 주의할 점은 이 문제는 시작지점이 주어지지 않고, 단순히 음의 순환이 있는지 없는지를 판별하는 문제이므로 거리 배열을 초기화 해줄때 INF(무한대)로 초기화를

다익스트라 알고리즘은 간선의 가중치가 양수인 경우만 해결할 수 있는 반면 벨만-포드 알고리즘은 가중치가 음수인 경우도 고려한 알고리즘이다.해당 문제는 가중치가 음수인 경우도 나오기 때문에 다익스트라 알고리즘이 아닌 벨만-포드 알고리즘을 사용해야한다.벨만-포드 알고리즘에

풀이 과정 다익스트라 알고리즘을 사용하여 구현하면 된다. 처음에는 힙큐에 데이터를 넣어줄때 (정점, 비용) 순서로 넣어주는게 자연스러울것 같아서 파이썬의 클래스와 스페셜 메소드 lt를 사용하여 힙큐의 우선순위를 커스텀 하는 방식으로 구현하였다. 코드는 다음과 같다.

쿼리에 들어온 문자열에 따라 해당되는 지원자의 숫자의 배열을 결과로 반환해주면 된다.지원자들의 조건은 언어, 직군, 경력, 소울푸드, 코테점수로 나뉜다.

처음에는 그냥 보자마자 python에 내장되어있는 replace 함수를 사용하면 간단하게 해결이 가능하겠다는 생각이 들었다.replace를 적용한 문자열과 이전 상태의 문자열의 상태를 비교하여 같을 때까지 반복을 돌려주고, 남은 문자열이 없다면 "FRULA"를 있다면

course에 따라 가장 인기있는 단품메뉴의 조합을 만들어야한다. course가 2인 경우에는 orders에서 길이가 2인 단품메뉴의 조합중 가장 많은 선택을 받은 조합을 찾고, course가 3인 경우에는 길이가 3인 단품메뉴의 조합중 가장 많은 선택을

게임판의 빈칸 중 왼쪽 위 부분부터 탐색해서 그 부분을 채우고, 그 다음 게임판의 빈칸을 찾아서 채워가는 방식으로 구현을 하였습니다.이때 중요한것은 중복을 없애는 것인데 게임판의 빈칸중 왼쪽 위 부분부터 아래방향으로 계속해서 채워나갈것이기 때문에 검색한 부분의 왼쪽과

가능한 모든 조합을 만드는 완전탐색을 이용해서 코드를 작성하였습니다.여기서 중요한것은 중복을 피하는것인데 (0,1)과 (1,0)같이 중복된 경우가 세지면 안되기 때문에 먼저 현재 짝이 지어지지 않은 학생중 번호가 가장 작은 학생을 찾고, 그 학생의 짝을 찾는 방식으로