일지 & 개발

문제 요약 알고리즘 분류: 다익스트라 난이도: Gold4 문제내용: 시작점 부터 각 노드간의 최단 거리를 구해라. 이동 못할 경우 'INF'를 출력해라 사이트: https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제풀이 이번에는 문제 유형은 그래프 탐색중에 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘 기본적인것을 묻기 때문에 자세한 설명은 여기서 참조하면된다. 풀이에 대한 설명은 다익스트라 알고리즘알면 ..

이론 이번에 볼 알고리즘은 최단경로 알고리즘이다. A 지점에서 B지점까지의 최단 거리를 구하는 방법이다. 최단 경로 알고리즘은 그래프 탐색 알고리즘중에서 난이도 높은 편이라서 이것을 알기 위해서는 그래프, 힙, 그래프 탐색 알고리즘을 알아 야 이해 알수 있다. 기본 적인것을 모르면 아래 것부터 보고 이해 한다음에 다음 내용을 보면된다. 그래프: https://jih3508.tistory.com/100 [알고리즘 이론] 그래프(Grape) 이론 이번에 볼 자료구조는 그래프이다. 트리는 노드간에 부모-자식, 형제 이런 개념이 있지만 그래프는 노드하나 이상이 사이클을 가진 개념이다. 사이클이란 간선 한번만 이동 가능할때 노드 jih3508.tistory.com 힙: https://jih3508.tistory...

이론 이번에 볼 자료구조는 그래프이다. 트리는 노드간에 부모-자식, 형제 이런 개념이 있지만 그래프는 노드하나 이상이 사이클을 가진 개념이다. 사이클이란 간선 한번만 이동 가능할때 노드가 자기 자신 노드로 돌아 올수 있다는 개념이다. 그래프에 대한 자세한 내용알고 싶으면 아래 사이트에서 확인 해보면된다. https://namu.wiki/w/%EA%B7%B8%EB%9E%98%ED%94%84(%EC%9D%B4%EC%82%B0%EC%88%98%ED%95%99) 그래프(이산수학) - 나무위키 그래프는 그래프 이론에서 다루는 수학적 대상이다. 그래프 이론의 초기에는 그래프가 한 종류였지만, 현대에 들어 전산학, 전자공학 등의 발전으로 인해 여러 변형이 생겼다. 무향 그래프의 꼭 namu.wiki

문제 요약 알고리즘 분류: 플로이드 워셜 난이도: Gold4 문제내용: 각 노드간의 최단 거리를 구해라 시작과 도착점은 같은 거리는 없다. 시작점에서 도착점까지 갈수 없으면 0으로 표시한다. 사이트: https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제풀이 이번에는 문제 유형은 그래프 탐색 관련 문제이다. 모든 노드간의 최단 거리를 구하라는 문제가 나와있고 데이터가 최대 100으로 봤을때 플로이드 워셜 알고리즘으로 해결 할 수가 있다. 시간복잡..

이론 이번에 볼 알고리즘은 플로이드-워셜이다. 플로이드 워셜은 다익스트라 알고리즘이랑 비슷한점은 a → b 최단 거리를 구하는 것인데 다익스트라는 시작점과 끝점이 있다는것고 플로이드 워셜은 각 노드간의 최단 거리를 구하는 것이다. 하지만 다익스트라와 다르게 구현이 간단하는데 시간복잡도는 O(N^3)이라는 긴 시간 복잡도를 간진다. 자세한 설명은 아래의 사이트에서 확인 해봐라 https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 플로이드-워셜 알고리즘 - 나무위키 이 저작물은 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 ..

문제 요약 알고리즘 분류: BFS 난이도: Gold5 문제내용: 위치가 X일때 X - 1, X + 1 이동하면 1초 X * 2는 0초 걸린다. 현재위치 N일때 K까지 이동하는데 최소 시간을 구해라 사이트: https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제풀이 이번에는 문제 유형은 그래프 탐색 관련 문제이다. 다이스트라 알고리즘으로도 풀수 있는데 그보다 구현이 더 쉬운 BFS로 풀수 있다. BFS 알고리즘 관..

이론 이번에 볼 자료구조는 넓이 우선 탐색(BFS)이다. 깊이 우선 탐색은 영어로 Breadth First Search이고 줄어서 BFS라고 많이 부른다. 그래프 탐색 알고리즘 중 하나인데 그래프 말고도 트리에서도 적용이 된다. 반대로 넓이 우선 탐색(BFS)도 있는데 코드 테스트에서도 BFS 관련 문제가 많이 나온다. 그래서 BFS알고리즘은 다른 알고리즘 보다 많이 공부해야되고 관련 문제들 많이 풀어야 한다. BFS 알기 위해서는 트리, 그래프, 큐 세가지 이론을 우선 적으로 알아야 한다. 그리고 그래프 전체적으로 탐색할때 DFS랑 BFS 속도 차이는 크게 없는 BFS가 속도가 더 빠르기 때문에 BFS 확실하게 숙지해야한다. 자세한 내용은 아래사이트에 찾아 보면된다. 시간되면 자세하게 설명하겠습니다. ..

문제 요약 알고리즘 분류: 트리, DFS 난이도: Gold4 문제내용: 노드와 가중치가 주어진다. 노드간의 가장 긴 길이를 구해라. 사이트: https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제풀이 이번에는 문제 유형은 트리와 DFS을 요구하는 문제이다. 트리와 DFS 알고리즘에 대한 설명은 아래에 있으니 참조하면된다. 트리 : https://jih3508.tistory.com/87 [알고리즘 이론] 트리(Tree) 이론 이..