문제 풀이 (11) 썸네일형 리스트형 [백준 9345] 디지털 비디오 디스크(DVDs) 1. 문제 https://www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 2. 풀이 세그먼트 트리를 이용한 문제이다. 물론 나는 인덱스 트리로 풀었다. 인덱스 트리에 대해 잘 모른다면 먼저 공부하고 오자! 인덱스 트리 : https://kinngife.tistory.com/32 인덱스 트리 (Binary Indexed Tree) 1. 정의 인덱스 트리는 원소들의 구간 합을 빠르게 구하기 위해 사용하는 자료구조로 펜.. [백준 2243] 사탕상자 1. 문제 https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 2. 풀이 세그먼트 트리를 이용한 문제이다. 물론 나는 인덱스 트리로 풀었다. 인덱스 트리에 대해 잘 모른다면 먼저 공부하고 오자! 인덱스 트리 : https://kinngife.tistory.com/32 인덱스 트리 (Binary Indexed Tree) 1. 정의 인덱스 트리는 원소들의 구간 합을 빠르게 구하기 위해 사용하는 자료구조로 펜윅 트리라고도 한다.. [백준 2517] 달리기 1. 문제 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 2. 풀이 세그먼트 트리를 이용한 문제이다. 물론 나는 인덱스 트리로 풀었다. 인덱스 트리에 대해 잘 모른다면 먼저 공부하고 오자! 인덱스 트리 : https://kinngife.tistory.com/32 인덱스 트리 (Binary Indexed Tree) 1. 정의 인덱스 트리는 원소들의 구간 합을 빠르게 구하기 위해 사용하는 자료구조로 펜윅 트리라고도 한다. 세그먼트 트리와 같.. [백준 2042] 구간 합 구하기 1. 문제 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 2. 풀이 기본적인 세그먼트 트리 문제이다. 나는 세그먼트 트리보다 인덱스 트리를 선호하므로 인덱스 트리로 설명하겠다. 인덱스 트리에 대해 잘 모른다면 먼저 공부하고 오자! 인덱스 트리 : https://kinngife.tistory.com/32 인덱스 트리 (Binary Indexed Tree) 1. 정의 인덱스 트리는 원소들.. [백준 16197] 두 동전 ● 문제 : 백준 16197번 : 두 동전 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net ● 알고리즘 - 백트래킹 ● 문제 풀이 백트래킹을 이용하여 문제를 풀었다. 보드판의 정보를 입력받을 N과 M 그리고 이차원문자열벡터 arr, 처음 동전 2개의 좌표를 입력받을 coin1과 coin2, 동전을 상하좌우로 이동시키므로 이동방향을 저장하는 배열 dir, 문제의 조건에 만족하는 최소의 답을 저장하는 ans를 전역변수로 선언하고 시작한다. 처음 보드판의 정보를 입력받고, 동전의 위치를 나타내는 'o'를 입력받았다.. [백준 2630] 색종이 만들기 ● 문제 : 백준 2630번 : 색종이 만들기 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net ● 알고리즘 - 분할정복 ● 문제 풀이 입력받는 길이가 최대 128이므로 130*130 크기의 이차원 배열과 정답으로 출력할 하얀색 종이의 개수를 나타내는 white, 파란색 종이의 개수를 나타내는 blue를 선언한 후 시작한다. 가장 큰 색종이부터 차근차근 분할해가며 정답을 구한다. 현재 색종이가 모두 0으로 이루어져있다면 white를 1 증가시키고 1로 이루어져있다면 blue를 1 증가.. [백준 9663] N-Queen ● 문제 : 백준 9663번 : N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ● 알고리즘 - 재귀함수 - 백트래킹 [백트래킹] 백트래킹이란 경로를 탐색하다가 올바르지 않은 경로라면 계속해서 탐색하는 것이 아니라 이전 단계로 돌아가 다시 올바른 경로를 향해 찾아가는 알고리즘이다. 모든 경로를 탐색하는 알고리 kinngife.tistory.com ● 문제 풀이 처음에 체스판을 표현하고자 이차원 배열을 사용하였는데, 일차원 배열만으로도 문제를 해결할 수 있다는 것을 깨달았다. 입력받는 N의 크기가 최대 15이므로.. [백준 15652] N과 M (4) ● 문제 : 백준 15652번 : N과 M (4) 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ● 알고리즘 - 재귀함수 - 백트래킹 [백트래킹] 백트래킹이란 경로를 탐색하다가 올바르지 않은 경로라면 계속해서 탐색하는 것이 아니라 이전 단계로 돌아가 다시 올바른 경로를 향해 찾아가는 알고리즘이다. 모든 경로를 탐색하는 알고리 kinngife.tistory.com ● 문제 풀이 백준 15650번 N과 M (2) 코드에서 조금만 수정하면 된다. [백준 15650] N과 M (2) ● 문제 : 백준 15650번 .. 이전 1 2 다음