본문 바로가기

Data Structures and Algorithms/백준 온라인 저지9

백준 온라인 저지 | 2630번 색종이 만들기 | C++ 백준 온라인 저지 | 2630번 색종이 만들기 | C++ 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 1. 문제 접근 ■ 1.1 기본 조건 종이가 한 가지 색으로만 칠해져 있는 경우, 종이의 개수를 세고 있는 배열에서 흰색 종이의 개수 혹은 파란색 종이의 개수를 1만큼 증가시킨다. ■ 1.2 재귀 조건 종이가 두 가지 색으로 칠해져 있는 경우, 종이를 좌상단, 우상단, 좌하단, 우하단 네 부분으로 나누고 네 부분에 대해서 각각 한 가지 색으로만 칠해져 있는지 재귀적으로 구현해야 .. 2022. 8. 4.
백준 온라인 저지 | 10870번 피보나치 수5 | C++ 백준 온라인 저지 | 10870번 피보나치 수5 | C++ 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 1. 문제 접근 수학에서 피보나치(fibonacci) 수는 첫째 항과 둘째 항이 1이고 그 이후의 모든 항은 바로 앞 두 항의 합인 수열이다. 피보나치 수 Fn의 초항은 F(1) = F(2) = 1이고, 점화식은 F(n) = F(n-1) + F(n-2) (n ≥ 2)으로 나타낼 수 있다. 예를 들어 F(4)는 F(3) + F(2) = F(1) + F(2) + F(2).. 2022. 8. 4.
백준 온라인 저지 | 10872번 팩토리얼 | C++ 백준 온라인 저지 | 10872번 팩토리얼 | C++ 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 접근 수학에서 팩토리얼(factorial)은 그 수보다 작거나 같은 모든 양의 정수의 곱이다. 예를 들어 N!은 N × (N-1) × (N-2) × ... × 2 × 1을 나타낸다. 재귀 문제를 풀 때 생각해야 할 함수 인자, 기본 조건, 그리고 재귀 조건을 살펴보자. ■ 1.1 함수 인자 N! = N × (N-1) × (N-2) × ... × 2 × 1으로 미루어보아 팩토리얼을 계산하기 위해서 필요한 숫자는 양의 정수 N임을 알 수 있다. 그러므로 재귀 함수에 전달할 인자는 사용자가 입력할 양의 정수 .. 2022. 8. 4.
백준 온라인 저지 | 10825번 국영수 | C++ 백준 온라인 저지 | 10825번 국영수 | C++ 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 1. 문제 접근 ■ 1.1 tuple 자료 구조 학생마다 이름과 국어, 영어, 수학 점수가 주어진다. 구조체(structure)를 사용하여 네 가지 데이터를 다룰 수도 있지만, 조금 더 편리한 tuple 자료 구조를 사용하려고 한다. #include 헤더 파일을 선언하고 이름과 국어, 영어, 수학 점수를 저장하는 데 가장 적절한 타입인 로 데이터를 받는다. ■ 1.2 compare 사용자 정.. 2022. 7. 24.
백준 온라인 저지 | 2178번 미로 탐색 | C++ 백준 온라인 저지 | 2178번 미로 탐색 | C++ 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1. 문제 접근 ■ 1.1 4방위 너비 우선 탐색 0 혹은 1로 이루어진 미로에서 한 칸에서 다른 칸으로 이동할 때 서로 인접한 칸으로 이동할 수 있다고 되어 있다. 이것으로 미루어 보아 2차원 평면에서 한 정점에 인접한 사방위 너비 우선 탐색을 수행하는 것이 적절해 보인다. ■ 1.2 최단 거리 시작 위치 (1, 1)에서 출발하여 도착 위치 (N, M)으로 이동할 때 지나야 하는 최소 칸 수를 구한다는 말은 정점 (0, 0)에서 정점 (N.. 2022. 3. 8.
백준 온라인 저지 | 1926번 그림 | C++ 백준 온라인 저지 | 1926번 그림 | C++ 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 1. 문제 접근 ■ 1.1 4방위 너비 우선 탐색 2차원 평면에서 0과 1로 그림의 데이터가 주어진 상태에서 1과 상하좌우로 연결된 (대각선으로는 연결되지 않은) 그림의 개수와 그 그림 중에서 가장 넓이가 큰 그림의 넓이를 출력해야 한다. 1과 인접한 상하좌우를 순서대로 탐색해야 하므로 큐(queue) 자료구조를 이용하여 4방위 너비 우선 탐색을 하고자 한다. ■ 1.2 그림의 개수와 그림의 넓이 숫자 1로 상하좌우 연.. 2022. 3. 8.
백준 온라인 저지 | 5397번 키로거 | C++ 백준 온라인 저지 | 5397번 키로거 | C++ 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 1. 문제 정의 ■ 1.1 리스트 반복자 강산이가 비밀번호 창에서 입력한 키가 주어지고 이 키는 알파벳 대문자, 알파벳 소문자, 숫자, 백스페이스, 화살표 키로 구성된다. 강산이가 입력한 길이가 L인 문자열에서 화살표 키로 커서를 움직이거나 백스페이스 키로 문자를 지워야 하기 때문에 데이터를 중간에 삽입하고 삭제하기 편한 리스트(list)로 코드를 구현하는 것이 적절해 보인다. ■ 1.2 리스트 메서드 리.. 2022. 2. 27.
백준 온라인 저지 | 1406번 에디터 | C++ 백준 온라인 저지 | 1046번 에디터 | C++ 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 1. 문제 정의 ■ 1.1 리스트 반복자 편집기에는 커서(cursor)라는 것이 있는데 커서는 첫 번째 문자의 왼쪽, 마지막 문자의 오른쪽, 혹은 모든 연속된 두 문자 사이에 위치할 수 있다. 그리고 편집기가 지원하는 4가지 명령어로 커서의 위치를 좌우로 옮기거나 문자를 삽입 혹은 제거할 수 있다. 이러한 특성을 고려해보았을 때, 문장은 리스트(list), 커서는 반복자(iterator)로 적절하게 구현하면 위의 .. 2022. 2. 26.
백준 온라인 저지 | 1158번 요세푸스 문제 | C++ 백준 온라인 저지 | 1158번 요세푸스 문제 | C++ 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 1. 문제 정의 ■ 1.1 요세푸스 순열 요세푸스 순열은 1부터 N까지 숫자에서 K번째 숫자를 순서대로 없애는 순열을 말한다. 예를 들어, (7, 3) 요세푸스 순열은 1부터 7까지의 숫자에서 3번째 숫자를 순서대로 없애는 {3, 6, 2, 7, 5, 1, 4}이다. ■ 1.2 리스트 요세푸스 알고리즘을 구현하려면 숫자를 넣고 빼내는 데 유용한 큐(queue) 혹은 리스트(list)를 사용하는 것이 적절하다. 나는 리스트를 사용하여 문제를 해결할 것이다. 요세푸스 알고리즘은 다음과 같이 두 가지 .. 2022. 2. 25.

티스토리툴바