알고리즘||코딩테스트/백준

https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 사용한 알고리즘 : 투 포인터 풀이전략 1. 문자열의 시작점 인덱스를 start, 끝점 인덱스를 end로 둔다. 2. start 인덱스에 해당하는 문자와, end 인덱스에 해당하는 문자를 비교하여 일치하면 ++start, --end를 수행한다. 3. 만약 start 인덱스에 해당하는 문자와, end 인덱스에 해당하는 문자가 일치하지 않는다면 count를 1 증가시키고 start를 1 증가시켜 문자 하나를 제외한 경우와 e..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 사용한 알고리즘: BFS 풀이전략 문제를 풀기 앞서 이분 그래프가 어떤 구조인지 알고 있어야 문제 풀이가 가능하다. 위와 같은 그래프가 있을 때, 인접한 노드끼리 서로 다른 색을 지니는 그래프를 이분 그래프라고 한다. 노드끼리 모두 연결되어 있지 않아도, 서로 인접한 노드끼리만 다른 색으로 구분될 수 있어도 이분그래프다. 이런 이분 그래프의 성질을 이용하여 BFS를 사용하면 문제를 풀 수 있..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 사용한 알고리즘: 플로이드 워셜(Floyd Warshall) 풀이전략 플로이드 워셜 알고리즘을 사용하여 모든 출발지에서 도착지까지의 최단 거리를 구한다. 단, 기존 플로이드 워셜 알고리즘에서는 자기 자신에게 가는 거리를 0으로 두고 알고리즘을 실행했지만 이 문제에서는 거리가 아닌 경로의 유무 판단이 중요 쟁점이기 때문에 모든 배열의 원소를 INF(무한)으로 초기설정한다. 그리고 입력에서 1로 경로가 있는 경우에만 배열 ..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 사용한 알고리즘 : 플로이드 워셜 알고리즘(Floyd Warshall) 풀이전략 전형적인 플로이드 워셜 알고리즘을 사용한 문제이다. 플로이드 워셜은 A에서 B로 가는 거리를 D(AB)라고 할 때, 다른 노드 K를 지나쳐 가는 것과 현재 거리를 비교하여 더 짧은 거리를 D(AB)에 저장시키는 알고리즘이다. 예로 D(AB) = Math.min(D(AB),D(AK)+D(KB))처럼 특정 노드 K를..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 사용한 알고리즘 : 데익스트라(Dijkstra) 풀이전략 전형적인 데익스트라 알고리즘을 사용한 최단거리 문제이다. 다만 계속해서 시간초과가 발생해서 골머리였는데, 이유는 ArrayList가 아닌 LinkedList 사용 때문이었다. ArrayList / LinkedList 검색 최대 시간 복잡도 ==> O(1) / O(..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 사용한 알고리즘 : 데익스트라(Dijkstra) 풀이전략 전형적인 데익스트라 알고리즘 문제이다. 우선순위 큐를 사용하지 않고, 각 노드에서 최단거리 노드를 구할 때 함수를 사용하면 시간초과가 발생했다. 따라서 우선순위 큐를 구현하고 거리에 따라 오름차순 정렬되도록 해야한다. 1. 시작 노드를 우선순위 큐에 먼저 inqueue하고 해당 노드를 방문처리, dis..

https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 사용한 알고리즘 : 정렬 풀이전략 문제 자체는 어렵지 않은데 JAVA에서 최적화된 정렬방법 및 입출력을 사용하지 않으면 시간초과가 나오는 문제였다. 문자열을 출력할 때, 한 줄 한 줄 출력을 하기보다 StringBuilder를 사용하는 것이 더 효율적이었다. StringBuilder는 출력해야할 문자열들을 하나로 묶어줬다가 한번에 출력시키는 역할 수행한다. 또한 정렬에서 Array..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 풀이 사용한 알고리즘 : 세그먼트 트리 풀이 전략 세그먼트 트리란 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조로 위와같은 구조를 가진다. 최댓값을 저장하는 트리 초기 설정 코드 static int max_init(int arr[], int node, int nodeLeft, int nodeRight){ if(nodeLeft==nod..

https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 풀이 사용한 알고리즘 : BIT(Binary Index Tree, segment tree) 풀이 전략 바이너리 인덱스 트리에 대한 이해가 있어야만 풀 수 있는 문제이다. 바로 전에 풀었던 구간합 구하기와 풀이 방법이 동일했다. 바이너리 인덱스 트리와 풀이 방법에 대해 자세히 적어놓았으니 아래 링크를 참고바란다. https://chaechaeros.tistory.com..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 사용한 알고리즘 : BIT(Binary Index Tree) 풀이전략 BIT 알고리즘에 대해 이해하고 있어야만 이 문제를 풀 수 있다. 따라서 BIT 알고리즘에 대해 설명하도록 하겠다. 1. 트리 구조 만들기 원소가 8개인 리스트가 주어졌을 때, 해당 리스트를 바이너리 인덱스 트리로 만들어 보겠다. 1~8 사이의 숫자들을 이진수로 바..