투투

programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 접근 1, 2, 4의 숫자를 활용해서 10진법의 수를 표현해야한다. 3진법을 사용해서 변환을 시도하였고 그 이후에는 어떻게 해야할지 감이 잡히지 않았다. 먼저 3진법으로 변환하는 코드에서 while문을 사용할 때 0을 초과할 때는 n을 3으로 나눈 나머지를 추가하고 n을 3으로 나누는 것을 반복한다. 하지만 124의 나라는 3진법으로 변환할 때 0, 1, 2가 아닌 1, 2, 4를 사용한다. 이때 1~10을 3진법으로 변환하면서 규칙을 찾아야한다. 나머지가 0일 때는 4, 1일 때는 1, 2일 때는 2를 최종해에 추가를 하며 나머지가 0일 때는 몫..

programmers.co.kr/learn/courses/30/lessons/12981 코딩테스트 연습 - 영어 끝말잇기 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] [0,0] programmers.co.kr 접근 끝말잇기를 하면서 탈락하는 조건을 그대로 구현을 하였다. 이 문제에서는 탈락한 사람과 탈락한 ..

programmers.co.kr/learn/courses/30/lessons/49993# 코딩테스트 연습 - 스킬트리 programmers.co.kr 접근 처음에 중복된 스킬은 주어지지 않는다는 것을 스킬 트리가 담겨있는 리스트 내에 중복된 스킬 트리가 없다는 것을 이해를 했다. 하지만 하나의 스킬 트리 내에 중복된 스킬이 없는 것이었다. 그래서 단순히 skill의 앞에서부터 비교하여 조건에 부합하는 스킬트리가 있는지 판단하였다. 구현 먼저 skill_trees를 탐색하면서 각각의 skill_tree를 검사한다. 스킬의 순서가 담겨있는 skill을 리스트형으로 변환하고 skill_tree를 탐색하면서 skill의 앞과 같은지 확인한다. 다르다면 break가 될 것이며 같다면 앞의 원소가 제거되어 다음 비..

programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr 접근 다른 사람들의 풀이를 참고하였다. 현재까지 이해한 것은 각각의 money로 만들 수 있는 1부터 n까지의 수를 누적해서 계산해나간다. 1은 1부터 n까지의 돈을 만드는 경우의 수가 1개이다. 2는 1을 만들 수없기 때문에 이전의 1에서 1을 만드는 경우의 수에서 가져온다. 그리고 2로 2를 만들 수 있는 경우의 수는 1+1과 2이다. 즉 1로 만든 수와 자기..

programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 접근 최소한의 조작으로 입력된 문자열로 변경해야한다. 조작은 문자열 변경을 위해 위, 아래로의 조작과 바꿀 문자열의 위치로 이동하는 왼쪽, 오른쪽의 조작이 있다. 이를 최소로 하기위해서는 바꿔야하는 문자에서 A와 Z까지의 거리 중 최소를 구하고 현재 위치에서 왼쪽과 오른쪽으로 갈 때의 최소를 구하도록 한다. 구현 - 먼저 changed_name에 위, 아래..

programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 접근 탐욕법 알고리즘에 분류된 문제이다. 그래서 어떠한 기준으로 매번 최적을 선택할지 고민을 했다. 먼저 정렬을 했는데 진입한 시점을 기준으로 오름차순으로 정렬을 하였다. 이후 규칙을 찾아보려고 했고 나가는시점을 기준으로 오름차순 정렬도 해보았다. 나가는시점을 기준으로 정렬했을 때 나가는 시간을 기준으로 카메라를 설치하고자 하였다. 즉, 정렬 후에는 첫 번째 오는 시간은 가장 빨리 나가는 차량이기때문에 해당 차량이 나가는 시점에 카메라를 설치한다. 이후 설치한 카메라의 시점을 통해..

programmers.co.kr/learn/courses/30/lessons/12951 코딩테스트 연습 - JadenCase 문자열 만들기 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 programmers.co.kr 접근 공백다음의 글자는 대문자로 만들고 나머지는 소문자로 만들어서 answer에 추가한다. 구현 첫 번째 인덱스가 영문이라면 대문자로 만들어 answer에 추가한다. 첫 번째 인덱스 이외에는 이전의 문자가 공백일 때 현재문자를 대문자로 만들어 추가하고 아닌 것은 모두 소문자로 만들어 추가한다. def solution(..

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 접근 시간초과가 날 것 같았지만 백트래킹으로 시도를 해보았다. 역시 시간초과가 발생했다. 그래서 1칸, 2칸까지 뛸 수 있다는 것에 동적계획법이 생각이 났고 점화식을 세우려고 했다. 경우의 수를 봤을 때 f(n) = f(n-1) + f(n-2)라는 점화식을 세울 수 있었고 그대로 구현을 하였다. 구현 n은 1이상 200..

programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 접근 처음에 완전탐색으로 풀었지만 시간초과가 발생했다. 이후에 다른 사람들의 풀이를 보고 DP로 접근하는 것을 알았다. 하지만 어떻게 DP로 풀어야할지 감이 잡히지 않았다. 내가 이해한 방식은 다음과 같다. (y, x) 좌표를 기준으로 2x2 크기의 윈도우로 정사각형를 찾아서 크기를 저장해두는 것이다. 1, 1부터 시작을 하여 1이상인 좌표에 대해 왼쪽, 위, 좌상단을 검사하여 최솟값을 찾는다. 만약 이 범위 내에 0이 있다면 정사각형이 아니다. 정사각형이라면 1이상..

programmers.co.kr/learn/courses/30/lessons/68645 코딩테스트 연습 - 삼각 달팽이 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] programmers.co.kr 접근 이 문제처럼 어떠한 규칙에 의해 수들이 정렬되어 있을 때 방향이 어떠한 규칙으로 반복되는지, 인덱스는 어떻게 변하는지 등을 생각해볼 필요가 있다. 이 문제는 아래, 오른쪽, 위 방향이 반복되어지고 있다. 그리고 방향이 바뀔 때마다 포함된 숫자들이 하나씩 감소하고 있다. 이 부분을 신경써서 구현을 해보자. 구현 NxN 크기의 그래프를 생성하여 0으로 초기화하였다. 이 그래프에 숫..