https://www.acmicpc.net/problem/1931 그리디(greedy), 탐욕 알고리즘은 현재 가장 최선의 선택을 하는 알고리즘이다.제약 조건에 벗어나지만 않으면 되어서 "항상 최적의 해를 보장하지 않는다" 라는아주 마음에 안 드는(?) 단점이 있다. 사실 내가 그리디 알고리즘을 별로 선호하지 않는데..그래도 문제는 풀어야겠지 에효 백준 1931번 회의실 배정 문제는 그리디 알고리즘을 사용하면 된다.  문제  설명 회의를 가장 많이 진행하기 위해서는 회의의 끝나는 시간이 중요 키포인트다. 회의 시작 시간과 끝나는 시간이 같을 수 있다고 문제에 주어졌는데,예를 들어 (11, 11), (10, 11) 2개의 회의가 있다면 2개 모두 진행이 가능하지만(11, 11)이 먼저 입력되면 나중에 나온..

https://www.acmicpc.net/problem/2178 백준 2178번 미로 탐색 간단한 너비 우선 탐색(bfs)으로 구현이 가능한 문제였다. 너비 우선 탐색(breadth-first search) 알고리즘 특징은 그래프의 완전 탐색 방법 중 하나로,가까운 노드를 먼저 방문한다. 스택, 재귀를 사용하는 깊이 우선 탐색(depth-first search)과 다르게 너비 우선 탐색은선입선출(First In First Out) 방식이므로 큐를 사용해서 구현한다.  문제    설명 출발점 (0, 0)에서 상,하,좌,우를 봤을 때, 1이 있으면 현재 내가 있는 값 + 1 을 해준다.  도착점 (N-1, M-1)에 도달했을 때 그 값을 출력해 주면 끝. 코드가 짧고 어렵지 않으므로 바로 소스를 보며 이해..

https://www.acmicpc.net/problem/1753 백준 1753번 최단경로 문제는 다익스트라 알고리즘을 사용했다. 참고로 다익스트라 알고리즘은 출발 노드에서 모든 노드 간의 최단 거리를 구하며 엣지는 양수이어야 한다. 문제  설명  다음은 1753번 문제에 대한 풀이 순서이다. 1) 최단 거리 리스트 D[N]은 1차원 리스트로 출발 노드는 0, 그 외는 모두 무한대로 초기화한다. 2) D[N]에서 현재 값이 가장 작은 노드를 골라서 연결된 다른 노드의 값을 없데이트 한다.최단 거리 업데이트는 min(현재 노드 최단 거리 값 + 가중치, 다음 노드 최단 거리 값) 으로 비교한다. 3) 방문 리스트 visited[]를 만들어서 재방문 하지 않고 모든 노드가 선택될 때까지 반복한다. 글만 보면..

http://https://www.acmicpc.net/problem/1717  백준 1717번 집합의 표현은 유니온 파인드(union find) 알고리즘을 확실히 알게 해주는 문제였다. 문제  설명 문제 1717번 예제로 유니온 파인드에 대해 설명하자면, 1)  대표 노드를 저장하는 1차원 리스트가 필요하며 처음에는 연결되어 있지 않으므로자신의 인덱스 값으로 초기화한다.  2) 2개의 노드 각각의 대표 노드를 찾아 union 연산으로 연결한다.예를 들어 두 번째 줄 입력을 받아서 0일 때 union(1,3) 을 해주면 arr[3] = 1로 값이 변경된다.이때, 작은 값을 대표 노드로 본다. 유니온 파인드 알고리즘에서 유의할 것은 입력 6번째 줄 union(3,7) 인 경우다.5번째 줄까지 모두 진행되었..