코딩테스트 연습 - 합승 택시 요금 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시간 뒤 녹는 치즈를 찾자마자 바로 녹이면 안된다. 그 치즈가 녹고 외부에 노출되는 치즈가 있다면 잘못 녹일 수 있..
3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net POINT 뱀의 위치를 큐에 저장하자 뱀의 머리가 매번 움직이고, 꼬리는 사과를 먹으면 움직이지 않는다. → 움직일 때마다 머리 위치를 새로 저장한다. 사과를 먹지 못하면 꼬리도 움직여야 한다. → 움직이기 전의 꼬리 위치를 제거한다. 뱀의 방향 전환 방향에 따라 증가하는 좌표 값을 시계 방향으로 리스트에 설정해두고 오른쪽으로 회전할 땐 인덱스를 증가, 왼쪽으로 회전할 땐 인덱스를 감소시킨다. 동, 서, 남, 북 4가지 방향이므로, 4로 나눈 나머지를 구한다. 풀이 n..
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 ..
- Total
- Today
- Yesterday
- node.js
- DP
- React-native
- 키워드밑줄
- 백준
- 프로그래머스
- 판례암기
- 파이썬
- 웅진IT
- 동기
- 코테
- Spotify
- 코드분석
- Unsplash
- python
- flutter
- 코딩테스트
- dfs
- p5js
- 코어자바스크립트
- Python3
- 비동기
- fetch
- 프로젝트
- 다이나믹프로그래밍
- 감시피하기
- rn
- React
- React.js
- backtracking
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |