프로그래밍 공부 노트

https://www.acmicpc.net/problem/23358 23358번: Quack Strikes Back (Easy) Two years ago the IPSC contestants had a hard time to understand a piece of code written in PostScript. Last year wasn't any better as we introduced a queue-based programming language. If you didn't participate last year (and even if you did :), this pract www.acmicpc.net 굳이 따지자면 큐를 쓰는 문제이긴 하지만, 알고리즘 문제라기 보단 CS 문제에 가깝다. 큐와 레..

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 특별한 알고리즘을 사용하지 않는 구현 문제이다. 주사위를 객체로 만든 뒤 주사위의 회전을 메소드로 구현하면 쉽게 풀 수 있다. #include #define MAX_N 20 // N: 지도의 세로 크기, M: 지도의 가로 크기 int N, M; // 좌표 class coord { public: // (x, y): (가로, 세로) i..

https://www.acmicpc.net/problem/15653 15653번: 구슬 탈출 4 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 기본적으로 문제 자체는 구슬 탈출 2와 같은 문제이다. 단 이 문제는 기울일 수 있는 최대 횟수가 정해져 있지 않으므로, 각 상태에 도달할 수 있는 최소 기울임 횟수를 따로 저장하여 중복되는 경우의 수를 최대한 쳐내야 한다. #include typedef unsigned int ui; #define MAX_N 10 #define INF 0xffff..

https://www.acmicpc.net/problem/20327 20327번: 배열 돌리기 6 크기가 2N×2N인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 8가지가 있고, 연산에는 단계 ℓ (0 ≤ ℓ < N)이 있다. 단계 ℓ은 배열을 부분 배열로 나눌때 사용하는 값이며, 부분 www.acmicpc.net 철저한 구현 문제이다. 배열의 각 성분마다 돌린 후의 위치를 계산하여 배열을 돌린 각 결과를 저장한 뒤, 배열을 모두 돌린 후의 결과를 출력하면 된다. #include #define MAX_N 7 #define pow(i) (1

https://www.acmicpc.net/problem/20005 20005번: 보스몬스터 전리품 입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다. 입 www.acmicpc.net 철저한 구현 문제이다. 각 플레이어가 보스가 있는 장소까지 1초에 한 칸씩 이동한 뒤 1초에 한 번씩 dps만큼의 데미지를 넣는 문제인데, 특별한 알고리즘이 사용되는 것이 아니므로 HP가 양수일 동안 루프하며 각 플레이어의 이동 및 데미지 계산을 진행하면 된다. #include #include #include using namespace std; t..

https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 한 건물이 최대 3개 건물에 영향을 미친다는 말은, 곧 한 건물은 최대 3개 건물의 필요 조건이라는 말이다. 즉 어떤 건물을 짓기 위해선 4개 종류 이상의 건물을 지어야 할 수도 있다. 모든 종류의 건물의 개수와, 해당 건물을 짓기 위해 더 지어야 하는 건물 종류의 수를 배열에 저장한다고 하자. 즉 건물이 건설되거나 파괴될 때마다 해당 건물 종류의 개수를 1씩 증감..

https://www.acmicpc.net/problem/23349 23349번: 졸업 사진 첫째 줄에 학교가 공지할 것으로 예상되는 혼잡 (장소, 시간대) 쌍을 공백으로 구분하여 출력한다. 이때 시간대는 조건을 만족하는 가장 긴 시간대를 의미한다. www.acmicpc.net 각 촬영을 선분, 촬영의 시작 시간과 종료 시간을 시작점과 끝점으로 보면, 이 문제는 라인 스위핑을 이용해 선분이 가장 많이 겹치는 구간을 찾는 문제이다. 이 때 촬영 장소, 즉 선분의 종류가 문자열로 구분되므로, 라인 스위핑을 위해 각 점을 정렬할 때 선분의 종류를 최우선으로 두어 정렬하면 각 종류 별로 선분을 나누어 저장할 필요 없이 빠르게 라인 스위핑을 실행할 수 있다. #include #include #include #in..

https://www.acmicpc.net/problem/15973 15973번: 두 박스 표준 입력으로 두 박스의 정보가 한 줄에 하나씩 주어진다. 각 박스의 정보는 왼쪽 아래 꼭짓점 좌표 (x1, y1)과 오른쪽 위 꼭짓점 좌표 (x2, y2)로 구성되는데 이들 좌푯값 x1, y1, x2, y2 (x1 < x2, y1 < y2) www.acmicpc.net 두 사각형 a, b에 대해, a.x1< a.x2, a.y1 < a.y2, b.x1 < b.x2, b.y1 < b.y2 네 식이 모두 조건에 의해 성립한다. 따라서 a.x2 < b.x1, b.x2 < a.x1인 경우 두 사각형은 x축 좌표에 대해 서로 만나지 않고, a.y2 < b.y1, b.y2 < a.y1인 경우 두 사각형은 y축 좌표에 대해 만..

https://www.acmicpc.net/problem/7347 7347번: 플립과 시프트 이 퍼즐은 m개의 검은색 원판과, n개의 흰색 원판으로 이루어진 임의의 수열(sequence)이 타원형 모양의 트랙에 배치되어 있는 구조입니다. 또 이 게임에서는 플립(flip)이라는 동작을 할 수 있는 디 www.acmicpc.net 우선 트랙의 어느 한 지점을 끊어 타원형 트랙을 직선형 트랙으로 사용한다고 생각해보자. 트랙 위 어느 디스크를 중심으로도(각 끝의 두 디스크를 제외하고) 회전 가능하고 회전 전/후의 좌표 차이는 2 혹은 그 배수이므로, 홀수번째에 있는 모든 디스크는 서로 교환이 가능하고 짝수번째에 있는 모든 디스크 역시 서로 교환이 가능하다. 이 때 모든 검은 디스크를 한 곳으로 모은 경우 검은 ..

https://www.acmicpc.net/problem/23350 23350번: K 물류창고 K사의 물류창고를 운영하는 도커 씨는 오늘 발주를 처리하기 위해 N 개의 컨테이너들을 적재해야 한다. 도커씨는 이 일을 하나의 로봇을 이용해 처리하려 한다. 로봇은 컨테이너를 옮길 때마다 www.acmicpc.net 모든 컨테이너를 컨테이너의 큐 q1에 넣은 뒤, O(n ^ 2)의 시간에 걸쳐 다른 큐 q2에 우선순위의 오름차순으로 정렬되게 넣는다. 그 다음 q2의 모든 컨테이너를 컨테이너의 스택 s1에 넣는데, 이 때 우선순위가 같으면서 무게가 무거운 컨테이너를 스택에 넣을 경우 우선순위가 같으면서 더 가벼운 컨테이너를 컨테이너의 스택 s2에 임시로 넣은 뒤 q2의 컨테이너를 s1에 놓고, 다시 s2의 컨테이..