백준

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 사이의 숫자들을 이진수로 바..

https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 풀이 사용한 알고리즘 : 이진 탐색, LIS(Longest Increasing Subsequence) 풀이 전략 1. 첫 번째 입력한 수를 비어있는 result 리스트에 추가한다. 2. i 번째 입력한 수가 result의 맨 끝값보다 크면 result 리스트에 추가한다. 3. i 번째 입력한 수가 result의 맨 끝값보다 작으면 result 내부를 이진탐색하여, 해당 수보다 크거나..

https://www.acmicpc.net/problem/2550 2550번: 전구 첫 번째 줄에는 가장 많은 전구가 켜지게 하는 스위치의 수를 출력한다. 두 번째 줄에는 눌러야 하는 스위치의 번호를 오름차순(번호가 커지는 순서)으로 빈칸을 사이에 두고 하나의 줄에 출력 www.acmicpc.net 풀이 사용한 알고리즘 : LIS 풀이 전략 import sys input=sys.stdin.readline N=int(input()) switch=list(map(int,input().split())) bulb=list(map(int,input().split())) arr=[] for i in switch: arr.append(bulb.index(i)) length=[0]*N preNode=[] for i i..

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 사용한 알고리즘 : LIS (Longest Increasing Subsequence) 원소가 N개인 배열에서 일부 원소를 골라내서 만든 부분수열 중 오름차순을 만족하며, 그 길이가 최대인 수열을 LIS라고 한다. 풀이과정 1. 입력값을 저장할 arr, 특정 인덱스에서 내림차순의 LIS 값을 저장할 length 리스트를 정의한다. 2. 0~N-1 인덱스를 돌며 특정 인덱스에서 해당 ..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 사용한 알고리즘 : 풀이1_ 라인 스위핑, 풀이2_투 포인터 ※풀이 전략 2가지 전략으로 풀이를 해보았다. 풀이1. (라인 스위핑) 1. 입력받은 각각의 수를 튜플 형식으로 리스트에 추가한다. 만약 음수면 (abs(수), -1)로, 양수면 (수, 1) 형식으로 리스트에 추가한다. (abs는 절댓값 의미) 2. 리스트에 저장된 튜플들을 튜플의 첫 번째 원소로 ..