본문 바로가기

코테6

다양한 알고리즘 - 서로소 집합(경로 압축 기법) 안녕하세요. 오늘은 이전에 다뤘던 기본적인 서로소 집합 알고리즘을 개선해 보려고합니다. https://sonlife97.tistory.com/entry/%EB%8B%A4%EC%96%91%ED%95%9C-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 다양한 그래프 알고리즘 - 서로소 집합 안녕하세요. 오늘은 코딩 테스트에서 사용할 수 있는 다양한 그래프 알고리즘에 대해서 소개드리려고합니다. 그래프 알고리즘에 들어가기 앞서, 먼저 기초 내용부터 다지고 들어가겠습니다. 그 sonlife97.tistory.com 기본적인 알고리즘을 사용하면 find 함수가 비효율적으로 동작합니다. 최악의 경우 find 함수가 모든 노드를 다 확인하는 터라 시.. 2024. 1. 19.
[이코테] 미래 도시 - 코딩테스트 - 구체적 풀이 문제 미래 도시에는 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.
최단경로 - 다익스트라 알고리즘 구체적인 설명(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.
[이코테] 바닥 공사 문제 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2 X 3 크기의 바닥을 채우는 경우의 수는 5가지이다. 입력 조건 1. 첫째 줄에 N이 주어진다. (1 2024. 1. 11.
[이코테] 개미 전사 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 합니다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있습니다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 선택적으로 약탈하여 식량을 빼앗을 예정입니다. 이때 메뚜기 정찰병들은 일지선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있습니다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 합니다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자. {1, 3, 1, 5} 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼.. 2024. 1. 11.

티스토리툴바