Sims의 문제해결 저장소

어느덧 티스토리에서 진행한 이벤트 오블완 챌린지가 마지막 날이 됐다..3주라는 시간이 정말 짧게 지나간 것 같다..( 회사 일때문에 그런지도.. ) 일단 2024년이 끝나가는 마당에 회사일에 치이고 퇴근 후 더이상 기운이 안나 추가적인 공부를 거의 안한 것 같다.그때 마침 티스토리에서 챌린지를 한다는 소식에 냉큼 참여했다. 다시 생각해봐도 정말 참여하기 잘 했다.  평소 공부하고 싶었던 것을 해당 챌린지 삼아 공부하여 블로그에 정리해 놓는 아주 좋은 시간이 됐다. 덕분에 deep하게 모델에 대한 이해를 한층 더 강화할 수 있었고, 수정 사항을 발견하여 추후에는 수정하여 commit도 보내볼 참이다. 모델뿐만 아니라 알고리즘 관련한 공부도 많이 진행했다. 취업하고 알고리즘에 관심이 뜸했는데, 챌린지를 참여..

이번에도 MST 알고리즘 문제를 하나 풀어보고자 한다.https://www.acmicpc.net/problem/6497 해당문제도 MST 관련된 문제여서, 여기까지 풀어본다면 MST에 대한 개념은 충분히 잡을 수 있을 것이라 생각이 든다.해당 문제도 오리지널 MST 알고리즘을 통해서 풀 수 있는 문제다. MST 알고리즘에 관련해서 다시한번 기억해보자. 1. node, edge , value가 각각 주어지는 상황에서, 최소한의 value을 이용하여 모든 노드를 하나의 그래프에 속하도록 만드는 테스크이다.2. edge의 총 개수는 node - 1로 MST를 구성할 수 있다.3. MST는 유니온 파인드 알고리즘을 이용해서 해결할 수 있다. MST 문제를 풀때 위 내용만 기억하고 진행하면 될 것이다. 푸는 순서..

지난번 최소신장트리의 개념을 공부했다.최소한의 개념만으로 풀어 볼 수 있는 문제가 바로 아래 링크의 문제이다.https://www.acmicpc.net/problem/1197 최소신장트리는 노드 , 간선 , 간선의 가중치가 주어지는 상황에서 최소한 간선의 가중치를 유지하며 모든 노드가 하나의 그래프에 속해있는 상태를 말한다.위 설명을 봤을때 딱 기억나는것이 한가지 있다. 바로 유니온 파인드..유니온 파인드를 이용하면 MST를 구성할 수 있다.유니온 파인드의 사이클을 점검하는 TASK, 같은 그래프에 속하는지 보는 TASK가 명확히 들어 맞는다.물론 유니온 파인드만 사용하면 풀순없지만 +@를 통해 쉽게 해결할 수있다.MST의 목표는 "최소의 간선 가중치"이다. 두 노드와 간선, 가중치가 주어질 것인데 이때..

이번에는 최소 신장 트리에 대해 공부하고 정리해보고자 한다. MST란?노드와 간선이 주어지고, 간선간 가중치가 존재했을때, 모든 노드가 간선으로 연결되어 하나의 그래프를 만드는데, 그중 가중치을 가장 낮게 하는 그래프 구조를 말한다.글로만 보면 무슨 의미인지 잘 이해할 수 없다. 아래 사진을 보자. 위처럼 노드,간선, 가중치가 제공되었을때 모든 노드를 연결하는 그래프를 그리는 방법은 아주 다양하게 그릴 수 있다.위처럼 간선을 연결하여 하나의 그래프를 그릴 수 있다.하지만, 가중치의 합은 간선의 가중치 값에 따라 서로 다르게 되고, 그래프당 가중치 합은 서로 다르게 된다. 이중 가중치 합을 가장 낮게 구성하여 모든 노드를 하나의 그래프에 연결하는것이 바로 MST - 최소신장트리 가 되는것이다. 여기서 몇가..

