programmers

    [java] 프로그래머스 (거스름돈) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (거스름돈) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr Approach 백준 온라인 저지에서도 DP 카테고리의 문제를 풀어봤다면, 비슷한 문제를 보았을 것이다. 꽤나 유명한 DP문제이고, 아마 나는 KnapSack 문제로 풀었던 것 같다. 하지만 여기서는 KnapSack처럼 2차원배열을 가지고 풀면 효율성테스트에서 시간초과가 발생하므로, 1차원배열로 풀이하여야 한다. DP[i] 를 i ..

    [java] 프로그래머스 (리틀 프렌즈 사천성) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (리틀 프렌즈 사천성) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/1836 코딩테스트 연습 - 리틀 프렌즈 사천성 리틀 프렌즈 사천성 언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만 programmers.co.kr Approach 2017 카카오코드 본선문제이다. 구현에 필요한 별다른 테크닉은 필요없고, 여러 경우에 대해 조건 검사를 많이 해야되는 문제였다. 두 타일 사이가 최대 한번의 꺾임만으로 서로 도달할 수 있는지에 대한 문제이다. 동시에 없앨 수 있는 타일이 여러개이면, 알파벳이 작은 순부터 처리해야하므로, 정렬은 사용해야 되겠다는 점만 ..

    [java] 프로그래머스 (블록 이동하기) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (블록 이동하기) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr Approach 2020 KAKAO BLIND RECRUITMENT 문제이다. 약간 어려운 DP문제라고 생각한 문제이지만, 백준 온라인 저지에서도 비슷한 류의 DP 문제를 보았기에 크게 어렵지는 않았다. 일단 DP 배열을 구성함에 있어 로봇이 가로방향일 때와 세로방향일 때를 나누어 구성하였다. 그리고 자유롭게 이동을 할 수 있다는 가정에서의 총 움직임 개수는 8개이다.(상하..

    [java] 프로그래머스 (외벽 점검) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (외벽 점검) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 programmers.co.kr Approach 2020 KAKAO BLIND RECRUITMENT 문제였다. (해당 코딩테스트에서 가장 낮은 정답률을 기록하는... 0.6%) 순열을 이용한 탐색 유형의 문제이다. 처음 문제를 접했을 땐, dist 배열을 오름차순으로 정렬하여 무언가를 해보려고 했으나, 조금 생각한 결과 간단하게도 많은 반례가 생각이나서 고민 차에, 카카오 테크..

    [java] 프로그래머스 (기둥과 보 설치) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (기둥과 보 설치) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr Approach 2020 KAKAO BLIND RECRUITMEN..

    [java] 프로그래머스 (가장 긴 팰린드롬) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (가장 긴 팰린드롬) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr Approach 처음 생각한 풀이는 문자열의 왼쪽 끝과 오른쪽 끝을 각각 left와 right로 정해놓고, 범위를 점점 줄여나가는 식으로 풀이를 생각했지만, 결과적으로 시간초과가 나는 코드가 됐다. 문자열의 모든 위치를 기준으로 시작하여, 팰린드롬이면 계속해서 범위를 늘려 팰린드롬 문자열인지..

    [java] 프로그래머스 (보행자 천국) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (보행자 천국) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/1832 Approach 2017 카카오코드 예선 문제이다. DP를 이용하되, 두개의 DP를 유지하여야 하는 문제이다. 어느 한 지점 (x, y)에 대하여 그 점에 세로방향 길로 도착했는지, 가로방향 길로 도착했는지, 두개의 DP배열을 유지해야한다. 왜냐하면, 현재 위치 (x, y)에 회전금지 표지판이 있으면, 직진으로만 다음 위치로 갈 수 있기 때문이다. 따라서, 일반적으로 DP를 수행하되, 세로방향 길인지, 가로방향 길인지에 따라 다르게 처리를 해준 후, 목적지 (ex, ey) 를 세로방향 길로 도착할 수 있는 경우의 수와 가로방향 길로 도착할 수 있는 경우의 수를 더한다음 문제에서 요구한것처..

    [java] 프로그래머스 (베스트앨범) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (베스트앨범) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr Approach 자바에선 HashMap을 이용한 완전탐색으로 풀 수 있는 문제였다. 좀 더 깔끔하게 풀어보고 싶었지만 그럴줄 몰라 아쉬웠다. 문제에서 요구한 출력조건은 다음과 같다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은..

    [java] 프로그래머스 (순위) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (순위) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr Approach 플로이드-와샬 알고리즘을 활용하여 풀 수 있는 의외의 문제이다. 기본적인 메커니즘은 이렇다. result에 {1, 2}, {2, 3}이 있다면, (1, 3)도 결정된다. 경기결과에 없더라도 1과 3사이에 순위를 매길 수 있다. 그런 후, (i, j)와 (j, i)가 모두 갱신이 안되었다면, i 는 순위가 확정되지 않았다고 취급할 수 있다. 먼저 DP배열을 생성한 후, 초기화를 진행한다. (경기결과를 DP배열에 반영) 플로이드-와샬 알고..

    [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을 열의 ..

티스토리툴바