알고리즘,PS

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이 전형적인 이분탐색 문제이다. right left를 정해놓고 진행할때마다 점점 중간값으로 탐색하는 방식으로 하면된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import java.util.*; import java.io..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 풀이 TreeMap 으로 이진탐색을하여 이미 존재하는 숫자면 replace로 기존값 +1 처음 들어오는 숫자면 put을 하여 구성을 한 후 , containkey 함수를 호출하여 각 값을 출력하면된다. print함수를 사용하면 최악의 경우 50만번 출력을 해서 시간초과가 났었다. StringBuilder를 사용하여 한번에 출력할 것. 1 2 3 4 5 6 7..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 풀이 1. 정렬된 배열과 이분탐색으로 들어가야하는데 , 이를 보장하는 자료구조인 TreeSet을 이용한 풀이이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import java.util.*; import java.io.*; public class Main{ public static void main(..

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 문제 풀이 기본적으로 풀이는 우선순위 큐를 이용한 다익스트라 방법이랑 같다. (포장 하지 않을 경우) 하지만 여기선 추가되어야하는 부분이 거리부분인 distance[] 배열을 2차원으로 만드는것이다. 도로포장을 하지않을때 부터(0) 포장했을때(k)까지 의 거리비용이 달라지기 때문 따라서 distance[도시의갯수][도로포장 개수] 로 해야한다 => distanc..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 풀이 풀이 방식은 이전 포스팅과 동일하다. https://katastrophe.tistory.com/19 [BOJ] 백준 [1753] 최단경로 JAVA https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1..

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 문제 풀이 nlogn 시간복잡도인 우선순위큐를 이용한 다익스트라 기본 풀이다. 간선의 가중치 낮은 순으로 우선순위큐에 들어가기때문에 n^2 방식인 최소비용탐색하는 시간이 들지 않기때문 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 ..

https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제 풀이 아 .. 비트마스킹이란걸 몰라서 한참을 헤매었다.. 결론적으로는 열쇠의 유무를 2^6 = 64 , 즉 visit배열을 3차원으로 열쇠유무까지 추가하면 => visit[높이][너비][열쇠] visit[h][w][64] 이렇게 두고 풀어야 한다는 것이다. 열쇠면 | 연산으로 추가 , 문 이면 & 연산으로 확인하는 식으로해서 탐색을 하면 된다. 1 2 3 4 5..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 풀이 단순 DFS 시뮬레이션 문제이다. 특이한점은 dfs 안의 다른 조건으로 재귀호출을 두 번 한다는것. map[y][x] = 1 : 벽 map[y][x] = 2 : 청소 된 상태로 만들기 map[y][x] = 0 : 청소 안된 상태 문제에 나와있는 조건을 따라서 탐색한 방향 nextX,nextY 가 청소되어있는지 확인 후 움직이거나 청소가 다 되어 있거나 벽인경우 , 후진 할 수 있다면 ..