본문 바로가기

알고리즘

[백준] 11659 구간 합 구하기4 (Python 파이썬) https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 설명 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 풀이 과정 이 문제는 누적 합 으로 푸는 문제이다. 누적합을 이용하지 않고 단순 합계를 이용한다면 시간초과 오류가 나게 된다. 한번 구간합을 구하는 시간복잡도는 O(n)이고 m번동안 수행을 하게 된다면 총 시간복잡도는 O(nm)이 되는데 데이터가 10만개가 되면 시간초과 오류.. 더보기
[백준] 17478 재귀함수가 뭔가요? (Python 파이썬) https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 문제 설명 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다. 중앙대학교와 자신의 길이 맞지 않다고 생각한 JH 교수님은 결국 중앙대학교를 떠나기로 결정하였다. 떠나기 전까지도 제자들을 생각하셨던 JH 교수님은 재귀함.. 더보기
[백준] 2565 전깃줄 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 자세한 문제 설명은 위 링크를 참고하시길 바랍니다. 풀이 과정 이 문제는 DP(다이나믹 프로그래밍)을 이용해 최대 증가 수열을 찾는 문제라고 할 수 있다. 전깃줄이 교차하지 않도록 하려면 어떻게 해야할지에 대해 먼저 생각해보자. 먼저, 위 그림에서 A의 1번과 B의 8번만 연결되어 있다고 가정해보자. 그리고 이 때, 아래의 ①번 상황과 ②번 상황을 각각 생각해보자. ① A의 2번과 B의 2번이.. 더보기
[백준] 1912 연속합 (Python 파이썬) https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 설명 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 풀이 과정 이 문제는 DP(다이나믹 프로그래밍)을 이용해 .. 더보기
[백준] 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.. 더보기

티스토리툴바