공작소

문제 링크 : https://www.acmicpc.net/problem/10423 풀이 과정목표는 모든 도시를 발전소가 설치된 도시와 연결하는 것, 연결할 때 케이블을 최소 비용으로 설치하는 것이다. 도시를 최소 비용으로 연결하기 위해 최소 스패닝 트리 알고리즘을 사용하지만, 모든 도시가 발전소와 단순히 "연결"되어 있기만 하면 되므로 이 알고리즘을 살짝 변형시켜주면 된다. 1. 크루스칼 알고리즘 변형하기 먼저, 기본 크루스칼 알고리즘의 전체적인 실행 순서에 대해 알아보자.n개의 노드가 있을 때, m개의 간선들을 비용 기준으로 오름차순 정렬한다.정렬된 간선들을 차례대로 순회하면서, 간선이 연결하는 두 노드가 다른 부모 노드를 바라볼 때 (그룹이 다를 때) 두 노드를 연결한다.2번으로 n - 1 개의 간선..

원래는 주마다 잡담을 쓰려고 했는데, 그 주에 일어난 일이 아예 없거나 아주 많거나... 들쑥날쑥하다. 그래서 한 달에 일어난 일을 모아서 잡담을 쓰고자 다짐했다. 12월 7일에 쓰는 11월 잡담이라니, 새삼 너무 바쁜게 체감된다.. 하지만 다사다난했던 만큼 얻은 것 또한 많다. 내 인생에 크게 남을 커리어를 쌓기도 하고, 공부 과정에서 깨달은 것도 있다. 더럽게 안 지나가던 11월이었지만 되돌아보면 아주 빨랐던 11월을 회고해보고자 한다. 1. 이천시장기 제1회 군 장병 독서감상문 대회 최우수상 수상https://www.newspeak.kr/news/articleView.html?idxno=671803 이천시, ‘제1회 군 장병 독서감상문 대회’ 장병들의 뜨거운 관심 속에 마무리 - 뉴스피크[뉴스피크]..

문제 링크 : https://www.acmicpc.net/problem/1477 풀이 과정처음 접근 방법은, 최대 길이 구간의 중간에 휴게소를 설치하는 아이디어였다. 예를 들면, n = 4, l = 700 이고휴게소 위치 :  100  200  500  600구간 길이 :  100  100  300  100  100일 때,최대 길이 구간인 200 ~ 500 중간에 휴게소를 설치하여휴게소 위치 :  100  200 (350) 500  600구간 길이 :  100  100  150  150  100  100 다음과 같이 최대 길이 구간을 찾고, 그 구간을 분할하는 걸 m번 반복할 생각이였다. 하지만 이 아이디어는 최적의 방법이 아니다. 중간 설치 아이디어 문제점 : 균일하게 나누는 것이 더 최적이다.예를 들..

문제 링크 : https://www.acmicpc.net/problem/5214 풀이 과정역 하나하나마다 간선을 연결하는 것은 너무 비효율적이다. 한 하이퍼튜브 안에서 모든 역은 연결되어 있기 때문이다.한 하이퍼튜브가 서로 연결하는 역의 개수 K의 최대 제한이 1000이므로, 각 하이퍼튜브마다 K(K-1) 개의 단방향 간선을 생성해야 하는 일이 발생한다. 한 하이퍼튜브 안에서 단번에 다른 하이퍼튜브로 갈 수 있는 방법이 필요하다.  바로 하이퍼튜브 정점을 따로 만드는 것이다. 하이퍼튜브 정점을 따로 만들면, 한 하이퍼튜브 안에 있는 역 정점들은 하이퍼튜브 정점 한 개를 거쳐서 바로 연결되고, 다른 하이퍼튜브 안에 있는 역 정점 또한 하이퍼튜브 정점을 거쳐서 바로 연결될 수 있다. 이 아이디어가 있으면, ..

잡담 탭에 근황을 전하기로 다짐한게 8월인데, 정신없이 살다보니 10월의 절반을 넘어가고 있었다. 그동안 어떠한 근황이 있었는지에 대해 회고를 작성하고자 한다. 1. 우당탕탕 9월9월에는 추석 연휴와 휴가를 비롯한 다양한 일정들이 있어서, 이를 소화하느라 시간이 빠르게 지나갔다. 추석 연휴가 길었기 때문에 이 기간동안 TOPCIT 공부를 많이 하고자 다짐을 했지만, 방대하고 어려운 시험범위에 지쳐서 TOPCIT 공부에 크게 시간을 쓰진 못했다. 이후 있을 큰 일정들에 대비해 휴식 주기를 가진게 아닐까 싶어도, 기억이 나지 않는 다양한 일들이 많았어서 쉰 듯 안 쉰 듯 했다. 추석 연휴 이후에는 휴가를 다녀왔다. 짧은 5일동안의 휴가였지만, 휴가를 나와있는 동안에는 사실 내가 입대한게 꿈은 아니었을까 라는..

