Algorithm/Programmers

    [java] 프로그래머스 (등굣길) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (등굣길) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr Approach 간단한 DP문제이다. 주의할 점은 문제에서 주어진 예시그림과 주어진 데이터가 불일치한다는 점을 알고 가야한다. 문제의 그림에서는 m = 4, n = 3이지만, 3 x 4 지도가 나와있어 n이 행의 개수, m이 열의 개수라고 생각할 수 있겠지만, 그렇게 푼다면 런타임에러가 계속 뜰 것이다. m을 행의 개수, n을 열의 ..

    [java] 프로그래머스 (여행경로) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (여행경로) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr Approach DFS 를 활용하여 풀이가 가능한 문제이다. 이름의 알파벳 순서가 앞서는 경우부터 방문해야 하므로 방문공항기준 오름차순으로 정렬하고 시작한다. 출발지는 항상 ICN 이므로 ICN을 출발지로 하여 DFS를 수행한다. 티켓을 모두 사용해야 하므로, 시작공항을 제외한 방문공항은 티켓의 개수와 같다.를 이용하여, 티켓을 처음 다 썼을 때의 경로를 ans에 담..

    [java] 프로그래머스 (입국심사) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (입국심사) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr Approach 이분탐색(이진탐색)을 이용하는 문제였다. 주의할 점은 모든 자료형을 long으로 해줘야 런타임에러가 발생하지 않는다. 일단 이진탐색을 가능하게 하기 위해 정렬을 한다. 그리고 시간을 이분하면서 주어진 시간으로 몇명의 사람을 처리할 수 있는지를 체크한다. 주어진 사람 수 n미만 이면 시간이 더 필요하므로 반으로 나눠진 시간의 오른쪽..

    [java] 프로그래머스 (이중우선순위큐) Level 3
    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이다. 간단하게 설..

    [java] 프로그래머스 (정수 삼각형) Level 3
    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] 이다. 주의할 점은 삼각형의 변에 해당하는 경우에는 오는 경로가 하나 뿐이므로 예외적으로 처리해 주어야한다. 삼각..

    [java] 프로그래머스 (단속카메라) Level 3
    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에 저장해 놓고, 다음 차량들의 (진입지점 ~ 나간지점) 과의 겹치는 부분이 있는지를 검사하였다. 겹치는 부분이 있다면, 그 범위를 갱신하고 추가한다. 그리고 원래 있던 범위를 삭제한다.(이유..

    [java] 프로그래머스 (디스크 컨트롤러) Level 3
    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에 대해서는 따로 설명하진 않겠지만, 간단하게 작업 큐 안에 있는 프로세스 중 가장 수행시간이 짧은 것을 먼저 수행하는 기법이다. 평균 대기시간의 감소 효과를 볼 수 있다...

    [java] 프로그래머스 (가장 먼 노드) Level 3
    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이 ..

    [java] 프로그래머스 (단어 변환) Level 3
    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을 사용해야 하나 싶었지만 주어진 파라미..

    [java] 프로그래머스 (섬 연결하기) Level 3
    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일 경우 크루스칼 알고리즘을 사용한다. 나는 크루스칼 알고리즘을 사용하여 문제를 풀었다. 크루스칼 알고리즘을 대략적으로 설명하자면 다음과 같다. 모든 간선을 비용 오름차순으로 정렬한다. (여기서는 ..

티스토리툴바