gangee program

프로그래머스 코딩테스트 3단계 : 정수 삼각형 문제 설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 문제 풀이 이중 반복문을 통해 삼각형의 숫자 값들을 누적으로 더했을 때 더 큰 값으로 변경 ([[7], [10, 15], [18, 16, 15] ... ]) 첫 번째 반복문의 범위가 1부터인 이유 : triangle[0][0] 은 값의 ..

백준 코딩테스트 1463번 : 1로 만들기 (동적계획법) 문제 설명 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 문제 풀이 동적계획법의 Bottom-Up 방법을 이용해 풀이 x를 입력받기 위해 input을 해줌 연산 횟수를 저장하기 dp 리스트를 위해 0이 x+1개 있는 리스트로 초기화 반복문을 통해 2~x 까지 반복 i번째 dp 리스트를 i-1 리스트에 +1 해서 저장 (밑에 조건문에 부합하지 않을 경우 i-1 의 연산 횟수에 1을 더해주면 되기 때문) ..

프로그래머스 코딩테스트 2단계 : 피보나치 수 문제 설명 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 와 같이 이어집니다. 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. 문제 풀이 [기초문법] Dynamic Programming(동적계획법) - Python 다이나믹 프로그래밍에서 bottom..

분할 정복 알고리즘 큰 문제를 한번에 해결하기 어려울 때, 여러개의 작은 문제로 나누어 해결하는 기법 이때 동일한 작은 문제들이 반복적으로 계산되는 경우가 생길 수 있음 이를 보완하기 위해 나온 방법이 다이나믹 프로그래밍 Dynamic Programming (동적계획법) 1. 의미 필요한 계산 값을 저장해두었다가 재사용하는 알고리즘 설계 기법 처음 진행되는 연산을 기록하고 이미 진행되었던 연산이라면 기록되어있는 값 호출 = 시간, 자원 절약 가능 모든 가능성을 고려하여 항상 최적의 결과 도출 2. 사용 조건 최적 부분 구조 : 큰 문제를 작은 문제를 나눌 수 있다. 이러한 작은 문제의 답을 모아 큰 문제를 해결할 수 있다. 중복된 하위 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다. 3. 구현 방..

프로그래머스 코딩테스트 1단계 : 가장 가까운 같은 글자 문제 설명 문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다. 예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다. b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다. n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로..

프로그래머스 코딩테스트 1단계 : 시저암호 문제 설명 어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다. 예를 들어 "AB"는 1만큼 밀면 "BC"가 되고, 3만큼 밀면 "DE"가 됩니다. "z"는 1만큼 밀면 "a"가 됩니다. 문자열 s와 거리 n을 입력받아 s를 n만큼 민 암호문을 만드는 함수, solution을 완성해 보세요. 문제 풀이 문자를 숫자로, 숫자를 문자로 변환해주는 함수 (chr, ord)를 이용 영어가 z로 끝나면 다시 a로 넘어갈 수 있도록 만듦 조건문에서 isupper함수로 대문자일 경우, 대문자로 순서를 만듦 islower함수로 소문자일 경우, 소문자로 순서를 만듦 리스트 만큼 조건문을 반복하고 최종적으로 나온 리스트 a를..

ord() : 문자를 아스키코드로 변환 print(ord("A")) print(ord("B")) print(ord("a")) print(ord("b")) --------------------------- > 65 > 66 > 97 > 98chr() : 아스키코드를 문자로 변환 print(chr(65)) print(chr(66)) print(chr(97)) print(chr(98)) --------------------------- > A > B > a > b응용 : 특정 알파벳의 N번째 뒤의 알파벳 구하기 # A의 첫 번째 뒤 숫자 print(chr(ord("A") + 1)) # Z에서 다시 A로 돌아가는 코드 print(ord("Z") + 1 - ord("A")) print((ord("Z") + 1 -..

프로그래머스 코딩테스트 2단계 : 다음 큰 숫자 문제 설명 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다. 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다. 예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다. 자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요. 문제 풀이 answer에 n보다 1큰 값으로 설정 while 반복문을 통해 n의 이진수와 answer의 이진수의 1의 갯수를 세고 같을 경우 answer를 ..

프로그래머스 코딩테스트 1단계 : K번째수 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 문제 풀이 arr..

프로그래머스 코딩테스트 2단계 : 점프와 순간이동 문제 설명 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, ..