BOJ
-
[1600] 말이 되고픈 원숭이BOJ 2021. 9. 5. 01:28
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 4방향 bfs에서 제한적인 방향데이터 추가가 필요하다. 제한적이다는 의미는 더 빠른대신 횟수가 제한되어있다는 뜻이다. 그렇기에 현재의 상태를 나타낼 변수를 아래처럼 구성했다. {R, C, cnt, turn} cnt : 더 빠른 방향데이터를 사용한 횟수 (k번 사용하면 더 사용할 수 없다) turn : 현재의 [R][C]까지 걸린 시간, 목표에 도달하면 출력할 값이다. 그렇기에 vi..
-
[17142] 연구소 3BOJ 2021. 9. 2. 23:52
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 백트래킹 + BFS, 여기에 아래에 대한 예외처리를 요한다. -> '0'으로 표현되는 빈칸과 달리, '*'로 표현되는 비활성 바이러스에 대한 탐색은 '가중치가 없다'. 정확히는, 빈칸에 대해서는 가중치가 1, 비활성바이러스에 대해서는 가중치가 0일때의 최단거리를 구해야한다. 이외의 조건은 상수시간내에 처리할 수 있는 조건들이다. 예를들어, '모든 빈칸에 바이러스를 퍼뜨릴 수 없다면 -1을 출력' 하는 조건..
-
[17609] 회문BOJ 2021. 9. 2. 10:25
https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 회문에대한 판별은 여기를 참고하자. [1259] 팰린드롬수 :: Dizlet-Algorithm (tistory.com) [1259] 팰린드롬수 https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 dizlet.tistory.com 유사회문에..
-
[2568] 전깃줄 - 2BOJ 2021. 9. 2. 10:17
https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 잘 생각해보면 아래와 같은 문제라고 할 수 있다. -> 가장 긴 증가하는 부분수열의 최적해 + 최적해역추적 N이 10만이고, 시간제한이 1초이므로 O(NlogN)으로 구현해야 한다. 결국 아래문제와 같은 문제라는걸 알 수 있다. https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,0..
-
[1629] 곱셈BOJ 2021. 9. 2. 10:10
https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 분할정복을 이용한 거듭제곱을 구현하면 된다. X^N를 구하기 위해서는 X^(N/2)만 알고있으면 된다는 사실로부터 시간복잡도를 O(N)에서 O(logN)으로 줄일 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include int a,b,c; long long pow(long long x, long long y) { long long num = 1; while (y > 0) { num %= c; x %= ..
-
[15961] 회전 초밥BOJ 2021. 9. 2. 10:06
https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net KOI 고등부2번 문제라고한다. 직접적으로 알고리즘을 묻는 문제는 아니지만, 연관성 있는 알고리즘을 알고 있어야 떠올리기 쉽긴 하다. 원형 슬라이딩윈도우나 투포인터처럼 구현해주면 되겠다. 1번부터 n번까지의 원형 인덱스를 찾기 위해서, 아래 식으로 1~n의 값을 갖는 다음 인덱스를 구할 수 있다. idx = (idx + 1) % n + 1 이후, 윈도우..
-
[9663] N-QueenBOJ 2021. 9. 2. 09:52
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 유명한 백트래킹 문제이다. 퀸의 이동방식은 가로, 세로, 대각선이다. 체스에서는 퀸(기물)의 '행마'나 '행마법'이라는 표현도 쓰는것 같다. 우리는 아래와 같이 탐색을 진행할 것이다. 1) 한개의 행에는 하나의 퀸만 놓는다. 우리는 당장 놓아야하는 행의 위치를 'depth(level)'로 표현할것이다. 한개의 행에 하나의 퀸을 놓고, 총 N번 반복하면(depth == N) 모든 퀸을 놓은것으로 볼 수 있다. 이 ..
-
[2146] 다리 만들기BOJ 2021. 9. 1. 23:10
https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 쉬워보이지만, 생각보단 쉽지 않다. 떠올릴만한 효율적인 알고리즘들은 대부분 반례로 저격당한다. 결국, 일일히 하나씩 bfs를 돌려봐야 하는데, 사용 알고리즘은 다음과 같다. 입력에는 여러개의 섬이 존재한다. 섬의 개수가 M개 있다면, 이들에 각각 이름을 붙여준다. 1번섬, 2번섬, 3번섬...M번섬으로 하자. 1) 1번섬에서 이을 수 있는 다리의 최단길이를 알아보기 위해, 1번섬을 기준으로 bfs를 돌..
-
[1328] 고층 빌딩BOJ 2021. 9. 1. 22:54
https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 아이디어를 잘 떠올리면 쉽게 풀 수 있다. 아이디어를 못떠올리면 한없이 어려워지는 문제였다. 기본 아이디어는 다음과 같다. 1) N개의 턴을 반복하고, 매턴이 시작하면 이미 지어진 건물의 높이를 1 증가시킨다. 2) 높이 1의 건물을 배치한다. 배치가 끝나면 턴이 종료된다. 2)를 진행할때에, 경우의수는 아래의 3가지로 나뉜다. 1. 맨 왼쪽에 배치하는 경우 -> 왼쪽에서 볼때의 건물의 개수가 1..