Devlog

그동안 그래프 문제만 풀어대서 문제해결력 향상 + 코드포스 준비를 위해 다이나믹 프로그래밍과 그리디, 수학 위주로 문제를 풀고 있습니다. 너무 안해서 그런지 쉬운것부터 시작하는데도 빌빌거리네요. 마치 1년전 그래프로 빌빌거렸던 시절과 똑같은거 같습니다. 예나 지금이나 실력이 늘지 않는군요 ㅠㅠ 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 1부터 N까지 번호가 랜덤하게 나열되어 있습니다. 이 번호들을 오름차순으로 나열할 때, 이동되는 번호들의 최소 갯수를 구하는 문제 입니다. 그러니까 어느 번호가 옮겨지는 지, 어..

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 이전 문제인 다리 만들기 1이 여러 개의 섬들 중, 두 개의 섬을 잇는 다리의 최소 길이를 구하는 문제였다면. 2탄은 모든 섬들을 잇는 다리 길이의 합의 최솟값을 구하는 문제입니다. 구현 폭탄에 그래프 종합 문제라 다리 만들기보다는 난이도가 더 높게 책정되어있긴 한데, 저한테는 1탄보다 2탄이 더 쉬웠습니다. 1탄을 아마 거의 1년 전에 풀었던 거 같은데, 그 당시 그래프 알고리즘은 커녕 DFS, BFS에서도 빌빌거렸던 시절이라 더 어려워 보..

강한 연결 요소 (Strongly Connected Component) 시리즈 1. 코사라주 알고리즘 2. 타잔 알고리즘 3. 2-SAT 소개 강한 연결 요소(Strongly Connectioned Component)는 그렇게 잘 알려져 있는 알고리즘이 아니지만 제법 유용하게 쓰일 수 있는 알고리즘 입니다. 그래프에서 정점들 중 일부분이 서로 도달할 수 있는 정점들의 집합을 강하계 연결되었다. 라고 합니다. 강한 연결 요소 알고리즘이란 강하게 연결되어 있는 정점들의 집합의 정보를 구하는 알고리즘 입니다. 크게 코사라주 알고리즘과 타잔 알고리즘이 있습니다. 코사라주 알고리즘이 구현 난이도가 쉽기 때문에 이번 챕터에서는 코사라주 알고리즘 부터 설명합니다. 알고리즘 작동 방식 코사라주 알고리즘의 그래프이 간선..

개발 환경 OS: Ubuntu 20.04 LTS (WSL2) Compiler: GCC 9.4.0 (POSIX C) IDE: Vim, Visual Code 개요 파이썬에서 에러를 잡을 때는 try/except문을 사용합니다. 그리고 에러에 관련된 내용을 알 고 싶을 땐 "as e"를 추가해서 변수 "e"로부터 내용을 분석합니다. try: do_something() except Exception as e: print(e) 반대로 에러를 일으킬 수도 있는 데, 이때 "raise"문과 "Exception" 객체를 사용합니다. raise 문을 호출하면 해당 함수는 그 자리에서 바로 종료 합니다. def do_something(n): if n < 0: raise ValueError("Get Value Error")..

ㅠㅠ 점심에 게임 켜 놨다가 밥먹고 왔는데 꺼져버렸네요 너무 오랫동안 켜놓다가 그런줄 알고 램이고 그래픽카드고 식히다가 다시 끼워도 작동하지가 않네요 자세히 보니 케이블 전선 하나가 끊겨있는 걸 발견했습니다. 아마 원인이 파워 서플라이가 너무 오래되었다거나 (5년 가까이 썼습니다.) 케이블 끊긴게 원인이거나 둘중 하나 아니면 전부 다겠네요. 그나마 서버로 쓰던게 있어서 그걸 사용하고 있긴 한데, 기존 서버도 이제 사라졌고 서버 스펙으로는 FL 스튜디오가 돌아길리 없을테고 ㅠㅠ 당분간 작곡은 피아노 연습곡 외에는 뭘 만들지도 못하겠네요... + 사양 검색해 보니까 간신히 돌아갈 수 있긴 합니다. 권장사양에 턱걸이 정도 되는 듯 하네요 빨리 돈 벌어서 컴퓨터 하나 새로 사야겠습니다. ㅠㅠ

개요 위상 정렬은 DAG에서 정점의 순서를 정하는 데 사용하는 알고리즘입니다. 이는 대학교 선수 과목으로 쉽게 비유를 할 수 있습니다. 일부 과목들은 앞의 몇 개의 선수과목을 이수해야 들을 수 있는 경우가 있는데, 이런 경우까지 전부 체크해서 1학년 부터 4학년 까지 들어야 하는 과목의 순서를 나열할 때, 이 알고리즘을 사용하면 해결이 가능합니다. 원리 위상 정렬의 원리는 부모 정점과 이어저 있는 간선의 갯수(차수)를 파악하는 것입니다. 어떤 정점에서 몇 개의 차수가 있다는 것은 해당 정점을 탐색하기 전에 몇 개의 다른 정점을 탐색해야 해당 정점을 탐색할 수 있다는 의미가 됩니다. 즉 만약에 어떤 정점을 탐색을 완료했다면, 해당 정점의 탐색을 완료했기 때문의 해당 정점과 연결되어 있는 다음 정점들은 해당..