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/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번 선수를 상대로 승리했다..

문제 - 가장 먼 노드 풀이과정 BFS 방식으로 풀이를 진행 사전준비 각 Node마다 연결되어있는 Node들을 표현하기 위한 2차원 배열을 만든다. (boolean[n][n]) 이후 주어진 edge 정보를 바탕으로 서로 연결되어 있는 Node들 끼리는 해당 위치의 원소값을 true로 변경한다. 1번 Node로부터 얼마만큼의 거리에 떨어져 있는지를 표현할 1차원 배열을 만든다. (int[n]) 여기서 원하는 결과는 가장 먼 거리에 있는 Node의 갯수이므로 정확한 최대 거리를 꼭 알아야 할 필요성은 없다. 1번 Node로 부터 떨어져 있는 거리를 모르는 Node의 경우 원소값이 0인 상태로 존재한다. 1번 Node 부터 BFS 탐색을 시작할 수 있도록 준비한다. queue에 1번 Node를 enqueue ..

등굣길 풀이과정 주어진 n과 m에 대하여 이동 가능한 길을 grid로 나타낼 수 있다. 예를 들어 n = 3, m = 4이면 아래 그림과 같다. 문제의 제한 조건으로 이동 방향은 우측 및 하단 뿐이므로, 출발지점에서 우측과 하단으로 이동 가능한 방법의 수는 아래의 그림과 같이 나타낼 수 있다. 각각 오른쪽으로만 계속 이동하거나, 하단으로만 계속 이동해야 도달할 수 있는 위치이므로 이동가능한 방법의 가짓수는 모두 1이다. 나머지 비어있는 cell 들로 이동할 수 있는 방법은, 바로 위 cell에서 아래로 이동하거나 바로 왼쪽 cell에서 우측으로 이동하는 것 뿐이므로 나머지 각각의 cell들에 대한 이동 가능한 방법의 수는 바로 위쪽 cell까지 이동 가능한 방법의 수 + 바로 왼쪽 cell까지 이동 가능..