개발을항해

코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr POINT 반복되는 변수 파악하기 k개로 문자를 자를 때, 앞의 문자(prev_str)와 뒤의 문자(curr_str)의 index 값이 어떻게 변하는가? 예외 처리 문자 길이가 1일 때는 정답이 1이다. 참고 문자 길이를 초과하는 인덱스를 입력하면, 아무것도 나오지 않는다 (에러가 발생하진 않는다). str = "aabbaccc" print(str[8:9]) # 풀이 def solution(s): # (예외) 문자 길이가 1인 경우 if (len(s) =..

코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr POINT 최소 비용 (s -> i) + (i -> a) + (i -> b) 예제에서 4 → 1 → 5, 5 → 6 , 5 → 3 → 2 처럼, 어피치와 무지는 특정 노드(i=5)를 기..

** 백준 문제를 solution 타입 문제로 변형한 풀이입니다. ** 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net POINT 내부와 외부 공간 분리하기 백준의 처럼 치즈가 외부에 노출되어도 다른 치즈 안에 있으면 녹지 않는다. 내부가 아닌 외부 공간에 두 곳 이상이 노출되면, 그 치즈는 1시간 뒤 녹는다. 치즈를 녹인 후 다시 내부와 외부를 분리해야 한다. 치즈 한번에 녹이기 1시간 뒤 녹는 치즈를 찾자마자 바로 녹이면 안된다. 그 치즈가 녹고 외부에 노출되는 치즈가 있다면 잘못 녹일 수 있..

2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net POINT DP 암호는 두 자리로 묶을 수 있는 수가 있으면 경우의 수가 증가한다. 자릿수가 늘어나면서 동일한 방법으로 가짓수를 구하고 앞 자리의 결과가 뒤의 자리에도 영향을 미치니까 DP(Dynamic Programing, 다이나믹 프로그래밍)으로 문제를 해결한다. index 0 1 (시작) 2 3 4 5 code 0 2 5 1 1 4 dp 1 1 2 2 4 6 현재 자리를 i라고 하면, 다음과 같은 규칙이 생긴다. 뒤의 두 자리가 암호 범위에 속할 경우 dp[i] = dp[i..

https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net POINT 임의의 자리에서 상, 하, 좌, 우로 5번 이동하며 가능한 수의 개수를 구해야하기 때문에 DFS(Death-First Search)를 이용한다. 6자리의 000000 ~ 999999의 수가 만들어지므로 1000000자리의 visitied 배열을 사용한다. graph=[] for i in range(5): graph.append(list(map(..

2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net POINT Dynamic Programing (다이나믹 프로그래밍, dp) 피보나치 수열이 대표적인 예시이다. 1. 큰 문제를 작게 나눌 수 있고, 2. 작은 문제에서 구한 결과가 큰 문제에서도 사용되면 Dynamic Programing을 사용한다. 재귀(Top-down), 반복(Bottom-up) 두 가지 방법이 있으며, 시간 복잡도를 고려해서 반복문을 사용한다. 풀이 n = int(input()) # 계단 개수 scores = [0] * (n+1) # 계단 점수 for ..