새벽 기상을 꿈꾸는 루민

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

안녕하세요 세기무민입니다. 이번 포스팅은 브루트포스 알고리즘에 대해 다뤄보겠습니다. 브루트포스? 브루트 포스는 무차별 대입을 통해 값을 도출하는 방법입니다. 브루트 포스 알고리즘은 암호 해독에 유명한 알고리즘 중 하나입니다. 브루트 포스는 조합 가능한 모든 문자열을 하나씩 대입해보는 완전 탐색 기법이라고 생각하면 됩니다. 브루트포스 알고리즘 장단점? 조합 가능한 모든 문자열을 대입하기 때문에 정확도가 100%를 도출합니다. 단, 모든 경우의 수를 찾아가기 때문에 조금만 알고리즘이 복잡해져도 알고리즘의 시간 복잡성은 올라갑니다. 예시 알고리즘 문제 위의 문제는 가장 대표적인 브루트 포스 알고리즘 중 하나입니다. 3개의 숫자를 합했을 때 M의 크기와 가장 가까운 값을 찾는 문제인데 해당 문제는 순열을 통해서..

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

이번 포스팅에서는 최소 스패닝 트리 문제를 풀어보겠습니다. 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개로 분할하려면 방법은 한개의 도시로 ..