Algorithm

[백준 - JAVA] 4375번 : 1

https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 조건 파악 및 접근 문제를 보고 이해하는데 살짝 시간이 걸렸는데 결국 주어진 n의 배수 중에서 1로만 이뤄진 n의 배수를 찾는 문제였다. 우선 2와 5로 나누어 떨어지지 않는다는 조건이 왜 붙었냐면, 소인수분해 시 2와 5가 있을 경우 그 중 작은 수 만큼 수의 낮은 자리수에 0이 생겨서 1로 나누어떨어지지 않게 된다. 즉, 위 조건은 언젠가 1로만 이루어진 n의 배수가 나타나는 것이 보장되었다고 얘기하는 부분이다. 해당 문제는 나머지 연산의 법칙을 ..

[백준 - JAVA] 2606번 : 바이러스

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 조건 파악 및 접근 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 컴퓨터는 100 이하는 갖지만 최대 간선 수는(n*(n-1)) / 2 이므로 4,950개까지 가능. 그래프 문제고 DFS, BFS을 활용하면 된다. 결국 1에 연결된 노드의 개수를 파악하라는게 문제의 최종적인 질문. 풀이 1. BFS 풀이 2. union-find를 활용 union으로 "동일 집합..

[백준 - JAVA] 2470번 : 두 용액

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제를 파악하면서 투 포인터라는 것을 알고 분석을 해봤다. 2

[그래프/트리 - 응용] Union-Find / 서로소 집합

Union-Find란? 백준 문제를 풀 때 DFS로 풀었던 문제를 다른 사람들은 Union-Find로 풀었길래 정리. 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net Union-Find 알고리즘 대표적 그래프/트리 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있다. 상호 배타적 집합(Disjoint-set)이라고도 하며 서로소 집합으로 불린다. 서로소인 부분 집합의 표현 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은..

[이분탐색 - 응용] parametric search 개념 및 문제 풀이

백준 1654 - 랜선 자르기 문제본문 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 개요 parametric search는 이진 탐색의 원리를 이용해서 최적의 해를 구하는 방법이다. 최적화 문제를 결정 문제로 바꾸어 푸는 것이다. 정렬된 어떠한 리스트에서 탐색 기준을 결정해 놓고 특정 위치에서 기준에 만족하지 않는 다면 그 아래있는 위치들도 모두 기준에 통과하지 못할 것이라는 확신으로 문제를 해결하는 것이다. O(logN + a)의 시간 복잡도를 가진 parametric sea..

[알고리즘-기초] 완전 탐색, 브루트 포스(Brute Force)

완전 탐색, 브루트 포스란?Brute Force의 사전적 의미를 보면 다음과 같다. brute: 무식한 +  force: 힘    무식한 힘으로 해석할 수 있다. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.  장점알고리즘을 설계하고 구현하기 쉽다.복잡한 알고리즘 없이 빠르게 구현할 수 있다.   단점알고리즘 실행 시간이 매우 오래 걸린다.메모리 효율 쪽으로 매우 비효율적이다.  종류 브루트 포스는 기본 구조는 크게 선형 구조와 비선형 구조로 나눌 수 있다. 선형 구조 : 순차 탐색비선형 구조 : 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)심화 : 백트래킹(재귀)백트래킹과 DFS, BF..

최단 경로 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘)

최단 경로(Shortest Path) 알고리즘이란? 가장 짧은 경로를 찾는 알고리즘, '길 찾기' 문제로 불린다. 문제를 그래프로 표현하고 각 지점을 노드, 지점간 연결된 도로는 간선이라 한다. 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍이 그대로 적용된다. 다양한 사례가 존재하며, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 문제 형태가 정형화되어 있기 때문에 구현 부분은 비슷함 문제에 따른 외적인 조건만 챙겨서 풀이 ex) 한 지점에서 다른 특정 지점까지 최단 경로 구하기, 모든 지점에서 다른 모든 지점까지 최단 경로 구하기 등 1) 최단 경로 문제의 종류 단일 출발 (single-source) 최단 경로 어떤 하나의 정점에서 출발하여 나머지 모든 정점 까지의 최단 경로를 찾..

탐욕법(Greedy Algorithm)

이것이 코딩 테스트다 with 파이썬 정리 및 추가 내용 Greedy Algorithm이란? 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 예를 들어 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자. 이 문제를 해결하기 위해 몇 가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를..

시간 복잡도와 Big-O 표기

원문은 해당 페이지로 이동 알고리즘이란? Algorithm is a series of contained steps which you follow in order to achieve some goal, or to produce some output 알고리즘은 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미합니다. 삼성역에서 택시를 타고 강남역으로 향했는데 30분 걸렸다. 구글에서 알려주는 최단경로로 갔더라면 15분 내에 도착할 것이다. 레스토랑을 예약해서 가는 경우라던지 친구와 약속시간을 잡은 경우 우리에게는 시간은 항상 소중하다. 그래서 우리는 시간을 효율적으로 사용하기 위한 노력을 의식적으로 하고 있다. 컴퓨터 프로그래밍에서도 시간복잡도가 가장 낮은 알고리즘을 채택해 ..