공부하자

다익스트라 알고리즘이란? 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘이다. 한 정점에서 다른 정점까지의 최단 경로를 구하는데, 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 그래프 탐색 알고리즘 중 최소 비용을 구하는 알고리즘은 다익스트라 외에도 벨만-포드 알고리즘 Bellman-Ford Algorithm, 플로이드-워셜 Floyd-Warshall 알고리즘 등이 있다. (벨만-포드 알고리즘은 음수 가중치의 그래프도 탐색 가능하다.) 그중에서도 다익스트라 알고리즘은 프림 알고리즘을 살짝 변형한 형태인데, 두 가지 차이점이 존재한다. 차이점은 다음과 같다. ..

- 코스피 새해 첫 거래일 제외 8거래일 연속 하락세, 4.9% 하락 - 비트코인 현물 ETF, 상장 후 이틀째 하락...비트코인 가격도 내려 - 휘발유, 경유 가격 14주 연속 하락세 - 올해 수출 늘어도 ‘소비 부진’에 성장 체감 미미, 23년 한해동안 수출은 늘었지만, 민간소비는 연속 하락 - 미국, 후티 반군에 추가 공격...미·영 폭격에 유럽 내 판단 갈려 - 서울 아파트 매물만 7만5000건...'거래 절벽'에 매매가격 7주 연속 하락, 수요가 없어 거래량 급감 요인

- 코스피, 1년 8개월만의 최장기간 하락세.. 8거래일 연속 하락 마감 - 셀트리온, 셀트리온헬스케어 합병 신주 상장으로 단숨에 코스피 시장 시가총액 6위 - KB증권 "비트코인 선물 ETF 매수, 당국 가이드라인 전까지 제한" - AI 겨눈 삼성, CES서 차세대 반도체 대거 공개 - 현대차·기아, 작년 美서 165만대 판매… ‘사상 최대’ - 원유 가격 상승 우려, 미 유조선 이란에 나포등 영향 - 신세계, 中 춘절 관광객 기대감에 이틀 연속 상승 - 안 떨어지는 전셋값…서울 아파트 평당 2300만원 ‘고공행진’

- 코스피 7거래일 연속 하락, 2,540으로 하락 마감 - 日 닛케이지수 34년 만에 35,000선 돌파…새해 랠리 계속, 4거래일 연속 상승 - 일본은행이 대규모 금융 완화 정책 수정 기대감이 떨어지면서 엔저 하락세 - 미국 증권위, 11개 비트코인 현물 ETF 상장 승인. 11일부터 거래 가능 - 국내 운용사 "한국도 '현물 ETF' 출시 시간문제" - 中, 작년 車 생산·판매 첫 3000만대 돌파…"세계 수출 1위도 기대" - 3년 연속 매출 최대치…LG전자 수장 조주완 “질적 성장” 일성 - 카카오, 9개월 만에 6만 원대 주가 진입. 저점 대비 60% 상승 - 1월 둘째 주 전국 아파트값 변동률 -0.05%, 7주 연속 하락. 전셋값은 0.03% 상승…서울 상승폭 확대

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net BFS를 순회하면서 연결 요소의 갯수가 있는지 찾는 문제다. 처음엔 문제를 잘못 읽고 연결된 그래프가 몇개인지만 세아려서 출력하면 되는줄 알았는데, 아무 간선도 가지지않는 정점도 연결 요소에 포함시켜 구현해야 했다. 방향성 없고 가중치 없는 그래프다 보니 그냥 바로 BFS로 감을 잡고 풀었고, 백준 2606번 바이러스 문제와 유사한 ..