프로그래밍을 하다보면 Heap과 Stack 자료구조를 볼 수 있는데, 이 둘의 차이점을 알아보고자 정리한다.  1. Stack스텍은 너무나 자주사용하여 익숙한 자료구조일 것이다. FILO(First In Last Out) 형식을 따르며 주로 재귀함수에서 사용한 다는 점도 너무나 잘 알려진 사실이다. 추가적으로 메모리 부분을 살펴봐야 한다.Stack의 경우 정적 메모리에 할당되며, 컴파일 시 해당 크기가 결정되어 고정된 사이즈다. 이러다보니, OverFlow , UnderFlow가 발생할 수 있다. ( 정적 메모리 같은 경우는 로컬 변수가 저장되는 곳이다. 추가로, 함수를 호출하면, Stack구조에 쌓이게 되고, 해당 함수가 끝나면 Stack에서 pop되어 메모리가 자동으로 해제된다.) 스택의 구조는 상당..

https://www.acmicpc.net/problem/4195 Union-Find는 크게 두가지 테스크를 진행 할 수 있다고 언급을 했다.1. Cycle 여부 확인2. 동일 그래프 소속 여부 크게 두가지를 알 수 있는데 지난번 테스크는 사이클 여부를 체크하는 문제를 풀어봤다.이번에는 동일 그래프에 속하는지 판단 + @로 조금 다른 find를 하는 문제이다. 이번 알고리즘은 두 사람의 이름이 "A B"와 같이 주어지면, A와 B는 친구 네트워크가 생성된다는 의미이다.이렇게 되면 단순하게 노드를 연결하는 방법(Union)이 된다. 즉, Union 방식으로 그래프를 생성해 나가면 된다. 하지만 한가지 다른점은 Find가 친구관계가 input으로 들어왔을때, 해당 그래프는 몇명의 친구와 연관이 있는지 바로바..

지난번 유니온파인드 개념에 대해 알아보았다. 각 노드들을 병합시켜 가리키고 있는 root-node로 업데이트를 진행시키는 방법이었다.그 후 병합된 정보를 바탕으로 find을 찾아 같은 그래프에 속해있는지, 사이클이 있는지 살펴 볼 수 있다고 하였다. 그럼 적용가능한 문제를 하나 풀어보고자 한다.https://www.acmicpc.net/problem/20040 '백준'사이트에 있는 '사이클 게임' 문제이다.문제를 간단하게 정리해보면, 노드간 간선을 하나씩 그리는 게임을 하게 되는데, 진행하다보면 어느순간에 cycle이 생기는 순간이 생길것이다. 이걸 판단해 줄 수 있는 프로그램을 만들어 달라는 것이다. 정확히 유니온 파인드 알고리즘만 알고 있으면 풀 수 있는 문제다. 이 문제의 핵심은 Find에 존재한다..

알고리즘 Union & Find 알고리즘에 관해서 정리하고자 한다.알고리즘 이름 그래도 합치고, 찾는 알고리즘이다. 대개 이 알고리즘은 노드별 연결이 되어있을때, 사이클이 존재하는가를 찾는데 많이 사용된다.   위 그림처럼 노드와 간선이 존재한다고 했을때, 해당 그래프에서 사이클이 존재하는가 아닌가를 찾아낼 수 있다.사람의 눈으로 보면 간단하게 1->2->5->1의 사이클이 보이지만 알고리즘으로는 어떻게 알게되는지 알아보자.  위와같은 과정을 거쳐 최종적으로는 모든 노드의 root는 1에 연결되어있는 결과를 얻을 수 있다. 천천히 살펴보면 1. (1-2)의 경우, 간선으로 연결되어 있어서 2의 root-node값을 1의 root-node로 바꿔준다.(여기서 1의 root-node로 변경해준 이유는 1과 ..