반응형 분류 전체보기88 [알고리즘] 다익스트라 개념정리~~~!, BOJ1753 적용 이전에 했던 크루스칼, 크림이 최소신장트리(모든 정점을 있는 간선들 중에 가장 비용이 적은 애들)를 찾는 알고리즘이었다면, 다익스트라는 하나의 정점에서 다른 정점으로 가는 길목들 중에 가장 비용이 적은 간선들을 고르는 것이다. 목적은 달라도 구현방식은 유사하다. (비슷한데 조금씩 달라서 더 헷갈리기도 한다..ㅎㅎ) 정점 정보로(=행렬로) 입력값이 들어온다면? 무식하게 행렬로 하는게 더 간단할 때가 있는 법이다. 순서대로 체크포인트: 입력이 정점들로 주어지니 일단 다 받는다. 다익스트라는 출발 정점->도착 정점 문제임을 잊지말자. int[] distance부터 논리가 시작된다! distance[2]은 출발정점 ->2번정점으로 오는 최소비용이다. 주의할 게, 어디어디를 몇번 거쳐서 어케 왔든간에 출발정점에서.. 2022. 2. 24. [BOJ]16236_아기상어(BFS응용) 진짜 과장 거의 안하고, 하루종일 이거만 푼 거 같다. 잘 하는 분들은 한시간만에 풀던데, 난 거의 열배넘는 시간을 들여서 겨우 했다. https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 처음에 문제를 읽을 때 도저히 감도 잡히지 않았다. 해설을 보고나서야 BFS구나를 깨달은 나는 ㅄ인가. 암튼,해설대로만 하지 않고 그래도 아무것도 안보고 다시 시도해서 겨우겨우 하는 데 성공했다. 단, 중간중간 버그잡는게 두시간가까이 걸렸다. 절대 대충 이.. 2022. 2. 24. [알고리즘]최소신장트리(크루스칼,프림) 이름부터 무슨 중국말도 아니고 신장트리래. 영어는 더 어려움 수학공식같은 이름.. 그러나 막상해보면 별거아님 또. 이름 지은 사람들 다들 한대씩 맞아야함.ㅋㅋ 위 알고리즘을 쓰는 때는, 그래프에서 최소비용을 구할 때 쓰인다. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가되는 것을 구할 때 쓰인다. 신장트리란, 위구르신장지역 아님. 아니 암튼, 신장트리란 n개의 정점으로 이뤄진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이뤄진 트리를 말함. 걍 간단하게 말하면 모든 정점에 딱 하나씩만 간선이 있는거임. 이때 최소신장트리란, 무향 가중치 그래프에서 신장트리를 구성하는 가중치의 합이 최소인 신장트리를 말함. 그니까 두 정점 사이에 간선이 여러개 있을 수 있는데 그중 가장 쬐그만 간선들로 이뤄진 신.. 2022. 2. 23. [알고리즘]인접행렬과 인접리스트에서의 DFS,BFS 입력값으로 간선의 정보들이 주어지는 문제에서 탐색을 요구할 경우 인접행렬 또는 인접리스트로 DFS 나 BFS로 풀게 된다.(나중에 간선정보로 푸는 문제에는 최소신장트리를 구하는 크루스칼 알고리즘도 있지만, 최소신장트리가 아닌 일반적인 그래프에서는 인접행렬 또는 인접리스트로 푸는 경우가 많다) 인접행렬이나 인접리스트 뭐가 절대적으로 좋다라고 말할 순 없지만, 정점의 수가 엄청 많은데 간선은 없는 경우에는 인접리스트가 더 효과적일 것이고, 밀집그래프에서는 리스트는 타고타고타고 가야하니까 시간이 오래걸리므로 인접행렬이 더 나을 것이다. 문제의 정점과 간선 수를 보고 선택하면 된다. 인접행렬에서 DFS, BFS 아래처럼 간선의 0~6까지 7개의 정점이 주어지고, 8개의 간선정보가 주어졌다. 모두 탐색하는 dfs.. 2022. 2. 23. [SWEA] SWEA3234_준형이의 양팔저울_백트래킹 순열과 부분집합을 동시에 적용해야 풀 수 있는 문제이다. 코드를 보면 파바박 할 수 있을 것 같지만, 백지상태에선 막막했다. 게다가 백트래킹(가지치기)를 제대로 하지 않으면 시간초과까지 뜨니 효율성도 고려해야 한다. 결론적으로 순열+부분집합+백트래킹을 연습할 수 있는 good 문제. 문제. 준환이는 N개의 서로 다른 무게를 가진 무게 추와 양팔저울을 가지고 있다. 모든 무게 추를 양팔저울 위에 올리는 순서는 총 N!가지가 있고, 여기에 더해서 각 추를 양팔저울의 왼쪽에 올릴 것인지 오른쪽에 올릴 것인지를 정해야 해서 총 2N * N!가지의 경우가 있다. 하지만 양팔 저울에 갑자기 문제가 생겨서 무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 .. 2022. 2. 18. [알고리즘] 그리디 그리디는 정해진 방법이 없다. 해당 문제가 그리디라는 것을 눈치챘다면 순간의 센스가 8할이라고 한다. 그렇다면 패스..하려다가 일단 가장 대표적인 그리디 문제의 유형 하나쯤은 마스터해놓는 것도 나쁘진 않겠다 싶어 정리를 한다. 가장 유명한 예제는 바로 회의실 예약하는 문제이다. 그림을 그려서 푸는게 말로 100마디 하는것보다 훨씬 이해가 잘되니 글은 그림으로 해도 안될때 읽기 바란다. 회의실은 하나인데, 회의는 10개이다. 어느 회의를 회의실에 예약해야 가장 많은 회의를 진행시킬 수 있을까? 구현 시 재밌던 점은 Meeting 클래스를 하나 더 만들고 Comparable을 상속하여 compareTo메소드를 오버라이드 한것이다. 이는 회의실의 종료시간을 기준으로 오름차순 정렬을 해야 하는데, 사용자 정의 .. 2022. 2. 17. 이전 1 ··· 3 4 5 6 7 8 9 ··· 15 다음 반응형
