[백준 - Java] 11057번 : 오르막 수
문제 www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 설명 DP 동적 계획법을 사용해 해결하는 문제이다. 표를 그려보면 dp를 적용할 규칙이 쉽게 떠오른다. 먼저 각 자릿수에는 0~9까지의 10개의 숫자가 들어갈 수 있다. N=1 한자릿수일 경우 0~9까지 각 숫자들을 한 번씩 이용해 총 10가지의 오르막수를 만들 수 있다. N=2 두자릿수일 경우 00, 01, 02 ... 09 -> 10 가지 11, 12, 13 ... ..
2021. 2. 22.
[백준 - Java] 14499번 : 주사위 굴리기 (삼성 SW 역량 테스트 기출 문제)
문제 www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 설명 주사위 굴리는걸 어떻게 해야 하나 고민하는데 시간을 많이 쏟았다 ㅠ____ㅠ 근데 주사위만 굴리면 다 해결되는 문제. ㄹㅇ 아래 주사위를 기준으로 상하좌우 굴려보면 규칙을 찾을 수 있다. 2 4 1 3 5 6 나는 주사위의 Top, Bottom, Up, Down, Left, Right 6면을 모두 고려해 주사위를 굴렸는데 이렇게 하지 ..
2021. 2. 10.
[프로그래머스 - Java] 징검다리 건너기 (2019 카카오 개발자 겨울 인턴십)
문제 programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 설명 제한 사항을 보면 stones 배열의 크기는 1 이상 200,000 이하, stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수이다. 한 명 한 명 징검다리를 건너 보내면서 총 몇 명이 징검다리를 건널 수 있는지 확인한다면 굉장히 많은 시간이 걸림. 시간 초과가 나서 효율성에서 탈락함ㅠㅠㅠ 시간을 줄일 방법을 생각해서 문제를 풀어야 한다. 1. 이진 탐색으로 풀이 이진 탐색을 이용해 탐색의 시간을 줄이자! * 이진 탐색과 관련된 포스트는 아래를 확인해주..
2021. 2. 6.
[프로그래머스 - Java] 경주로 건설 (2020 카카오 인턴십)
문제 programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 설명 DFS로 모든 경로를 찾고, 경로마다 비용을 계산하며 최소 비용을 구하면 되겠다 생각도 했..
2021. 1. 31.
