코딩브론즈

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 0) 변수 설정 N : map의 크기 fuel : 연료 map : 지도 (N by N) tr, tc : 택시의 위치 distanceMap[r][c] : 현재 택시 위치에서 (r,c) 까지의 거리. 못 가는 경우가 있으므로 -1로 초기화 한다. isVisited[r][c] : (r,c) 위치를 방문했는지 체크 1) 입력값을 담을 Passenger 클래스를..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 0) 상어의 인덱스를 담을 map_idx[][]와 상어의 크기를 담을 map_z[][]를 생성하고 입력값을 기반으로 초기화한다. 1) 입력받은 상어들을 List에 담는다. Shark 클래스는 r, c, s, d, z, isDead로 이루어져 있다. 1-1) 상어는 1번부터 존재한다. List의 인덱스를 상어의 번호로 저장하기 위해 죽은 상어를 List에 최초 한번 add ..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 1) PriorityQueue 를 2개 사용한다. (최대힙, 최소힙) 2) 입력받은 숫자를 하나씩 넣는다. 2-1) 맨 처음 maxHeap이 비어있을경우 maxHeap에 우선적으로 넣는다. 2-2) 들어올 숫자가 maxHeap의 peek 값보다 작으면 무조건 maxHeap에 넣는다. 만약 maxHeap의 크기가 minHeap의 크기 + 2 보다 커지면 maxHeap의 peek..

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 풀이 1) 구간 합 배열(sum[])을 만든다. sum[i] : 0 부터 i 까지의 합. 2) a가 1 일 경우 2-1) 변경된 숫자의 번호와 차이값을 List에 저장한다. (인덱스, c - arr[i]) 3) a가 2 일 경우 3-1) 숫자 변경을 배제한다면 b~c 의 구간합은 sum[c] - sum[b-1] 3-2) list를 순회하며..

https://www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 풀이 1) 주어진 수영장 벽의 최대 높이 maxHeight 구하기 2) 1부터 maxHeight 까지 for문을 돌려서 수영장 벽의 높이와 같은 노드를 찾아낸다. 3) 해당 노드의 좌표에서 bfs 탐색을 한다. 3-1) 물은 위에서 아래로만 흐른다. 따라서 현재 높이 h 보다 작거나 같은 노드를 탐색한다. 3-2) 이때 지나간 경로를 Queue를 통해 저장해 놓는다. (pa..

https://www.acmicpc.net/problem/1035 1035번: 조각 움직이기 최대 5개의 조각이 있는 5×5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net 풀이 0) 주어진 조각의 총 개수를 구한다. 1) 조각의 총 개수로 만들수 있는 모든 경우를 구한다.(DFS) 2) 위의 경우 중 모든 조각들이 이어져 있는 경우를 구한다. 2-1) 임의의 조각 하나에서 BFS. (이어진 조각들의 개수 == 총 조각의 개수) 인 경우 모든 조각이 이어져있는 것이다. 3) 원본에서 2)의 경우로 옮기는 최소 비용을 구한다. 3-1) 이때 이동의 기준은 가장가까운..

서론 - 이전 포스트에서 순수 Java만 사용하여 비즈니스 요구사항에 맞게 프로젝트를 설계하였다. - 이제 새로운 할인 정책을 개발하여 프로젝트를 확장해보자. - 이때, 객체 지향의 설계 원칙을 잘 준수했는지 확인해 보자. 1. 새로운 할인 정책 개발 - 상황 : 서비스 오픈 직전에 할인 정책에 대한 기획자의 요구사항이 변경되었다. 기획자 : 고정 할인 정책(1000원)이 아니라 정률 할인 정책(10%)으로 바꿉시다! 개발자 : ㅠㅠ RateDiscountPolicy 추가 새로운 할인 정책을 설계했으면 이제 OrderService에서 기존에 사용하던 FixDiscountPolicy대신 RateDiscountPolicy로 대체한다. 이때, 문제점이 발견된다. 분명히 역할과 구현을 충실하게 분리했다. 다형성..

최근 백준 - 수 정렬하기 2 라는 문제를 풀다가 이상한 상황을 겪었다. Link : https://www.acmicpc.net/problem/2751 아니 배열에 담아 Arrays.sort() 해서 출력하면 시간초과가 나고 ArrayList에 담아 Collections.sort()를 하니까 통과되는 것이다!!! 덕분에 새로운 사실을 알게 되었다. 바로 Java에서 제공해주는 API 중 Arrays.sort() 와 Collections.sort() 가 서로 다른 정렬 알고리즘으로 구현되어있다는 것이다. Arrays.sort() : DualPivotQuicksort Arrays.sort()의 메서드를 클릭했을 때를 보면 다음과 같이 나온다. 저 DualPivotQuicksort를 클릭하니 4000라인의 코..