[java] 프로그래머스 (디스크 컨트롤러) Level 3

Probelm : https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr Approach 이 문제는 간단히 비선점(Non-Preemption) CPU 스케줄링 기법 중 SJF(Shortest Job First)기법을 구현하는 문제이다. SJF에 대해서는 따로 설명하진 않겠지만, 간단하게 작업 큐 안에 있는 프로세스 중 가장 수행시간이 짧은 것을 먼저 수행하는 기법이다. 평균 대기시간의 감소 효과를 볼 수 있다...

→2021.01.31

Algorithm/Programmers

[java] 프로그래머스 (가장 먼 노드) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr Approach 주어진 그래프의 1번 노드에서 가장 먼 노드의 개수가 몇개인지를 찾는 문제이다. DFS로 풀면 같은 그래프라도 답이 달라질 수 있다. (정확한 것은 아니고 예상(?)) 예를 들어, (1, 2), (1, 3), (2, 3) 라면, DFS는 1 -> 2 -> 3 순으로 진행되어 노드 3이 노드 1로부터 2거리에 위치한다고 판단한다. 그러나 BFS는 1 -> 2, 1 -> 3 순으로 진행하여 노드 3이 ..

→2021.01.30

Algorithm/Baekjoon Online Judge

[java] 백준 17472 (다리 만들기 2) Gold 3

Problem : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net Approach 삼성 A형 기출문제라고 한다. 만만치 않았다. 푸는 도중에도 풀이가 길어져서 이렇게 풀어도 되는지에 대해 계속 생각하게 만들었다. 문제 풀이에 앞서 크게 3가지의 알고리즘이 사용된다. 주어진 섬들의 numbering -> BFS/DFS numbering된 섬들끼리의 거리 계산 -> BruteForce(행렬로 주어졌으므로 다른 방법은 제한적이다..

→2021.01.30

Algorithm/Programmers

[java] 프로그래머스 (단어 변환) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr Approach 문자열을 이용한 BFS/DFS 문제이다. 보통의 DFS/BFS 는 연결된 간선을 이용해 탐색을 수행하지만, 이 문제에서는 서로 다른 글자가 단 한글자일 경우에만 탐색이 수행되므로, 서로 문자가 몇개 다른지를 검사해주어야 한다. 처음엔 HashMap을 사용해야 하나 싶었지만 주어진 파라미..

→2021.01.29

Algorithm/Baekjoon Online Judge

[java] 백준 20040 (사이클 게임) Gold 4

Problem : https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net Approach Union-Find 알고리즘을 활용하여 풀 수 있는 문제이다. 주어진 그래프가 사이클을 이루지 않는다면, m개의 간선을 처리할 동안 두 노드의 부모가 항상 달라야한다. 만약 간선을 처리하는 중, 두 노드의 부모가 같은 것이 나온다면, 두 노드는 이미 하나의 집합으로 묶여있는 상태이고, 같은 집합에 간선을 추가한다는 것은 곧 사이클을 만든다는 뜻이 된다. 따라..

→2021.01.29

Algorithm/Programmers

[java] 프로그래머스 (섬 연결하기) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr Approach MST(Minimum Spanning Tree) 최소신장트리 관한 문제이다. MST 풀이 방법엔 프림(O(N^2)), 크루스칼(O(ElogE)) 알고리즘이 있다. 일반적으로 dense graph일 경우 프림을, sparse graph일 경우 크루스칼 알고리즘을 사용한다. 나는 크루스칼 알고리즘을 사용하여 문제를 풀었다. 크루스칼 알고리즘을 대략적으로 설명하자면 다음과 같다. 모든 간선을 비용 오름차순으로 정렬한다. (여기서는 ..

→2021.01.28

Algorithm/Baekjoon Online Judge

[java] 백준 4803 (트리) Gold 4

Problem : https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net Approach 트리의 기본성질을 이용한 문제이다. 트리의 경우 노드개수는 (간선의 개수 + 1)이다. 문제에서 각 테스트케이스마다 노드의 개수 n과 간선의 개수m이 주어진다. 노드가 연결되지 않은 경우도 있기 때문에, 모든 노드를 방문해 보아야한다. 또한, 양방향 간선으로 구성했기 때문에 주어진 그래프가 트리를 이룬다면 (간선의 개수 / 2 + 1)이 노드의 ..

→2021.01.28

Algorithm/Baekjoon Online Judge

[java] 백준 1450 (냅색문제) Gold 1

Problem : https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net Approach meet in the middle 알고리즘을 적용하여 각각을 완전탐색 후 이진탐색을 수행하는 문제이다. meet in the middle 알고리즘을 간단하게 말하면 주어진 범위를 반으로 나누어 각각 처리하는 알고리즘이다. 문제에서 주어진 N이 최대 30이므로 완전탐색을 수행하려면 2^30번의 연산이 필요하다. 2^30은 대략 10억이지만, 절반인 2^15은 ..

→2021.01.27

Algorithm/Programmers

[java] 프로그래머스 (네트워크) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr Approach 간단하게 BFS/DFS 를 활용하여 풀 수 있는 문제이다. 나는 BFS 를 사용하였다. 모든 노드에 대하여 BFS 를 수행한 후, 집합의 개수가 몇개인지를 판별해주면 된다. Code import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.Test; imp..

→2021.01.27

Algorithm/Programmers

[java] 프로그래머스 (자물쇠와 열쇠) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr Approach 2020 KAKAO BLIND RECRUITMENT 문제였다. 문제풀이의 핵심은 배열을 확장시키고, 흘러가듯 밀면서 비교한다는 점이다. 완전탐색으로도 통과는 가능하다고 한다.(?) TC에서 100ms 정도 걸린다는 글을 보았다. 원본 lock 배열에 홈의 크기 hole를 구한다. 원본 lock 배열에 상하좌우에 (key배열 사이즈 - 1) 만큼씩 padding을 주어 확장된 e..

→2021.01.26

티스토리툴바