본문 바로가기

알고리즘/백준

 (109)
2167번: 2차원 배열의 합 https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y). www.acmicpc.net 다이나믹 프로그래밍 문제인데, 점화식의 정의를 어떻게 하는가가 중요한 문제이다. 점화식은 어떤 n에 대해서도 해당하기 때문에, 1부터 원하는 n까지 구할 수 있다. dp[301][301]을 선언하고, dp[i]..
[BOJ 1649] 택시(C++) https://www.acmicpc.net/problem/1649 1649번: 택시 첫 번째 줄에 교차로의 개수인 N(1 if(cnt[next] == cnt[curr])은 현재 curr 교차로에서 방문된 C1 ~ Ck의 값이, next 교차로에서 방문된 C1 ~ Ck의 값과 같다면, 경로의 수를 더할 수 있다는 것을 의미한다. 여기서 가질 수 있는 의문 점은, 'cnt[next]와 cnt[curr]의 값이 같다는 게 방문한 C1 ~ Ck의 노드도 같다고 할 수 있을까?'라는 의문이 생길 수 있다. cnt[next] = 3, cnt[curr] = 3이라고 생각해보자! next > C1, C2, C3 curr > C1, C2, C4 C1, C2, C4 순서로 방문하는 것이 불가능하다면 이유는, C1 -> C..
[15686번] 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 문제접근법 1. 치킨 집의 위치와 가정 집의 위치를 담을 자료 구조가 필요하다. 치킨 집의 위치와 가정 집의 위치를 통해서 도시의 치..
[15683번] 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 www.acmicpc.net 문제접근법 1. 카메라들의 위치와 방향을 기억할 자료 구조를 선언한다. 카메라들의 조합을 확인해가면서, 감시되는 지역을 체크하고 남은 사각..
[17472번] 다리 만들기 2(C++, 삼성 상시 테스트, 쉬운 설명) https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 이 문제는 삼성 상시 테스트 A형 기출 문제이다. 문제 접근법. 1. 섬과 섬 사이에 다리를 놓을 수 있는 경우의 수를 전체 탐색해야 한다. 우선, 다리를 놓을 수 있는 경우를 파악해야 한다. 다리를 놓을 수 있는 경우는, 각 섬에서 최소의 다리의 길이를 구해야 한다. 주의해야할 점은, 다리의 길이는 1보다 커야 한다. 즉, 다리의 길이가 1이라면 무시해야 한다. 이 말은 무..
[17471번] 게리맨더링(삼성 상시 테스트 A형 유사 문제) 문제 백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 ..
[5373번] 큐빙(2018년도 삼성 기출 문제) 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다. 이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란색, 앞 면은 빨간색, 뒷 면은 오렌지색, 왼쪽 면은 초록색, 오른쪽 면은 파란색이다. 루빅스 큐브를 돌린 방법이 순서대로 주어진다. 이때, 모두 돌린 다음에 가장 윗 면의 색상을 구하는 프로그램을 작성하시오. 위의 그림은 루빅스 큐브를 푼 그림이다. 왼..
[16235번] 나무 재테크(런타임 에러 발생 이유 설명) 문제 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 칸에 대해서 조사를 한다. 가장 처음에 양분은 모든 칸에 5만큼 들어있다. 매일 매일 넓은 땅을 보면서 뿌듯한 하루를 보내고 있던 어느 날 이런 생각이 들었다. 나무 재테크를 하자! 나무 재테크란 작은 묘목을 구매해 어느정도 키운 후 팔아서 수익을 ..

티스토리툴바