새벽 기상을 꿈꾸는 루민

안녕하세요 세기무민입니다. 회사 다니다보니 알고리즘 공부에 조금 소홀했는데 향후 이직이나 알고리즘 공부를 위해 틈틈히 풀면 좋을 것 같아서 이번 포스팅은 백준 알고리즘 포스팅으로 찾아왔습니다. 문제 설명 예시 문제 풀이 우선 해당 문제에서는 패턴만 파악하면 되는 문제인데 예시로 나온 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개로 분할하려면 방법은 한개의 도시로 ..

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

소드인사이트 문제를 기존에 풀었었는데 파이썬 공부 차원에서 풀어봤다. 결론적으로는 정렬을 하면 되는 문제! 우선 내가 C로 풀은 내용을 보면 #include #include void Sortin(char *a, int b) { int te; int max = 0; int index; for(int i = 0; i < b; i++) { if(b < 0 || a < 0)return; max = 0; index = i; for(int j = i; j < b; j++) { if(max < a[j]) { max = a[j]; index = j; } } te = a[i]; a[i] = a[index]; a[index] = te; } } int main() { char temp[101]; gets(temp); int..

최근에 알고리즘을 다시 접하면서 기존에는 C++로 문제를 풀었지만 파이썬이 속도가 빠르고 괜찮다고 하길레 파이썬을 공부하면서 문제를 풀고 있다. 사실 이 문제는 말 그대로 피보나치 공식을 알면 풀 수 있는 문제인데 처음에 고민했던건 굳이 제귀함수를 안써도 가능하겠는데? 라는 생각이 들었다. 이유는 결국에는 N번째 값만 출력하면 되니깐 반복문으로도 풀 수 있었다. 우선 방식을 2가지로 풀어봤다. 첫번째 방법은 가장 기본적인 제귀함수를 이용하는 방식 n = int(input()) def Fibonacci(x): if x == 0: return 0 elif x == 1: return 1 else: return Fibonacci(x-1) + Fibonacci(x-2) print(Fibonacci(n)) 피보나치..