[java] 프로그래머스 (구명보트) Level 2

Problem : https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr Approach N kg의 하중을 견디는 보트를 최소로 사용하여 모든 사람을 구출하는 문제이다. 일단 사람들의 몸무게를 오름차순으로 정렬한다. 그리고 밑의 단계를 반복한다. 구출하지 못한 사람들 중, 몸무게가 가장 큰 사람과 작은 사람의 합이 보트의 하중 기준치를 넘긴다면, 가장 큰 사람만 태운다. 구출하지 못한 사람..

→2021.01.06

Algorithm/Programmers

[java] 프로그래머스 (위장) Level 2

Problem : https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr Approach 조합의 수학적 규칙을 알고 있다면 쉽게 풀 수 있는 문제이다. N개의 옷이 있을 때, 옷을 고를 수 있는 경우의 수(입지 않는 경우도 포함)는 N+1가지다. 그래서 M종류의 옷이 각각 N1, N2, ... , Nm개씩 있을 때, 옷을 고를 수 있는 경우의 수(입지 않는 경우도 포함)는 (N1 + 1) * (N2 + 1) * ... * (Nm + 1) - 1(옷을 하나도 안입는 경우) 이다. 위 규칙만 안다면 각각 옷의 개수가 몇개인지만 판별하면 된다. 필자는 HashMap을 사용하여 옷의 개수를 카운팅하기가 편했다..

→2021.01.04

Algorithm/Baekjoon Online Judge

[java] 백준 1956 (운동) Gold 4

Problem : https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net Approach 최단경로 사이클을 찾는 문제이다. 따라서 플로이드 와샬(Floyd Warshall) 알고리즘을 사용하여야 한다. 참고로 1:N 최단경로 문제는 다익스트라 알고리즘을, 음수사이클을 찾을 때엔 벨만-포드 알고리즘을, N:N 최단경로 문제는 플로이드 와샬 알고리즘으로 접근하면 용이하다. 이 문제에서는 각 노드 A에 대하여 A에서 시작하..

→2021.01.04

Algorithm/Baekjoon Online Judge

[java] 백준 10217 (KCM Travel) Gold 1

Problem : https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net Approach 이 문제는 다익스트라 알고리즘과 DP를 같이 사용해서 풀어야했다. 인접리스트를 이용하여 그래프를 구성하였으며, 시간순 오름차순(시간이 같으면 비용순 오름차순)으로 구성하였다. 그런 후, 시작점 1부터 다익스트라 알고리즘을(BFS: PriorityQueue 이용) 적용하여, 비용을 초과하지 않는 선에서 모두 갱신해주었다. 다익스..

→2021.01.04

Algorithm/Programmers

[java] 프로그래머스 (전화번호 목록) Level 2

Problem : https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr Approach 처음엔 임의의 문자열 하나 A를 나머지 문자열(B, C, D, ...)에서 찾는 indexOf() 를 활용하여 반환값이 0인 것을 찾는 naive한 방법을 사용했었다. (indexOf()의 반환값이 0이면, 그 문자열로 시작한다는 뜻이므로) 그래서 Set 에 주어진 문자열을 모두 넣은 후, 하나씩 검사하는 방식을 썼었다. 이..

→2021.01.03

Algorithm/Baekjoon Online Judge

[java] 백준 11404 (플로이드) Gold 4

Problem : https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Approach 1 대 N 최단 경로를 구할 때에는 다익스트라(Dijkstra) 알고리즘을 사용하면 된다. N 대 N 최단 경로를 구할 때에는 플로이드 와샬(Floyd Warshall) 알고리즘을 사용하면 된다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택하며 최단경로를 구성해 나갔다면, 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 다음과 같은 ..

→2021.01.03

Algorithm/Baekjoon Online Judge

[java] 백준 11657 (타임머신) Gold 4

Problem : https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net Approach 도시 to 도시 의 최단경로비용을 구하는 문제인데, 음수 사이클이 존재할 수도 있는 문제이다. 음수사이클이 존재할 수 있으므로, 다익스트라 알고리즘은 사용이 불가능하다. 문제에서 의도한 바는 벨만-포드(Bellman-Ford) 알고리즘이므로 필자도 그 방법을 이용했다. 벨만-포드 알고리즘은 최단거리로 목..

→2021.01.03

Algorithm/Programmers

[java] 프로그래머스 (H-Index) Level 2

Problem : https://programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr Approach 이 문제에 있어서 주의할 점은 답이 citations에 없는 요소가 될 수 있다는 점이다. 예를 들어 citations = {6, 6, 6, 6} 이라면 답은 4가 된다. 필자는 citations 배열을 오름차순 정렬 한 후, 배열안에 i보다 크거나 같은 수가 i개 있는지를 검사하여, 가장 큰 i..

→2021.01.03

Algorithm/Programmers

[java] 프로그래머스 (큰 수 만들기) Level 2

Problem : https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr Approach (Wrong) 처음엔 주어진 문자열로 만들 수 있는 모든 수를 만들어 가장 큰 값을 저장해서 풀면 된다고 생각했다. 그러나 주어진 문자열의 길이가 최대 1,000,000자리 이하인 숫자이므로 당연하게 TLE, RTE를 받았다. Approach (Correct) 주어진 문자열에서 K개를 지워 가장 큰 수를 만들려면 앞자리 수가 클수록 좋다. 그렇다면 앞자리가 커질 수 있게, 앞의 수가 뒤의 수보다 작으면 삭제하면 된다. -> 언제까지? K개까지만 (K개만 지울 수 있으니까) 작지 않다면 그 뒤에 붙인다...

→2021.01.01

Algorithm/Baekjoon Online Judge

[java] 백준 9370 (미확인 도착지) Gold 2

Problem : https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net Approach 다익스트라 알고리즘을 이용하여 푸는 문제이다. 처음 문제를 이해할 때 g나 h로부터 갈 수 있는 노드들을 구하는 문제라고 이해를 했었다. 문제에서 요구한 것을 간단히 쉽게 말하면, 시작점 s에서 임의의 노드 X로 최단거리로 가는 길에 무조건 g-h 혹은 h-g가 있는 노드들을 구하는 것이다. 예를 들어, s = 1, g = 3, h =4 라고 할 때, 1에서..

→2021.01.01

티스토리툴바