새벽 기상을 꿈꾸는 루민

안녕하세요 세기무민입니다. 이번 포스팅에서는 그리디 알고리즘에 대해 다뤄보도록 하겠습니다. Greedy? 탐욕? 우선 그리디 알고리즘은 탐욕 알고리즘이라고도 말합니다. 그리디 알고리즘에서 가장 중요하게 생각하는 포인트는 "현재 선택지 중 가장 좋은(최적)의 방법을 선택하는 것" 그리디 알고리즘에 대한 가장 좋은 예시는 최단거리를 구하는 것이다. 아래의 그림으로 설명해보면 시작 지점으로부터 끝지점까지 최단거리를 구해보도록 하자. 시작 지점에서 4로 시작하는 경우 2가지의 경우의 수가 만들어지며 20, 23의 거리를 가진다. 시작 지점에서 4보다 큰 6으로 시작했을 경우 19의 거리를 가지게 되고 최종적으로 가장 짧은 거리를 가지게 된다. 즉 그리디 알고리즘은 여러개 중 한개를 선택해야 할 경우 그 순간에 ..

이번 포스팅에서 풀어본 문제는 "전기가 부족해"라는 문제입니다. 1. 문제 2. 입출력 및 예제 3. 문제 풀이 이번 문제는 가장 중요한 것이 3개의 발전소로 나눈다는 것이다. 따라서 이번 문제에서는 find를 이용하여 정점들을 탐색할 때 탐색한 경우 체크하는 것이 중요하다 . 아래의 그림을 통해서 이해해보자 위의 그림처럼 가정하여 풀어보도록 하자. 처음에는 발전소를 선택하지 않았기 때문에 모두 0의 값을 가진다. 발전소를 1,2,9번으로 선택하고 진행할 예정이다. 발전소를 선택했을 때 해당 발전소의 값(index)에는 체크를 해두면 된다. 양수의 값의 경우 겹칠 수 있기 때문에 음수의 값으로 체크하는 것이 중요하다.(boolean으로도 가능) 가장 짧은 간선인 2를 이어주고 7에 체크를 해준다. 다음으..

이번 포스팅에서 다룰 문제는 나만 안되는 연애 문제 입니다. 1. 문제 2. 입출력 및 예시 3. 문제 풀이 이번 문제에서 3가지의 특징을 잘 분석하면 된다. 1. 남초 대학교와 여초 대학들을 연결하는 도로만 이루어져 있다. -> 이말은 즉 2가지의 정점으로 구분된다는 의미 2. 사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서 모든 대학교로 이동 가능하다. -> 모든 정점들이 모두 이어져서 있어야 한다는 것, 즉 트리형태 3. 시간낭비하지 않고 경로의 최단거리를 구해야 한다. -> 최소 스패닝 트리 4. 모든 학교를 연결하는 경로가 없을 경우 -1을 출력한다. -> 학교 정점 == 입력받은 학교의 수 - 1 우선 위의 포인트를 잘 이해하면 문제를 쉽게 접근할 수 있다. 그래도 이번 문제를 풀기..

이번 포스팅에서 다룰 문제는 별자리 만들기 입니다. 1. 문제 2. 입출력 및 예시 3. 문제 풀이 이번 문제에서 포인트는 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있다는 말이다. 이 말은 즉 그래프 형태이면서 간접적으로 연결되어 있다는 것은 부모가 연결되어 있으면 연결되어 있는 구조이다. 이 문제는 최소 스패닝 트리 문제와 동일하다. 따라서 Kruskal-Mst 알고리즘을 이용해서 문제를 풀면 된다. 그렇지만 문제를 풀다보면 기존에는 결과값을 주었지만 이 문제는 주지 않았다. 그 말은 해당 정점들의 간선 길이를 내가 직접 구해야 한다는 말이다. 아래의 그림을 보면서 한번 이해해보자. 위의 예시대로 그림을 그려봤다. 정점들을 그린 뒤 간선을 하나씩 이어봤다. 간선을 이어봤다면 이제 ..

이번 포스팅에서는 최소 스패닝 트리 문제를 풀어보겠습니다. 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. 문제 풀이 위의 그림을 보면 모든 컴퓨터가 최소 비용으로 연결되기 위한 방법은 위와 같을 것이다. 이번 문제에서 가장 중요한 포인트는 모든 컴퓨터를 연결하는데 필요하는 최소비용입니다. 여기서 알 수 있는 건 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와 진입차수가 없다는 것을 확인할..

최근에 면접 준비하느라 포스팅을 못했는데 면접이 끝나서 오늘 일어나자마자 푼 문제를 포스팅 해보려구 합니다! 오늘 푼 문제는 3진법 뒤집기! 문제 설명 & 제한 사항 & 입출력 예시 풀이 이번 문제는 담백 그 자체! 사실 어렵지 않다. 10진법 -> 3진법 -> 역순 -> 10진법 위에 조건처럼 구현해주면 되는데 여기서 리스트를 이용하면 역순부분을 사용하지 않아도 된다. 즉! 10진법 -> 3진법 -> 10진법 바로 코드를 보도록 하자! # 첫번째 코드 def solution(n): result = [] count = n while count > 0: tmp = count % 3 result.append(tmp) count = int(count / 3) i, check = -1, 0 answer = 0 ..

오늘 풀어 볼 문제는 문자열 내 마음대로 정렬하기! 문제 설명 및 제한 조건 입출력 풀이 사실 이번 문제는 10분?정도 걸렸던거 같네요 ㅎㅎ 사실 너무 쉬운 문제라서 포스팅하는게 맞는지 의문이 들었지만 해봅니다. 이번 문제에서는 n번째 값을 기준으로 정렬을 해주면 됩니다. 또한 같은 값이 존재한다면 사전순으로 나열하면 된다고 하네요! 여기서 초점을 둬야하는 부분은?! 1. 정렬을 2번 해주기! 정렬을 2번하는 건 사전순으로 한번 정렬해준 뒤 n을 기준으로 정렬해주기 위해서! 이렇게 문제를 접근하면 끝입니다. 코드는 2가지 방법으로 풀어봤어요! 코드 def solution(strings, n): # 방식 1 strings.sort() strings.sort(key=lambda x : (x[n])) retu..