돌고 돌아 기본

프로그래머스 12980번 - 점프와 순간 이동 요구사항 1. 한 번에 K 칸을 앞으로 점프하거나, 현재까지 온 거리의 2배에 해당하는 위치로 순간이동하는 아이언 슈트를 착용하고 이동한다. 2. 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 들며, 순간이동을 할 경우는 건전지 사용량이 들지 않는다. 3. 거리 N을 이동하고자 할 때, 사용해야 하는 건전지 사용량의 최솟값을 반환하라. 요구사항 분석 및 풀이과정 1. 건전지 사용량의 최소로 하기 위하여 최대한 순간이동을 많이 하며, K 칸 점프를 최소한으로 하여야 합니다. 2. N번째 칸에 도착하는 방법은 K칸 점프해서 오거나, 순간이동으로 그전까지 온 거리의 2배에 해당하는 위치가 N인 경우 순간이동해오는 방법이 있습니다. 2-1. 후자의 경우는 그전..

프로그래머스 17677번 - [1차] 뉴스 클러스터링 요구사항 1. 두 문자열의 자카드 유사도 값에 65536을 곱한 후 소수점 아래를 버린 정수부를 반환하라. 요구사항 분석 및 풀이과정 자카드 유사도를 구하기 위하여 다중집합을 구성하여야 한다. 다중집합은 주어진 문자열을 두 글자씩 끊어 다중집합의 원소로 한다. 단, 영문자로 된 글자 쌍만 유효하며, 기타 공백이나 숫자, 특수 문자가 들어있는 경우에는 그 글자 쌍을 버리며 대소문자는 구별하지 않는다. 자카드 유사도는 두 다중집합 A, B에 대하여 (교집합의 원소의 수 / 합집합의 원소의 수)로 정의되며, 만약 두 다중집합 A, B가 모두 공집합일 경우 자카드 유사도는 1로 정의한다. 자카드 유사도 다중집합 A, B에 대하여 합집합(A or B)은 다음과..

프로그래머스 68645번 - 삼각 달팽이 요구사항 1. 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 반환하라. 요구사항 분석 및 풀이과정 위 사진에서 주어진 삼각형(n=4)을 우리가 다루는 이차원 배열의 형태로 시각화해보면 다음과 같습니다. 이렇게 이차원 배열로 시각화한 후, 기존 삼각형에서 반시계 방향으로 달팽이 채우기를 시각화해보겠습니다. 달팽이 채우기를 위해서 칸을 이동하는 방향에 규칙성이 보이시나요? 1번 화살표 방향 -> 2번 화살표 방향 -> 3번 화살표 방향 -> 1번 화살표 방향 -> ... -> 지금은 n = 4 일 때의 삼각형이지만, n에 따라 그려보시면 1번, 2번, 3번..

프로그래머스 12973번 - 짝지어 제거하기 요구사항 1. 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾은 후 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 2. 1번 과정을 반복해서 문자열을 모두 제거할 수 있으면 1을, 아니면 0을 반환하라. 요구사항 분석 및 풀이과정 연속된 문자열을 모두 제거하는 문제이며 전형적인 스택 문제입니다, 올바른 괄호 쌍을 찾을 때 스택을 사용하는 방법과 동일한 방법으로 구현하면 됩니다. 1. 문자열의 첫 문자부터 순회하여 만약 스택이 비었다면 문자를 추가합니다. 2. 스택이 비어있지 않다면 스택의 가장 위의 문자와 현재 문자가 같은지 확인합니다. (같은 알파벳 2개 붙어있는 짝을 확인하는 작업) 3. 같다면 스택의 가장 위의 문자를 제거하고, 현재 문자도 스택에 넣지 ..

프로그래머스 12914번 - 멀리 뛰기 요구사항 1. 한 번에 1칸 또는 2칸을 뛸 수 있을 때, n개의 칸을 건너 끝에 도달하는 방법의 수를 1234567로 나눈 나머지를 반환하라. 요구사항 분석 및 풀이과정 1. n개의 칸을 건너 끝에 도달하는 방법의 수를 dp[n]이라고 정의하면 다음과 같습니다. dp[n] = dp[n-2] + dp[n-1] ( n >= 3 ) dp[1] = 1 ( 1칸 ) dp[2] = 2 ( 1칸 + 1칸, 2칸 ) n개의 칸을 건너 끝에 도달하는 경우 마지막에 2칸을 뛰어 끝에 도달하는 경우와, 1칸을 뛰어 끝에 도달하는 경우가 있습니다. 마지막에 2칸을 뛰는 경우는 마지막 2칸을 제외한 n-2 개의 칸을 건너오는 경우의 수이고, 마지막에 1칸을 뛰는 경우는 마지막 1칸을 제..