Algorithm/Programmers

    [Java] 프로그래머스 (거리두기 확인하기) Level 2
    Algorithm/Programmers

    [Java] 프로그래머스 (거리두기 확인하기) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr Approach Greedy 한 BFS 문제이다. 2021 카카오 채용연..

    [Java] 프로그래머스 (게임 맵 최단거리) Level 2
    Algorithm/Programmers

    [Java] 프로그래머스 (게임 맵 최단거리) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr Approach 아주 기본적인 BFS 문제이다. BFS를 구현할 줄 안다면 풀 수 있는 문제이다. 추가적인 스킬은 필요하지 않은 것 같다. Code import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.Test; impo..

    [Java] 프로그래머스 (다단계 칫솔 판매) Dev-Matching 3
    Algorithm/Programmers

    [Java] 프로그래머스 (다단계 칫솔 판매) Dev-Matching 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr Approach 트리 를 구성할 수 있는지, 특정 노드를 시작으로 부모 노드들을 순회할 수 있는지가 핵심인 문제이다. 문제 풀이의 주요 로직은 다음과 같다. 트리를 구성하는 전처리 과정이 필요하다. 이 과정에서 트리를 구성함은 물론, 현재 노드 i에 대하여 부모 노드가 무엇인지도 저장해주어야 한다. 각 seller에 대하여 반복문을 돌린다..

    [Java] 프로그래머스 (행렬 테두리 회전하기) Dev-Matching 2
    Algorithm/Programmers

    [Java] 프로그래머스 (행렬 테두리 회전하기) Dev-Matching 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr Approach 행렬의 특정 부분을 회전시킴과 동시에, 그 영역에 있는 최솟값을 찾는 문제이다. 행렬 회전을 구현할 수 있어야 한다. 행렬 회전만 구현할 줄 안다면, 약간의 조건을 걸어 쉽게 풀이가 가능하다. 문제 풀이의 주요 로직은 아래와 같다. 좌상단과 우하단의 위치를 찾고, 그 영역의 테두리 부분을 시계방향 90도 회전 ..

    [Java] 프로그래머스 (로또의 최고 순위와 최저 순위) Dev-Matching 1
    Algorithm/Programmers

    [Java] 프로그래머스 (로또의 최고 순위와 최저 순위) Dev-Matching 1

    Problem : https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr Approach 먼저 주어진 입력에서 0의 개수를 센다. 최고 순위는 0이 모두 당첨번호와 같다는 것을 가정하여 계산하고, 최저 순위는 0이 모두 당첨번호와 다르다는 것을 가정하여 계산한다. 그리고 난 뒤, 일치하는 번호의 개수를 가지고 등수를 계산하여 반환하면 되는 간단한 문제이다. Code im..

    [Java] 프로그래머스 (하노이의 탑) Level 3
    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)로 옮긴다. -> 여기서는 정답..

    [Java] 프로그래머스 (최고의 집합) Level 3
    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가..

    [Java] 프로그래머스 (줄 서는 방법) Level 3
    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..

    [Java] 프로그래머스 (야근 지수) Level 3
    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..

    [java] 프로그래머스 (멀리 뛰기) Level 3
    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] ..

티스토리툴바