본문 바로가기

전체 글82

다양한 그래프 알고리즘 - 서로소 집합 안녕하세요. 오늘은 코딩 테스트에서 사용할 수 있는 다양한 그래프 알고리즘에 대해서 소개드리려고합니다. 그래프 알고리즘에 들어가기 앞서, 먼저 기초 내용부터 다지고 들어가겠습니다. 그래프 노드와 노드 사이에 연결된 간선정보를 가지고 있는 자료구조를 의미합니다. 그래서 알고리즘 문제에서 '서로 다른 개체(혹은 객체)가 연결되어 있다'는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 합니다. 트리 더불어 그래프 자료구조 중에서 트리 자료구조는 다양한 알고리즘에서 사용되므로 꼭 기억하면 좋습니다. 다익스트라 최단 경로 알고리즘에서는 우선순위 큐가 사용되었는데, 우선순위 큐를 구현하기 위해 최소 힙이나 최대 힙을 이용할 수 있다고 했습니다. 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조.. 2024. 1. 19.
[이코테] 전보(2) - 코딩테스트 - 다른풀이 안녕하세요. 이번에는 이전에 풀었던 전보 - 다익스트라 알고리즘 풀이를 다른 방식으로 풀어보려고합니다. 다익스트라 풀이법은 아래의 링크로 들어가시면 보실 수 있습니다. https://sonlife97.tistory.com/entry/%EC%9D%B4%EC%BD%94%ED%85%8C-%EC%A0%84%EB%B3%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B5%AC%EC%B2%B4%EC%A0%81%EC%9D%B8%ED%92%80%EC%9D%B4 [이코테] 전보 - 코딩테스트 - 구체적인풀이 문제 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하.. 2024. 1. 18.
[이코테] 전보 - 코딩테스트 - 구체적인풀이 문제 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다. 어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌.. 2024. 1. 18.
[이코테] 미래 도시 - 코딩테스트 - 구체적 풀이 문제 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다. 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 공중 미래 도시에서 특정 회사와 다른 회사가 도로로 연결되어 있다면, 정확히 1만큼의 시간으로 이동할 수 있다. 또한 오늘 방문 판매원 A는 기대하던 소개팅에도 참석하고자 한다. 소개팅의 상대는 K번 회사에 존재한다. 방문 판매원 A는 X번 회사에 가서 물건을 판매하기 전에 먼저 소개팅 상대의 회사에 찾아가서 함께 커피를 마실 예정이다. 따라서 방문.. 2024. 1. 18.
최단경로 - 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘이란? 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘입니다. 이번에 설명하는 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘입니다. 다이나믹 프로그래밍을 기반으로 하며, 특히 밀집 그래프(dense graph)에서 효과적입니다. 플로이드 워셜 알고리즘의 개념 초기화 먼저, 최단 거리를 저장할 테이블(2차원 배열)을 초기화합니다. 이 테이블의 각 항목 dist[i][j]는 정점 i에서 j로 가는 최단 거리를 나타냅니다. 자기 자신으로의 거리는 0으로, 직접 연결된 정점 사이의 거리는 해당 가중치로, 그렇지 않은 경우에는 무한대(또.. 2024. 1. 17.
[투자조언] 빅텍 투자정보 - 투자지침서 기업개요 1990년 7월 1일에 설립되었으며, 2003년 2월 5일 코스닥시장에 주식을 상장했습니다. 방위사업과 민수사업을 영위하고 있습니다. 방위사업 부문에서는 전자전 시스템 방향탐지장치, 군용 전원공급장치, 피아식별장비, TICN 장치 및 기타 방산제품 등을 생산하고 있습니다. 민수사업 부문에서는 공공자전거 무인대여시스템(U-BIKE) 등을 제공하고 있습니다. 주요 제품은 전자전 시스템 방향탐지장치로, 기존의 방향탐지장치인 SONATA와 함께 소형전자전장비(ACES -Ⅰ)를 별도로 개발 완료했습니다. 최신뉴스 피코팩-빅텍, 차세대 디지털엑스선 발생장치 개발 양해각서(MOU) 체결 "주식회사 피코팩이 주식회사 빅텍과 디지털엑스선 발생장치 사업 공동 개발 및 협력을 위한 양해각서(MOU)를 체결했습니다... 2024. 1. 17.
[투자조언] 대한해운 투자정보 - 투자지침서 기업개요 1968년에 설립된 이 회사와 그 종속회사는 해운업, 무역업, 광업, 건설업 등 다양한 사업을 수행하고 있습니다. 그들의 주요 사업은 해상화물운송 서비스이며, 주로 벌크선, LNG선, 탱커선 등의 선박을 통해 철광석, 천연가스, 원유 등의 원자재를 운송하는 것입니다. 주요 거래처로는 포스코, 한국가스공사, 한국전력공사 등이 있으며 장기운송계약을 맺어 안정적인 영업과 수익을 극대화하려고 노력하고 있습니다. 최신뉴스 홍해 지정학적 긴장 속 해운주 주가 급등, 대한해운 27% 상승 "홍해 지역의 지정학적 리스크 증대로 인한 물류비 상승 기대감이 투자자들 사이에 퍼지면서 대한해운을 포함한 해운주들이 17일 장중 큰 폭의 상승세를 기록하고 있다." 미국과 영국의 후티 반군에 대한 지속적인 공습으로 인해 .. 2024. 1. 17.
최단경로 - 다익스트라 알고리즘 구체적인 설명(2) - 우선순위큐 활용 이전의 간단한 다이스트라 알고리즘 https://sonlife97.tistory.com/entry/%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%EC%B2%B4%EC%A0%81%EC%9D%B8-%EC%84%A4%EB%AA%85 최단경로 - 다익스트라 알고리즘 구체적인 설명 다익스트라 알고리즘은 하나의 출발 노드로부터 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 알고리즘의 원리를 간략히 설명하면 다음과 같습니다. 1. 출발 노드를 설정한다. 2. 최단 거 sonlife97.tistory.com 해당 알고리즘의 시간 복.. 2024. 1. 16.
자료구조 - 힙(Heap) 힙(Heap) 이란 힙은 특별한 종류의 이진트리인데, 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용됩니다. 힙은 다음과 같은 특성을 가지고 있습니다. 1. 부모 노드의 값이 항상 자식 노드의 값보다 크거나 작음(최대 힙 또는 최소 힙). 2. 완전 이진 트리(Complete Binary Tree) 구조를 가짐. 이는 트리의 모든 레벨이 완전히 채워져 있고, 가장 아래 레벨은 왼쪽부터 채워져야 함을 의미합니다. 힙은 주로 다음과 같은 작업에 사용됩니다. 최댓값 또는 최솟값을 빠르게 찾아내는 작업 (O(1) 시간 복잡도로 가능). 데이터의 삽입과 삭제(최대 또는 최소 요소에 대한)를 빠르게 수행하는데 효율적. 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 값을 가지며, 최소 힙은 부모.. 2024. 1. 16.
[투자조언] 아프리카TV 투자정보 - 투자참고서 기업개요 AfreecaTV은 1인 미디어 플랫폼으로, 기부경제선물 문화를 선도하고 있습니다. 그들의 매출은 기부경제선물과 광고로 나누어집니다. 광고매출은 플랫폼 내 광고상품을 판매하는 '플랫폼 광고'와 라이브방송 및 영상제작과 같은 '콘텐츠형 광고'로 구성되어 있습니다. 주요 사업은 'AfreecaTV'로 국내외 시장을 공략하면서, 광고와 라이브 커머스와 같은 신사업도 진행하고 있습니다. 최신 뉴스 "트위치의 국내 철수 후, 아프리카 TV가 네이버 치지직을 앞서는 모습을 보이며 대형 스트리머 영입으로 이용자 유입을 주도하고 있습니다." 트위치가 국내에서 철수를 예고한 후, 아프리카TV가 네이버 치지직을 앞서는 모습을 보이고 있습니다. 최근 모바일 빅데이터인 모바일인덱스에 따르면, 치지직의 일간 활성 사용.. 2024. 1. 16.

티스토리툴바