SilentWalk

문제: https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 풀이과정 124나라에서는 1, 2, 4 세 가지 숫자만을 사용하여 모든 자연수를 표현한다. 먼저 이 숫자의 규칙성을 찾기 위해 10진법 숫자와, 3진법 숫자, 그리고 124 나라의 숫자를 비교 해 보았다. 10진법 수 3진법 수 124 나라의 숫자 1 1 1 2 2 2 3 10 4 4 11 11 5 12 12 6 20 14 7 21 21 8 22 22 9 100 24 10 101 41 11 102 42 12 110 44 13 111 111 14 112 112 15 120 114 여기서 124나라의 숫자에서 4가 나타나는 경우를..

문제: https://programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 풀이과정 N의 값에 따라 어떤 방식으로 이동하는지 살펴보면 다음과 같은 표를 얻을 수 있다. N 이동방법 (J: Jump, TP: Teleport) K 1 J(0 → 1) 1 2 J(0 → 1) → TP(1 → 2) 1 3 J(0 → 1) → TP(1 →2) → J(2 → 3) N(2) 까지 이동 후 1칸 점프 2 4 J(0 → 1..

문제: https://www.acmicpc.net/problem/11726(백준) 문제: https://programmers.co.kr/learn/courses/30/lessons/12900(프로그래머스) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 프로그래머스의 [멀리 뛰기] 문제와 사실상 같은 문제이다. 멀리 뛰기 게시글에 해당 내용을 정리 해 놓았다. 소스코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scann..

문제: 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 풀이과정 문제를 서술하는 방식만 바뀌었을 뿐, 2N 타일링 문제와 완전히 동일한 문제이다. 그래서 1칸 점프와 2칸 점프를 각각 다음과 같이 치환하여 생각할 수 있다. 이제, 높이가 2이고 가로길이가 N인 공간에 크기가 1 * 2인 타일을 놓는 방법의 수를 몇가지 더 찾아보면 다음과 같다. 이 그림..

문제 풀이과정 팰린드롬은 크게 두 가지 종류로 구분할 수 있다. 글자 하나를 중심으로 서로 대칭을 이루는 팰린드롬 (팰린드롬의 길이가 홀수) a, aba, aaa, abbb 등 글자 두 개를 중심으로 서로 대칭을 이루는 팰린드롬 (팰린드롬의 길이가 짝수) aa, abba, aaaa, abcc 등 풀이의 진행과정은 다음과 같다. 특정 index i 번 째 문자 하나를 중심으로 팰린드롬을 이룬다고 가정하고 최대 팰린드롬의 길이를 구한다. 특정 index i 및 i + 1 번 째 문자 두 개를 중심으로 팰린드롬을 이룬다고 가정하고 최대 팰린드롬의 길이를 구한다. (해당 문자 두 개가 서로 다를 경우 최대 팰린드롬의 길이는 1이다.) 1과 2에서 구한 값들 및 기존에 구한 최대 팰린드롬의 길이 중 가장 긴 값을..

문제: https://leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 처음 문제를 봤을 땐, 난이도도 Easy이고 문제 번호도 1번이어서 워밍업 문제라고 생각했다. 그래서 그 때는 바로 떠오르는 대로 이중 for문을 사용해서 풀이를 했었는데, Solution을 보니 hash table을 사용하여 해결하는 방법이 있어서 정리 해 둔다. 이런 걸 보면, 사소한 곳에서도 자료구조의 적절한 선택이 ..

문제 : https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 각 칸에서 담을 수 있는 빗물의 양을 찾는 방법은 다음과 같다. 먼저, 각 칸마다 담을 수 있는 빗물의 최대 높이는 해당 칸의 왼쪽 벽과 오른쪽 벽 중 낮은 쪽의 높이이다. 이 때, 양 옆의 벽이 꼭 해당 칸의 바로 옆에 붙어있을 필요는 없다. 각각의 칸에서 왼쪽, 오른쪽을 바라본다고 생각했을 때, 눈에 보이는 가장 높은 벽의 높이를 찾으면 된다. 예시 1번에서 벽의 높..

문제 링크 참고 : 플로이드-워셜 알고리즘 풀이 과정 Floyd-Warshall 알고리즘을 되짚어보고 진행하면 수월하다. 문제에 주어지는 조건 (선수의 수 및 전적)을 int 형 2차원 배열로 표현할 수 있다. 주어진 예제라면 아래 표와 같이 표현된다. int 타입 2차원 배열로 표현하였으므로 위 표의 빈칸도 0으로 초기화되어있다. 따라서, 0은 자기 자신 또는 결과 모름을 의미한다. 1은 상대에게 승리했음을, -1은 상대에게 패배했음을 의미한다. 이후 1번 선수부터 아래의 과정을 반복한다. i번 선수가 승리한 상대 선수를 찾는다. 주어진 예제에서는 1번 선수가 2번 선수를 상대로 승리했다. 1번의 결과로 찾은 선수가 승리한 상대 선수를 찾는다. 주어진 예제에서는 2번 선수가 5번 선수를 상대로 승리했다..