분류 전체보기
-
[5639] 이진 검색 트리BOJ 2021. 9. 5. 01:42
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 숫자의 대소관계로 탐색범위를 두개씩 쪼개준다. 분할정복같은 느낌으로 접근하면 되며, 이를 재귀로 구현했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include using namespace std; int a[10001], x, cnt; void f(int start, int e..
-
[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..
-
[LPS] Longest Palindrome Substring / Subsequence알고리즘 2021. 9. 3. 20:15
입력으로 문자열이 들어온다. 문자열의 substring / subsequence중 Palindrome을 만족하는 문자열의 최대길이를 구해야한다. 결론적으로 subsequence는 O(N^2), substring은 O(N)의 시간복잡도를 갖는다. 그 이유에 대해서 알아보자. ※ N = 문자열의 길이 ※ 문자열은 0부터 n-1의 인덱스를 갖는다. 1. 가장 먼저 떠올릴만한 방법은 (L, R)을 브루트포스로 구성하는 방법이다. L의 범위는 0부터 n-2까지, R의 범위는 L+1부터 n-1까지 돌려준다. 여기에 O(n^2)의 시간이 소요된다. 이후 팰린드롬에 대한 판별은 구성된 문자열의 길이 M만큼의 시간이 소요된다. M은 1~N의 값을 갖기에, O(N^3)의 시간복잡도를 갖는것으로 생각할 수 있다. 더 정확히..
-
[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) 모든 퀸을 놓은것으로 볼 수 있다. 이 ..