https://www.acmicpc.net/problem/5612 문제 1분 단위로 터널에 들어간 차량의 수와 터널에서 나온 차량의 수가 주어졌을 때, 터널에는 차량이 최대 몇 대 있었는가? 풀이 처음에 터널에 있었던 차량 수에서, 매분 들어간 차량의 수를 더하고 나간 차량의 수를 빼면 된다. 중간에 한번이라도 터널 안 차량의 수가 음수가 되면 0을 출력하는 것에 주의하면 정답. 코드

링크 1: https://uva.onlinejudge.org/...problem=1859 링크 2: BOJ 2133 - 타일채우기(https://www.acmicpc.net/problem/2133) 문제 타일 시리즈 중에 하나로, 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 문제이다. 풀이 3×n 크기의 벽을 채우는 경우의 수를 \(f(n)\)이라고 하자. 다음은 전개될 수 있는 모든 모양이다. 모양이 반복되는 경우까지만 적었다. .... x... .... f(n) = .... g(n) = .... or .... .... .... x... A..... AA.... A..... or ...... ...... ...... A..... ACC... ACC... ACC... A..... -> A....

링크: https://www.acmicpc.net/problem/17142 문제 연구소에 이미 존재하는 바이러스들 중 \(m~(2\le m \le 10)\)개를 활성 상태로 바꾸어 바이러스를 퍼뜨리는 문제이다. 그 때, 연구소의 모든 빈칸에 바이러스가 퍼지게 하는 최소 시간을 구해야 한다. 풀이 연구소에 존재하는 바이러스 들 중 \(m\)개를 골라야한다. DFS 같은 방법으로 고를 수 있지만, next_permutation을 사용하면 간단하다. 4개 중 2개를 고르는 조합은 0011 → 0101 → 0110 → 1001 → 1010 → 1100 순으로 진행된다. 이런 특징을 사용하여 매번 적당히 \(m\)개를 선택하여 플러드 필(Flood Fill, BFS)을 한다. 모든 빈칸을 방문한다면 그 때의 탐색..

링크: https://www.acmicpc.net/problem/17140 문제 R 연산을 기준으로 구현하고, C 연산은 행/열만 바꿔서 똑같이 진행하면 된다. 한 행을 읽고 map과 같은 적당한 자료구조에 (수, 등장한 횟수)의 형태로 저장한다. 삽입과 조회, 수정 모두 \(O(logN)\) 만큼 걸린다. 정렬 기준은 1. 등장한 횟수가 적은 순, 2. 수의 크기가 작은 순이다. 정렬을 위해 map에 저장된 내용을 추출한다. 반복자 등으로 자료구조를 순회하면서 (수, 등장한 횟수)를 배열로 바꿔 정렬하고, 정렬된 순서로 새로운 행에 덮어씌운다. 바로 덮어씌워도 상관없으나, 이전 행보다 길이가 짧아지는 경우에 주의해야한다. (ex. [3, 1, 1, 1, 1, 1] → [3, 1, 1, 5, 0, 0] ..

링크: https://www.acmicpc.net/problem/14852 문제 타일 시리즈 중 하나인데, 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 먼저 왼쪽부터 타일을 채워가면서 생기는 모양에 따라 부분 문제를 만들어나간다. 아래와 같은 모양을 각각 \(f(n), g(n)\)이라고 정의해보자. \(g(n)\)은 첫 번째 열 중에서 한 칸만 채워진 경우이다. 두 모양이 채워질 수 있는 Base case를 이렇게 정의하자. \(f(0)\)은 모든 타일을 채웠다는 뜻으로 1개로 센다. \(g(0)\)은 불가능한 모양이므로 0이다. 먼저 \(g(n)\)은 아래와 같이 세 가지 모양으로 전개될 수 있다. 첫 번째 열의 빈칸에 1×1짜리 타일을 하나 채우면 ..

링크: https://www.acmicpc.net/problem/9375문제해빈이가 가진 의상들의 이름과 종류가 주어지면, 가능한 모든 경우의 수는 몇 개인지 묻는 문제입니다.문제에서 같은 이름을 가진 의상은 존재하지 않으므로 이름은 중요하지 않고 해당 종류만 구분하면 됩니다.가지고 있는 모자가 2개라면 모자만으로 가능한 경우는 3가지입니다. 첫 번째를 쓰거나, 두 번째를 쓰거나, 아무것도 쓰지 않거나 이렇게 총 3가지입니다. 어떤 종류를 \(n\)개 가지고 있다면 선택 가능한 수는 \(n+1\)개이고, 나올 수 있는 모든 가짓수는 각 종류마다 가능한 경우를 모두 곱한 값입니다.위 그림의 경우에는 \(3 \times 4 \times 2~=~24\) 이지만, 문제에서 알몸이 아닌 상태 즉 모두 선택하지 않..

링크: https://programmers.co.kr/learn/courses/18/lessons/1878문제코딩 테스트의 데모 문제, 연습 문제로 많이 등장하는 문제입니다.직사각형을 나타내는 네 개의 꼭짓점 중 세 개의 좌표가 주어졌을 때, 나머지 한 좌표를 구하는 문제죠.좌표의 범위에 따라 해결 방식이 다를 수 있습니다. 여기서는 좌표의 범위가 10억까지인 프로그래머스 문제의 풀이를 다룹니다. (백준에서는 1000 이하의 정수)네 점의 x좌표들은 모두 2번씩 등장합니다. 마찬가지로 y좌표들도 2번씩 등장해야하죠. 그럼 x, y 좌표들 중 1번만 등장한 녀석들이 문제의 정답입니다.이것을 카운팅하는 것이 곧 문제를 해결하는 것인데, 좌표가 10억까지 주어지는 경우라면 해시(Hash)와 같은 적당한 자료구..

링크: https://www.acmicpc.net/problem/1405문제동서남북 각 방향으로 이동할 확률이 주어지고, 로봇이 동선을 겹치지 않게 n번 움직일 확률을 구하는 문제이다.(0, 0)부터 출발한다고 생각하면 동서남북 경계의 끝은 (14, 0), (-14, 0), (0, 14), (0, -14) 일텐데 음수를 없애기위해 출발점을 (15, 15)로 설정하면 편하다.좌표값을 들고 다니는 이유는 동선이 겹쳐서는 안되기 때문에, 다시 말해 이미 방문한 위치는 다시 방문하지 않도록 하기 위해서이다.어떤 한 위치에서 생각했을 때, 동쪽으로 이동한다면 동쪽에서 나오는 모든 확률은 (그 위치에서 발생하는 확률 * 동쪽으로 이동할 확률)이 된다. 이걸 동서남북 모든 방향과 모든 위치마다 반복한다면 정답을 구할..