본문 바로가기

Algorithm

[백준] 10844 쉬운 계단 수 (Kotlin 코틀린) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명 5656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 풀이 과정 이 문제는 단계마다의 규칙을 찾아 점화식을 세워 구현하는 DP 문제이다. 길이 1짜리 계단을 생각해보면, 1 2 3 4 5 6 7 8 9 총 9개의 계단이 있다. 길이 2짜리 계단을 생각해보면, 10 12 21 23 32 34 43 45 ... 87 89 98 로 총 17개가 있다. .. 더보기
[Codility]GenomicRangeQuery (Python, Kotlin) https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/start/ Codility Your browser is not supported You should use a supported browser. Read more app.codility.com 문제 설명 A:1, C:2, G:3, T:4 이며 'A,C,G,T'로 이루어진 문자열 S를 P[i]부터 Q[i]까지 범위의 인덱스로 잘랐을 때 해당 문자열 내의 최솟값을 구하는 문제이다. 즉, 'CAGCCTA' 라는 문자열 S가 주어지고, P[0] = 2, Q[0] = 4 이면 자른 문자열은 GCC가 되고 여기서 최솟값은 C = 2가 된다. 풀이 과정 이 문제를 풀면서 굉장.. 더보기
[백준] 2579 계단 오르기 (Python 파이썬) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 설명 위 링크에 주어진 문제 설명처럼, 계단을 오르는 문제이다. 단, 3번 연속된 계단을 이어서 오를 수는 없으며 마지막 계단은 무조건 밟아야 한다. 풀이 과정 이 문제는 DP(다이나믹 프로그래밍)을 이용해 앞에서 부터 최대값을 저장해 나가야 한다. 현재 계단을 밟는다면, 이전과 이이전을 연속해서 밟으면 안된다. 따라서, 현재 계단의 최댓값은 현재 + 이전 + 이이이전 or 현재 + 이이전 중에 선택을 .. 더보기
[백준] 1932 정수 삼각형 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 주어진 그림처럼 삼각형 모양으로 숫자가 주어진다. 맨 위부터 시작해 제일 아래쪽으로 탐색을 하게되는데, 현재 지점에서 다음 지점(아래 지점)으로 이동할 때는, 왼쪽대각선과 오른쪽 대각선으로만 갈 수 있다. 이 방법으로 탐색했을 때, 탐색경로에 있는 숫자들을 모두 더했을 때의 최대가 되는 경로를 구하는 문제이다. 풀이 과정 이 문제는 DP(다이나믹 프로그래밍)을 이용해 앞에서부터 최댓값을 저장해나가며 푸는 문제이다. 가장 첫번째 열에 있는 숫자(7, 3, 8,.. 더보기
[백준] 20057 마법사 상어와 토네이도 (Python 파이썬) https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 문제 설명 문제의 자세한 설명은 위 링크를 참조하시길 바랍니다. 이 문제는 구현 시뮬레이션 문제로, 문제에서 요구하는 사항이 꽤 많고 상세합니다. 빠짐없이 체크하여 어떻게 구현해야 할지 구상한 후에 구현해야 하는 문제입니다. 풀이 과정 from collections import deque n = int(input()) graph = [] graphIdx = dequ.. 더보기
[백준] 20056 마법사 상어와 파이어볼 (Python 파이썬) https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 문제 설명 문제의 자세한 설명은 위 링크를 참조하시길 바랍니다. 이 문제는 구현 시뮬레이션 문제로, 문제에서 요구하는 사항이 꽤 많고 상세합니다. 빠짐없이 체크하여 어떻게 구현해야 할지 구상한 후에 구현해야 하는 문제입니다. 풀이 과정 ① 먼저 초기의 파이어볼을 입력받은 후에 fireball라는 큐와 graph의 각 칸에 파이어볼을 삽입합니다. firebal.. 더보기
[백준] 21609 상어 중학교 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다. 일반적인 BFS/ DFS 문제보다 신경써서 구현해야 할 부분들이 훨씬 까다로운 문제이므로 과정을 하나하나 잘 살펴보면서 구현하시는 것을 추천드립니다. 풀이 과정 먼저 두 방법으로 풀면서 코드를 두 가지로 작성해보았습니다. 코드①은 구현해야 할 부분들을 그대로 나열식으로 작성한 코드.. 더보기
[백준] 21611 마법사 상어와 블리자드 (Python 파이썬) https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 문제 설명 문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다. 이 문제는, 특별한 알고리즘 없이 문제에서 주어진 사항을 구현하는 문제이지만 구현해야 하는 부분들이 굉장히 까다로운 문제였습니다 풀이 과정 풀이과정이 굉장히 길기 때문에, 잘 모르시는 부분을 중점으로 보시는 것을 추천드립니다. ① 먼저, 가운데 칸(n//2, n//2.. 더보기

티스토리툴바