새벽 기상을 꿈꾸는 루민

이번 포스팅에서는 최소 스패닝 트리 문제를 풀어보겠습니다. 1. 문제 2. 예제 3. 문제 풀이 이번 문제는 최소 스패닝 트리를 구하면 되는 문제이다. 위의 그림처럼 가중치 C가 최소인 값으로 구성된 트리를 구하면 되는데 이 또한 기존에 풀었던 union-find 알고리즘을 그대로 사용하면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.StringTokenizer; import jav..

이번 포스팅에서는 도시 분할 계획 문제를 풀어보겠습니다. 1. 문제 2. 입출력 및 예제 3. 문제 풀이 이번 문제는 네트워크 연결(1922번)문제와 유사하게 접근하면 쉽게 풀 수 있습니다. 자세한 1922번 문제 풀이는 아래 링크로 남겨보겠습니다. [백준] 1922번 네트워크 연결 문제 풀기(Java) - 세무민의 코딩일기 이번 포스팅은 알고리즘 문제 풀이 포스팅입니다. 이번 문제는 네트워크 연결이라는 문제입니다. 1. 문제 설명 2. 입출력 예제 3. 문제 풀이 위의 그림을 보면 모든 컴퓨터가 최소 비용으로 연결 sg-moomin.tistory.com 문제 풀이의 결론을 말하자면 도시를 2개로 분할시키면 됩니다. 유지비의 합을 최소로 할 수 있도록 하되 도시를 2개로 분할하려면 방법은 한개의 도시로 ..

이번 포스팅은 알고리즘 문제 풀이 포스팅입니다. 이번 문제는 네트워크 연결이라는 문제입니다. 1. 문제 설명 2. 입출력 예제 3. 문제 풀이 위의 그림을 보면 모든 컴퓨터가 최소 비용으로 연결되기 위한 방법은 위와 같을 것이다. 이번 문제에서 가장 중요한 포인트는 모든 컴퓨터를 연결하는데 필요하는 최소비용입니다. 여기서 알 수 있는 건 Kruskal-MST를 이용하여 문제를 풀 수 있다는 것입니다. Kruskal-MST는 최소 비용 신장 트리를 만든되 사이클이 생성되면 안되며 최소 비용이여 하는 것입니다. 따라서 Kruskal-Mst를 이용하면 문제를 풀 수 있습니다. package backjoon_20210920; import java.io.BufferedReader; import java.io.Bu..

오늘 풀어볼 문제는 게임 개발 문제입니다. 1. 문제 2. 입출력 및 예제 3. 문제 풀이 이번 문제도 동일하게 위상정렬을 이용하는 문제입니다. 이번 문제에서는 크게 봐야할 부분은 건물을 지을 때 건물 번호가 존재한다면 해당 건물이 지어진 시간까지 계산을 해야 한다는 것입니다. 즉 i번째의 건물을 짓는데 걸리는 시간을 구한다면 가장 최대의 시간(MAX)를 구해주면 시간적인 부분에서 문제 없이 건물을 지을 수 있습니다. 4. 코드 package backjoon; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io..

오늘 포스팅할 문제는 줄세우기 문제입니다. 1. 문제 내용 2. 입출력 3. 문제 풀이 우선 이번 문제는 그래프를 이용해서 푸는 문제이며 위상정렬을 이용한 문제이다. 위상정렬이라고 한다면 순서가 정해진 정렬이지만 싸이클이 없는 즉 단방향(사이클 발생 X) 그래프를 말한다. 문제를 좀 더 확인해보자. N명의 학생들의 키를 순서대로 줄을 세울려고 하는데 두 학생의 키를 비교하여 정렬을 한다고 가정한다. 첫번째 예제를 입력했을 때 줄을 세워진 방법이다. 1번의 친구와 3번의 친구를 비교하고 2번의 친구와 3번의 친구를 비교한다고 가정하면 3번의 친구는 1번과 2번의 친구를 비교한 상태 즉 2명과 비교했고 1번과 2번은 3번과 비교한 것을 제외하고 비교 대상이 없다. 즉 1과 2와 진입차수가 없다는 것을 확인할..

[세무민의 코딩일기] 로또의 최고 순위와 최저 순위 문제 풀이 이번에 풀어본 문제는 2021 Dev-matching : 웹 백앤드 개발 관련하여 출제된 문제이다. 1. 문제 설명 2. 제한사항 및 예시 3. 문제 풀이 방법 이번 문제는 문제 이해만 잘하면 쉽게 풀수 있는 문제입니다. 말 그대로 0을 제외하고 같은 값이 존재하는지 찾아본 뒤에 0값만큼 최고순위에 증가시킨 뒤 순위를 매기면 됩니다. 4. 코드 풀이 def RankCheck(result): return {6:1, 5:2, 4:3, 3:4, 2:5, 1:6, 0:6}.get(result, "rank") def solution(lottos, win_nums): result = [] maxResult = 0 minResult = 0 zeroChec..

이번 포스팅은 프로그래머스에서 위클리 챌린지 2주차 문제 풀이로 돌아왔습니다. 1. 문제설명 2. 제한사항 및 입출력 예시 3. 문제 풀이 이번 문제에서는 가장 큰 포인트를 둬야하는 문구는 2가지입니다. - 자신이 가장 최대 및 최소로 준 점수라면 제거한다. - 자신이 가장 최대 및 최소라고 생각했으나 동일한 값이 있다면 제거하지 않는다. 이 2가지의 조건만 잘 맞춰주면 문제를 풀 수 있습니다. # 처음 코드 def solution(score): result = "" for i in range(len(score)): maxCheck = 0 minCheck = 0 maxSize = list() for j in range(len(score[i])): maxSize.append(score[j][i]) maxC..

오늘 풀어볼 문제는 프로그래머스 스택/큐 문제 중 하나인 주식가격 문제입니다. 1. 문제 설명 및 제한 사항 2. 입출력 예시 3. 문제 풀이 제가 생각한 문제 풀이 방법은 위와 같습니다. 해당 i번째의 값을 기준으로 뒤에 나오는 값이 하락하는 경우 -1을 해주면 됩니다. 그리고 하락과 상승폭을 구한 값과 해당 i번째 기준으로 arr의 마지막까지의 길이의 합을 구해주면 됩니다. 코드는 아래와 같습니다. # 1번 풀이(Stack 이용 - 시간초과) from collections import deque def solution(prices): stacks = deque(prices) result = [] temp = 0 count = 0 inputprice = 0 numbers = 0 while len(sta..

오늘 포스팅 할 내용은 2019 KAKAO BLIND RECRUITMENT에서 나온 문제인 오픈채팅방 문제를 풀어봤습니다. 1. 문제 설명 2. 제한 사항 및 입출력 예시 3. 문제 풀이 이번 문제는 생각보다 당황스러웠던 문제 중 하나였습니다. 제가 푼 방법은 딕셔너리를 이용해서 key와 value를 사용한 방식입니다. 이번 문제는 말 그대로 "Enter Uid1234 Muzi"일 경우 "check usrId name"으로 구분하여 check 값이 요청할 때 해당 usrId에 대한 name값을 반환해주면 되는 문제 입니다. 처음 풀었을 때는 런타임 에러가 발생했었는데 두번째 푼 코드는 런타임 에러가 나지 않고 성공했습니다. 우선 코드를 보면서 하나씩 설명하겠습니다. # 틀렸던 코드 def solution..

오늘 포스팅은 프로그래머스에서 위클리 챌린지 1주차 문제인 "부족한 금액 계산하기"입니다. 퇴근 한 후에 머리 식힐 겸 풀어봤는데 생각보다 쉽게 풀어서 포스팅을 하게 되었네요..ㅎㅎ(이 문제가 쉬워요..) 1. 문제 설명 2. 입출력 예시 3. 문제 풀이 이 문제는 문제 설명보다 입출력 예시를 보면 바로 풀 수 있다. 말 그대로 놀이기구의 price와 count의 곱이 money보다 큰지 아니면 같거나 작은지를 구분해주면 됩니다. # 가장 표본인 답변 def solution(price, money, count): answer = -1 resultCheck = 0 for i in range(1, count + 1): resultCheck += price * i if(resultCheck = 0): answ..