안녕

0. 문제 링크 https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 1. 풀이 방법 문제를 보자마자 BFS로 풀려고 했다. 여기서 키포인트는 비어있는 칸에 방문했는데, 근처에 쓰레기가 있다면 해당 비어있는 칸을 다른 어떤 값으로 변경해줘야 한다. 아 그리고 문제를 잘 읽어야 한다. 처음에 문제 잘못 읽어서 조금 고생했음 풀이 방법은 비교적 쉽다. 비슷한 류의 문제를 풀어서 그런가 쉽게 느껴졌음 왜냐면 최적의 조건이 딱 ..

0. 문제 링크 https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 1. 풀이 방법 문제를 보고 살짝 투포인터로 풀까 고민했는데, 그렇게 풀면 무조건 시간 초과가 날 것 같아서 포기했다. 양쪽을 한 번에 봐야 하나 싶었는데, 생각을 좀 해보니까 양쪽을 한 번에 볼 필요가 없었음 그냥 왼쪽을 봤을 때의 개수를 세고, 오른쪽을 봤을 때의 개수를 세면 되는 일 ! 그러면 이제 특정한 방향을 봤을 때의 개수와 그때의 건물 번호는 어떻게 세야 할까? 처..

P = NP임을 증명하려면 NP에 속한 각각의 문제에 대해 문제를 풀 수 있는 다항 시간 알고리즘을 찾아야 합니다. 하지만 이 작업은 단순화할 수 있습니다. 즉, 많은 문제 중에서 하나만 다항 시간 알고리즘을 찾으면 됩니다. 하나만 다항 시간 알고리즘을 찾으면, 나머지 문제들도 마찬가지로 P에 속하게 되는 NP-Complete에 대해 알아보겠습니다. 우선 알아보기 전에 이론의 기초가 되는 CNF-Satisfiability에 대해 알아봐야 합니다. 그리고 마지막으로 지금까지 결정 문제에 대해서만 NP, P를 따졌는데, 이제는 최적화 문제까지 확장한 NP-Hard에 대해서도 알아보겠습니다. 1. CNF-Satisfiability CNF ~ 는 Conjunctive Normal Form의 약자로, 논리식 사이..

이전 글의 Halting Problem을 기억하시나요? 이처럼 진위 판별을 불가능한 문제가 있고, 진위 판별이 불가능한 문제가 있습니다. 간단하게 진위 판별 문제(결정 문제)로 NP를 제한하면 이론을 전개하기가 쉬워집니다. 우선 결정 문제를 한 번 알아봅시다. 1. Decision Problem 그러기 위해선 우선 지금까지 해온 모든 알고리즘들, Decision Problem과 Optimization Problem에 대해 생각해봐야 합니다. 최적화 문제란 답이 최적해라는 말입니다. 하지만 최적화 문제는 결정 문제로 만들 수 있습니다. 참고로 결정 문제는 yes or no 두 가지 정답만 내놓습니다. 예를 들어서, TSP 문제를 생각해봅시다. 우리는 최소 거리를 구하는 알고리즘을 구현했지만, 만약 특정 거..

새로운 알고리즘을 개발할 때, 이 알고리즘이 다루기 어렵다는 것은 무엇을 의미할까요? 현실에서 다루기 어렵다는 것은 취급하기 또는 작업하기 어렵다로 정의하지만, 컴퓨터 과학에서 다루기 어렵다는 것은 "해당 문제를 다항시간(Polynomial-time)에 풀 수 없다"를 의미합니다. 즉 알고리즘의 Worst Case W(n) = O(p(n)) 만족하는 다항식 p(n)이 없다는 뜻입니다. 다항 시간안에 풀 수 있는 알고리즘은 2n, 3n^3, n lg n등이 있습니다. n lg n은 n에 대한 다항식은 아니지만, n lg n < n^2에 의하여 다항시간 알고리즘으로 분류합니다. 따라서 컴퓨터 과학에서 문제가 다루가 힘들다는 것은 특정 알고리즘의 성질이 아니라 문제의 성질이 되어야 합니다. 사실 최악 시간 복..

https://www.acmicpc.net/problem/7450 7450번: Bin Packing The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The fir www.acmicpc.net 코드) def func() -> int: cnt = 0 # bin의 개수 l = 0 r = n - 1 # 뒤에서 찾아야함 w..

앞의 글을 읽으시면 이해에 도움이 됩니다. 2022.04.13 - [Computer Science/알고리즘] - [알고리즘] 동적 계획법 (Dynamic Programming) [알고리즘] 동적 계획법 (Dynamic Programming) 1. 동적 계획법이란? DP (Dynamic Programming)는 코딩 테스트의 절반 이상을 차지하는 알고리즘이라 봐도 무방합니다. DP는 분할 정복과 매우 유사합니다. 하지만 분할 정복은 top-down 방식을 이용하고, D hi-guten-tag.tistory.com 2022.05.27 - [Computer Science/알고리즘] - [알고리즘 - 이론] Branch-and-Bound Strategy (분기한정법) [알고리즘 - 이론] Branch-and-B..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWvzGUKKPVwDFASy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 반복문 쓸 필요도 없고, 그냥 점화식 세워서 문제 풀어버리면 된다. c++) #include using namespace std; int main() { unsigned long long int test, i; cin >> test; for (int j = 1; j > i; if (i == 1){ cout

https://www.acmicpc.net/problem/16563 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net from math import sqrt _ = int(input()) # 필요 없음 k = list(map(int, input().split())) # 자연수들 M = max(k) # 자연수의 최댓값 arr = list(i for i in range(M + 1)) # arr을 초기화 함 for i in range(2, int(sqrt(M)) + 1): # 2부터 M의 제곱근까지만 계산해도 됨 if ar..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net n, m = map(int, input().split()) # 두 개의 자연수 arr = [True] * (m + 1) # True은 소수라는 뜻 arr[0] = arr[1] = False # False은 소수가 아님 # for i in range(2, int((m + 1) ** 0.5)): # 최고 숫자의 루트로 계산해도 되긴 함 for i in range(2, m + 1): # 2부터 최고 숫자까지 에라토스테네스의 체를 계산..