전체 글

Algorithm/Programmers
[java] 프로그래머스 (이중우선순위큐) Level 3
Problem : https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr Approach 힙(Heap)이나 우선순위큐(PriorityQueue)를 사용하여 풀이가 가능한 문제이다. 나는 처음 문제를 보고 PriorityQueue와 Deque을 생각했다. 그러나 하나의 PriorityQueue에서는 최솟값과 최댓값을 한 번에 처리할 수 없었고, Deque는 정렬된 상태를 유지하는 방법을 찾지 못했다. 최소한의 자료구조를 가지고 문제를 풀고 싶었다. 내가 필요한 자료구조는 정렬된 상태를 유지하는 것과 최댓값과 최솟값을 뽑을 수 있는 자료구조였다. 그래서 생각한 것이 TreeSet이다. 간단하게 설..
→2021.02.02
Algorithm/Programmers
[java] 프로그래머스 (정수 삼각형) Level 3
Problem : https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr Approach 대표적인 DP 문제이다. 문제에서 보이기는 정삼각형이지만, 배열로 구현하게 되면 왼쪽 하단이 직각을 이루는 직각삼각형이 된다. 따라서 점화식도 간단하게 유추가 가능하다. 점화식은 DP[i][j] = max(DP[i - 1][j - 1], DP[i - 1][j]) + triangle[i][j] 이다. 주의할 점은 삼각형의 변에 해당하는 경우에는 오는 경로가 하나 뿐이므로 예외적으로 처리해 주어야한다. 삼각..
→2021.02.02
Algorithm/Programmers
[java] 프로그래머스 (단속카메라) Level 3
Problem : https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr Approach 은근히 이렇게 범위가 주어지는 문제가 까다로운 것 같다. 나는 진입지점 기준 오름차순을 한 후, 새로 놓아야 할 카메라의 범위를 구하였다. 그 범위 중 한 곳에 카메라를 놓으면 된다는 식으로 문제를 풀이했다. 카메라를 놓아야 할 범위들을 list에 저장해 놓고, 다음 차량들의 (진입지점 ~ 나간지점) 과의 겹치는 부분이 있는지를 검사하였다. 겹치는 부분이 있다면, 그 범위를 갱신하고 추가한다. 그리고 원래 있던 범위를 삭제한다.(이유..
→2021.01.31
Algorithm/Programmers
[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

• 이전
• 1
• ···
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• ···
• 34
• 다음