프림 알고리즘이란? 최소 신장 트리 (Minimum Spanning Tree, MST) 구현에 사용되는 알고리즘으로 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법이다. 프림 알고리즘의 시퀀스 1. 시작할 정점을 MST집합에 넣는다. 2. MST집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점을 MST집합에 넣는다. 3. 2번과정을 MST집합의 원소 개수가 그래프 정점의 갯수가 될 때까지 반복한다. 4. 만들어진 MST집합의 가중치를 다 더해서 MST Cost 산출. 크루스칼 알고리즘 vs 프림 알고리즘 크루스칼 알고리즘 : Kruskal's Algorithm 프림 알고리즘 : Prim's Algorithm 그래프의 최소 가중치 간선들을 정렬된 순서로 추가하여..

크루스칼 알고리즘이란? 최소 신장 트리 구현에 사용되는 알고리즘으로, 가중치가 있는 그래프의 모든 간선들을 대상으로 1. 최소 비용의 간선으로 구성 2. 사이클을 형성하지 않음 의 조건을 지켜가며 각 단계마다 최선의 해를 선택하기에 그리디 알고리즘에 기원을 둔다. 크루스칼 알고리즘의 시퀀스 1. 그래프의 간선들을 가중치 기준으로 오름차순 정렬한다. 2. 정렬된 간선들 중 가중치가 작은 순서대로 사이클을 형성하지 않는 한 선택한다. 3. 선택된 간선으로 MST를 구현한다. 4. MST 집합의 원소의 개수가 V-1개가 될때까지 위 단계를 반복한다. 이때, 주의해야 할 점은 사이클을 형성하지 않게 정렬된 간선들을 선택한다는 것이다. 따라서 사이클을 형성하는지 안하는지에 대한 판가름을 해줄 수 있는 메소드를 같..

신장 트리란? (ST, Spanning Tree) 모든 임의의 정점이 연결된 그래프의 부분 그래프이다. 모든 정점이 간선으로 연결되어 있지만, 사이클은 존재하면 안된다. 최소 신장 트리란? (MST, Minimum Spanning Tree) 그래프의 간선에 가중치가 부여될때, 신장 트리를 구성하는 간선들의 가중치의 합이 가장 작은 신장 트리이다. 이 최소 신장 트리를 구할때엔 보통 2가지 알고리즘을 활용해 최소 신장 트리를 구하게 되는데, 크루스칼 알고리즘과 프림 알고리즘이 그것이다. 최소 신장 트리의 특징 - 신장 트리들 중 간선의 가중치 합이 최소이다. - N개의 정점을 갖는 그래프에 대해 N-1개의 간선만 사용해야 한다. - 사이클이 존재하면 안된다. - 항상 최단 경로를 보장하지는 않는다. => ..

- 코스피, 외인·기관 매도에 2540대 마감… 6거래일 연속 하락 - 삼성전자, LG에너지솔루션 등 국내 주요 업체들이 잇달아 ‘어닝쇼크’ - 日증시, 3일 연속 큰폭 상승 3만4441 마감…33년11개월만에 최고치 - 현대자동차그룹, ‘소프트웨어 중심 자동차(SDV)’ 플랫폼 개발에 삼성전자 ‘엑시노스 오토’활용 - 엔비디아 베팅 늘린 ETF '웃음꽃'…순자산 1년새 3.6배 급증 - 올해부터 내년까지 준공되는 소형 주거용 오피스텔 매입시 세제 혜택 - 尹정부 "규제 최소화로 주택공급 속도내겠다" - 건설협회 "주택공급 정책 환영…정책 실현 가능성 매우 높아"

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net BFS 문제를 계속 풀어보고 있는데, 이 문제 또한 비슷한 형태의 알고리즘이다. BFS로 풀리는 문제는 정해진 몇몇개의 특징이 있는 듯 하다. 1. 가중치가 없는 그래프에서 최단 경로를 찾아야 한다거나 2. 그런 최단 경로의 갯수를 구한다거나 3. 어떤 행렬이나 지도를 주고 그 지도에서 같은 부분으로 묶이는 영역을 구한다거나 이런 특정한 조건이 들어간 문제가 있으면 웬만하면 BFS로 접근해라 라는 ..