JooTopia's Blog

출처 : https://www.acmicpc.net/problem/2252 입사 후 교육을 받는 기간이라 주말에 간간히 한 두 문제 정도 풀 수 있다..ㅜ 심지어 회사와 관련된 내용과 지식은 보안상 조심해야 한다고 하기 때문에 퇴사 전 까지는 알고리즘 문제 풀이 정도나 올릴 것 같다. 오늘은 동기들을 통해 추천받은 "위상 정렬" 알고리즘 문제를 풀어봤다. 정답률도 높고, 정답의 범위도 넓기 때문에 푸는데 조금 수월했던 것 같다. 풀이 위상정렬의 개념에 대해서 공부하기 좋은 기본 문제라고 생각한다. a, b를 입력받을 때 a가 b를 참조한다고 생각하고, 참조 횟수가 0인 정점부터 위상 정렬을 수행하면 쉽게 문제를 풀 수 있다. 다만 참조 횟수가 0인 정점에 대해 정렬을 수행하고 나서 해당 정점이 참조하던 ..

출처 : https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오. A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다 www.acmicpc.net 그래프 이론 알고리즘으로 분류된 문제이다. 문제를 다 풀고 다른 사람들의 풀이를 참고하며 공부했는데 플로이드 와샬 알고리즘을 사용했..

오픈 S/W 컨트리뷰톤과 카카오 코딩 테스트를 위해 열심히 알고리즘 공부를 하는 중이다. 한 문제를 풀기 위해 여러 개의 알고리즘을 공부하게 되니 시간이 오래 걸리는 것 같다. 간단하게 코드만 정리하고 다음 공부를 하러 가야겠다. Kruskal과 Union Find - Kruskal 알고리즘 최소 신장 트리(MST)를 만들 때 사용하는 알고리즘의 종류 중 하나다. 노드가 많고 산선이 적을 때 유리하다고 하는데, 최소 신장 트리를 만드는 알고리즘 중에서는 가장 쉽기 때문에 공부를 시작했다. 시간 복잡도는 ​ O(E * logV) 모든 간선을 비용의 오름차순으로 정렬한 다음 간선을 차례대로 선택한다. - Union Find 서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다. 여러 개의 노드가 존재..

알고리즘 공부 혼자 하는 게 생각보다 어렵..지만 꾸준히 해야지! 나는 원래 C언어로 알고리즘 문제를 풀었다. 임베디드 전공이다 보니 전공과목에서 프로그래밍 언어를 C/C++ 만 배웠기 때문이다. 하지만 임베디드를 넘어서 다양한 분야에 만능 프로그래머가 되고 싶어서 파이썬을 시작하게 되었고, 요즈음은 파이썬으로만 문제를 푼다. 쓸데없는 소리를 한 이유는.. 파이썬으로 알고리즘 문제를 풀면 너무 느려서 시간 초과가 너무 자주 뜬다.. 편법으로는 PyPy3로 채점하는 방법이 있는데, 그래도 찝찝하긴 하다.. 나는 이 문제를 세그먼트 트리 알고리즘으로 풀었다. 간단하게 정리해보자 세그먼트 트리 이 문제를 단순하게 배열을 확인하는 알고리즘으로 구현한다면 O(N^2)의 시간 복잡도를 갖게 되어 시간 초과를 면하지..

카카오 온라인 코딩 테스트를 준비하기 위해 슬슬 알고리즘 문제들을 풀 때가 왔다. 간단하게 정리만 하고 다음 문제를 풀러 가자 백준 6603번 로또 문제는 여러 가지 알고리즘으로 문제를 풀 수 있다. 파이썬과 조합 함수 (itertools 모듈에 combinations 함수)를 사용하면 정말 쉽게 풀 수 있지만, 백트래킹으로도 풀어보고 싶어서 두 번 풀었다. 조합을 이용한 풀이법 combinations 함수를 호출하면 자동으로 사전 순으로 정렬해주기 때문에 정말 간단하게 풀 수 있는 문제이다. 정답 코드를 첨부하겠다. from itertools import combinations import sys input=sys.stdin.readline while 1: arr = input().split() if ..