새벽 기상을 꿈꾸는 루민

안녕하세요 세기무민입니다. 회사 다니다보니 알고리즘 공부에 조금 소홀했는데 향후 이직이나 알고리즘 공부를 위해 틈틈히 풀면 좋을 것 같아서 이번 포스팅은 백준 알고리즘 포스팅으로 찾아왔습니다. 문제 설명 예시 문제 풀이 우선 해당 문제에서는 패턴만 파악하면 되는 문제인데 예시로 나온 dir a?b.exe를 유심히 봅시다. acb.exe, aab.exe, apb.exe가 나와도 문제 없다고 하는 말을 다시 해석해보면 ?표에 들어간 단어는 달라도 무관하다는 의미를 가집니다. 즉, 입력받은 값들 중 같은 값이 아닌 경우에는 ? 표시를 해주면 되는 문제입니다. 코드를 보면 아래와 같습니다. # 명령 프롬포트 - 1032 inputValue = int(input()) for i in range(inputValue..

이번 포스팅에서 풀어본 문제는 "전기가 부족해"라는 문제입니다. 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. 문제 풀이 이번 문제는 네트워크 연결(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와 진입차수가 없다는 것을 확인할..

이번 포스팅은 2년 전에 C++로 작성해서 문풀 했던 기억이 나는데 파이썬으로 풀면 좀 더 간편하게 풀 수 있을 것이라고 판단해서 파이썬으로 풀어봤다. 문제는 위와 같은데 말 그대로 나이순으로 정렬한다. 그렇지만 나이가 동일한 경우에는 알파벳 순서대로! 이 경우에는 파이썬에서 sort를 이용한다면 쉽게 가능하다는 판단이 나왔다. C++로 문풀한 건 2년 전이지만 파이썬으로 쉽게 만들었지만 문제가 틀렸다고 나왔다. 그래서 무슨 문제인지 처음에 몰랐는데....... 파이썬에서 변수를 설정할 때 정수형을 구분 안해서 틀렸다.... 즉 Number = int(input().split()) 으로 변수를 입력받거나 아니면 변수를 int(number)로 변환해야 했는데... 그렇게 하지 않아서 문제가 틀렸다. # c..