본문 바로가기

전체 글262

[알고리즘] 최단거리 알고리즘(Dijkstra,Floyd Warshall) Dijkstra Algorithm 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘 입니다. A,B,C,D,E,F 노드가 있을 때 하나의 정점A를 기준으로 A-B, A-C, A-E ...까지의 최단거리를 구할 수 있습니다. 이전에 구한 값을 재사용한다는 의미에서 다이나믹프로그래밍, 항상 가장 짧은 거리의 노드를 선택한다는 점에서 그리디 알고리즘으로 분류하기도 합니다. 1. 출발 노드를 설정 2. 출발 노드를 기준으로 각 노드의 거리를 저장 3. 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택 4. 해당 노드를 거쳐가는 경우와 거쳐가지 않은 경우를 비교하여 최단거리 갱신 5. 3,4 과정을 반복 A를 기준으로 각 노드의 거리 저장하였습니다. D,E의 경우 .. 2020. 9. 22.
[알고리즘 문제] 백준2606 - 바이러스 www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net dfs,bfs로 풀 수 있는데 저는 bfs로 풀었습니다. 각 노드들의 간선을 양방향으로 map먼저 체크해주었습니다. 1번 컴퓨터 부터 시작하기 때문에 que에 1번을 넣어주고 하나씩 꺼내면서 맵에 연결되어 있으면 그 다음 시작점을 que에 넣는 방식으로 진행하였습니다. 한번 방문한 노드는 다시 방문하면 안되기 때문에 visited[]로 체크해주었습니다. #include #include using namespace.. 2020. 9. 21.
[알고리즘] 최소비용 알고리즘(Kruskal's, Prim's) 최소신장트리(MST : Minimum Spanning Tree) 크루스칼 알고리즘을 알기 전에 먼저 최소신장트리에 대해 간략하게 공부하고 넘어 가겠습니다. 신장트리란 트리의 특수한 형태로 모든 정점을 포함하고, 정점간 서로 연결되면서 사이클이 존재하지 않는 그래프를 의미합니다. 여기서 최소신장트리는 신장트리들 중에서 간선의 가중치가 최소를 만족하는 신장트리를 의미합니다. 아래의 사진을 보면 여러 정점들 사이에 간선이 존재하고, 이 간선에는 가중치값이 존재합니다. 아래의 왼쪽 그래프에는 다양한 신장트리가 나올 수 있습니다. 하지만 여러개의 신장트리 중에서 그 가중치의 합(간선에 배정된 값)이 최소가 되는 트리가 최소신장트리 입니다. 여기서 최소신장트리를 만드는 알고리즘이 이번시간에 배울 크루스칼 알고리즘과.. 2020. 9. 18.
[알고리즘] Union-Find 알고리즘 Union-Find알고리즘은 서로소 집합, 상호배타적 집합(Disjoint-Set)알고리즘이라고도 불립니다. 여러 노드가 존재할 때, 선택한 두개의 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 입니다. Union-Find 알고리즘에서는 두 노드를 Union연산, 즉 두 노드를 같은 그래프에 합치는 과정과 Find연산, 두 노드가 같은 그래프에 존재하는지를 확인합니다. 위에서와 같인 5개의 서로 연결되지 않은 채로 흩어져 있습니다. 여기서 각 노드들의 연결성을 프로그래밍 적으로 파악하기 위해 1차원 배열을 사용할 수 있습니다. index는 노드, index의 값은 부모노드를 의미합니다. 지금은 모두 독립적으로 존재하기 때문에 부모노드의 값을 현재의 index로 초기화 해줍니다. 여기서 두개의 노드.. 2020. 9. 15.
[알고리즘 문제] 백준17471 - 게리멘더링 www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제는 아래의 흐름으로 풀 수 있습니다. 1. 선거구를 나눌 수 있는 모든 케이스로 나누어 줍니다. next_permutation을 사용해도 되고 재귀를 사용해도 됩니다. 풀이에서는 재귀를 사용하였고 bool 1차원 배열을 사용하였습니다. 2. 케이스마다 각각의 선거구의 지역들이 모두 연결되었는지 검사합니다(연결 안되있으면 다음 케이스) 여기서 고민을 많이 했고, union-find방법을 사용할까 하다가, 다른분의 코드를 참고하여 .. 2020. 9. 11.
[알고리즘 문제] 백준14697 - 방 배정하기 www.acmicpc.net/problem/14697 14697번: 방 배정하기 정보 초등학교 6학년 여학생들은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 www.acmicpc.net 처음에 재귀로 문제를 해결하려다가 그냥 for문을 사용해서 풀었습니다. 그냥 for문을 사용해서 풀면 O(N^3)으로 풀 수 있는데 재귀를 사용하면 O(3^N)시간이 걸리게 됩니다. 따라서 재귀로 풀면 시간초과가 나옵니다. 1. 재귀버전(3^N) #include #include using namespace std; int A, B, C, N; int ans = 0; bool isFind = false; v.. 2020. 9. 11.
[알고리즘 문제] 백준17136 - 색종이 붙이기 www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크�� www.acmicpc.net 완전탐색(색종이를 하나씩 붙여보는 방식)으로 푸는 건 알고 있었는데 어떻게 코드로 옮겨야 할지 몰라 다른 분의 풀이를 참고하였습니다. 일단 재귀함수로 색종이를 계속 이어 붙이면서 기저조건은 다음과 같습니다. 1. x의 위치가 10인 경우 -> 다음 행으로 이동 2. y의 위치가 10인 경우 -> 사용한 색종이 개수 갱신(최소값으로) 3. arr[y][x]==0 인 경우 -> x+1로 이동 위의 조건.. 2020. 9. 11.
[알고리즘 문제] 백준1051 - 숫자 정사각형 www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 www.acmicpc.net 완전탐색 문제입니다. 변의 길이가 1,2,3...일때 구할 수 있는 정사각형을 모두 구하고 꼭지점을 검사하였습니다. 길이가 1인 정사각형도 존재하기 때문에 ans=1부터 시작해야 합니다. #include #include using namespace std; bool check(int yPoint, int xPoint, int length, int arr[51][51]) // 각 꼭지점의 값이 모두 동이한지 .. 2020. 9. 10.
[알고리즘 문제] 백준2589 - 보물섬 www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 보물간에 최단거리를 구하는 문제인데, 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 사실 문제를 읽고 "최단 거기로 이동하는 데 있어 가장 긴 시간이 걸리는 ~"이 이해가 잘 안되서 몇번 읽었습니다. 중요한 것은 "최단거로 + 가장 긴 시간"을 만족해야 하는데 bfs를 사용하면 자동으로 최단거리를 만족하고 가장 긴 시간은 bfs로 탐색할 때 max값을 계속 갱.. 2020. 9. 9.

티스토리툴바