프로그래머스 코딩테스트 연습 문제 중에서 2024 KAKAO WINTER INTERNSHIP 문제 세트를 알고리즘 스터디 중에 풀어보게 되었습니다. 해당 문제 세트를 어떻게 접근했고, 어떻게 코드를 작성했는지에 대한 전체 풀이 과정을 포스팅할 예정입니다. 제가 풀이한 과정이 모범 정답 풀이가 아닐 수도 있음을 밝힙니다. 단순히 제가 떠올리고 정답을 받은 풀이임을 알립니다! 1. 가장 많이 받은 선물다음 달에 선물을 가장 많이 받을 친구가 "다음 달에 받을 선물의 수"를 구해야 한다.다음 달에 선물을 받기 위해선 다음과 같은 조건이 필요하다.특정 두 사람이 주고 받은 선물 기록이 있다면, 더 많이 준 사람이 다음 달에 선물을 하나 받는다.선물 기록이 같거나 없다면, 선물 지수 (이번 달 준 선물 수 - 이..

이번 주는 특별히 바빴다. 하고 있는 일에 집중하느라 다른 일들에 집중을 많이 못했다. 특히 TOPCIT 공부를 주력으로 하지 못한 점이 후회가 남는다. TOPCIT 시험 범위는 내용이 지루하고 어려워서 백준 문제를 푸는 게 더 끌렸던 것 같다.   다가오는 9월엔 배워야할 게 정말 많다. 군대에서 하는 일도 포함해서, 꾸준히 백준 문제를 푸는 것과 동시에, TOPCIT 시험 준비와 프로그래밍 언어 5종 숙달이 필요하다. TOPCIT 시험도 40일 가량 남았는데, 그 안에 이 수많은 분량을 다 끝낼 수 있을까에 대한 걱정이 생기곤 한다. 열심히 공부하다 보면 9월이 한 순간에 지나가겠지..? 1. 대외활동 최근 들어 입대하기 전에 공모전이나 대외활동 등의 활동을 많이 못 해본 후회가 남는다. 주변에서 진..

입대하고 나서부터 입대 전보다 하는 게 점점 더 많아지는 것 같다. 성장하고 있는 중!매주마다 그 주에 있었던 일들을 회고 느낌으로 작성해보고자 한다. 사실 이전부터 쓰려고 시도했다가 계속 실패했던건데, 입대한 지금은 뭔가 다르겠지라는 느낌으로 다시 도전해본다.1. Solved.ac 등반 올해 4월부터는 입대에 대한 준비 및 걱정이 가득한 마음에 '이제 백준 많이 못 하겠구나..' 라고 생각하며 문제 풀이보다는 놀기만 했었다. 군 부대 안에서 자율적으로 공부할 수 있다고 듣긴 했지만 모든 부대가 동일한 분위기인 것은 아님을 알고 있었기에 군 복무 중의 공부는 거의 포기 상태로 계획하고 있었다. 그렇기에 새로운 알고리즘을 공부해야겠다는 생각은 하지 않은 채로, 내 레이팅은 작년 6월부터 쭉 변함없이 다이아..

강한 연결 요소 (SCC, Strongly Connected Component) 란, 유향 그래프에서 정점의 부분집합이 부분집합 내의 다른 모든 정점에 대해 방문 가능한 경우를 말한다. 쉽게 말해 사이클이 생기는 그룹을 엮으면 강한 연결 요소가 된다. 다음 그래프에서 사이클이 생기는 그룹을 엮어보자. 이 사이클이 생기는 그룹을 하나의 정점으로 보고 문제를 해결해야 하는 경우가 생길 수 있다. 따라서 이렇게 엮은 그룹들을 정점으로 치환하면 다음과 같은 그래프로 볼 수 있다. 정점 안에서 엮여진 하위 정점들은 그 정점 안이라면 언제든 방문 가능하다. 이렇게 강한 연결 요소로 묶으면 사이클이 없는 유향 그래프로 바라볼 수 있다는 특징이 있다. 이제 SCC 를 두 가지 방법으로 구현해보자. 타잔 알고리즘SCC ..

문제 링크 : https://www.acmicpc.net/problem/24520 문제신촌 왕국에는 1번부터 N번까지 N개의 마을이 있고 N-1개의 도로가 서로 다른 두 마을을 연결하고 있다. 모든 마을은 도로를 통해 다른 마을로 갈 수 있고, 이때 마을 내에서의 이동 거리는 무시할 수 있다.현재 신촌 왕국은 "대칭병"의 대유행으로 혼란을 겪고 있다. 대칭병은 어떤 것이든 대칭을 이루지 않으면 심신이 불편해져 일상생활을 할 수 없게 만드는 병이다. 대칭병의 여파는 엄청났는데 심지어 사람과 사람 간의 만남조차 어렵게 됐다. 신촌 왕국의 두 사람이 만나는 상황을 생각해보자. 약속 장소가 둘 중 한 사람의 마을에 더 가깝다면 아주 불편해진다. 따라서 두 사람이 사는 각 마을까지의 거리가 정확히 같은 곳을 약속..