[Java] 백준 1043 (거짓말) Gold 4

Problem : https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net Approach union-find라는 알고리즘을 사용하는 문제였다. 같은 집합으로 묶는 개념이며 알고리즘에서 자주 사용하는 방법이므로 숙지해두면 좋다. 다른 union-find에서와 마찬가지로 parent[] 배열을 사용한다. 로직은 다음과 같다. 진실을 아는 사람들은 parent[x] = x로 초기화를 하고, 진실을 모르는 사람들은 parent[x] = -1로 초기화를 한다. 각 파티마..

→2021.03.29

Algorithm/Baekjoon Online Judge

[Java] 백준 1016 (제곱 ㄴㄴ 수) Gold 1

Problem : https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net Approach 에라토스테네스의 체 라는 소수 판별 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제이다.(주관적 생각) 개인적으로 나는 에라토스테네스의 체라는 알고리즘을 사용한다는 것을 바로 생각했고, 구현하는 데에도 큰 어려움이 있지 않았지만 Gold 1이라는 난이도가 매겨져있었다. 조건을 좀 따져야 하긴 한다. 조건을 먼저 살펴보자. (자료형은 무조건 long ..

→2021.03.28

Algorithm/Baekjoon Online Judge

[Java] 백준 1005 (ACM Craft) Gold 3

Problem : https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net Approach 위상정렬(Topological Sort)의 연습문제이다. 위상정렬 자체에 대해서는 간단히 설명하겠다. 알고리즘에서 꽤나 자주 나오는 개념이므로 숙지해두면 좋을 것이다. DAG(Directed Acyclic Graph: 방향성이 있고 싸이클이 없는 그래프)에 순서가 곁들여져 있는 경우, 위상정렬을 사용해 볼 수 있다. 위상정렬에서는 중요한 개념 하나가 있다. ..

→2021.03.28

Algorithm/Programmers

[Java] 프로그래머스 (하노이의 탑) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/12946 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대 programmers.co.kr Approach 많이 알려져 있는 재귀문제, 하노이의 탑 오리지널 문제와 크게 다르지 않은 문제이다. 하노이의 탑의 주요 알고리즘은 다음과 같다. n개의 원판을 1에서 3으로 옮길 때, 출발지(1)에 있는 n - 1개 원판을 경유지(2)로 옮긴다. 출발지(1)에 있는 1개 원판을 도착지(3)로 옮긴다. -> 여기서는 정답..

→2021.02.24

Algorithm/Programmers

[Java] 프로그래머스 (최고의 집합) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족 programmers.co.kr Approach 약간 Greedy한 성격의 문제였다. 일단, 합이 s인 n개의 숫자 곱이 크려면 n개의 숫자가 s / n 과 가까운 숫자여야 한다. s 를 n으로 나눈 나머지를 rest, 몫을 value 라고 할 때, 곱했을 때 최대가 되려면 rest개 만큼 value + 1인 숫자가 존재하고, 나머지 개수를 value가..

→2021.02.23

Algorithm/Baekjoon Online Judge

[Java] 백준 1107 (리모컨) Gold 5

Problem : https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net Approach BruteForce 문제이다. 우선 0부터 목표 채널 * 2 까지 만들 수 있는 숫자인지를 판단하고, 만들 수 있는 숫자라면, 숫자를 만들 때의 클릭 수와 만든 숫자와 목표 채널과의 차이(+-클릭 수)를 더한 것들 중 최솟값을 찾으면 된다. 주의할 점은, 시작 채널이 100이기 때문에 최소 100까지는 숫자를 만들 수 있는지 판단해야 한다. isP..

→2021.02.21

Algorithm/Programmers

[Java] 프로그래머스 (줄 서는 방법) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/12936 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr Approach 각 자리를 정하는 나름의 규칙을 찾고 그에 맞게 구현을 해야했던 문제이다. 참고로 순열을 이용한 풀이는 정확성 테스트는 통과되나, 효율성 테스트에서 통과되지 못한다. 문제에서 주어진 n = 3, k = 5인 케이스를 예로 들겠다. 3명이 줄을 설 수 있는 방법은 다음과 같이 6가지이다. [1, 2, 3] [1, 3..

→2021.02.20

Algorithm/Programmers

[Java] 프로그래머스 (야근 지수) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr Approach 우선순위 큐(PriorityQueue)를 이용하여 문제를 풀었다. 자바의 PriorityQueue 는 Heap으로 내부동작이 이루어져서 시간복잡도가 O(NlogN)이다. N이 최대 1,000,000 이라 시간초과가 나지 않을까도 싶었지만 다행이도 시간초과는 나지 않았다. 우선순위 큐를 큰 숫자가 우선이 되게끔 Co..

→2021.02.19

Algorithm/Programmers

[java] 프로그래머스 (멀리 뛰기) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr Approach 매우 간단한 DP 문제이다. DP[i] 를 i 칸에 도달할 수 있는 방법의 수라고 하였을 때, i 칸에 도달할 수 있는 방법은 (i - 2 칸에서 2칸으로 움직였을 경우) + (i - 1 칸에서 1칸으로 움직였을 경우)이다. 위의 문자대로 DP[i] = DP[i - 2] ..

→2021.02.17

Algorithm/Programmers

[java] 프로그래머스 (방문 길이) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr Summer/Winter Coding(~2018) 문제였다. 두 가지 방법이 있지만 나는 여기서의 2번째 방법을 이용했다. 좌표평면 크기의 visited 배열을 선언하여 실제로 방문하였는지를 체크한다. HashSet을 이용하여 선분을 나타내는 무언가를 set에 양방향으로 추가하고 size / 2한다. 2번 풀이로 푸는게 매우 간단하다. 중복을 걸러야 하므로 int[] 배열 보다는, 두 점을 String 으로 묶어 set에 양방향으로 넣은 후, size / 2를 하면 정답이 된다. Code import org.junit.jup..

→2021.02.17

티스토리툴바