문제2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.입력첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.출력L1과 L2가 교차하면 1, 아니면 0을 출력한다.두 선분의 다양한 경우의 수를 ccw값의 부호(외적 결과의 부호)를 기준으로 정리해 보았다.(AB X BC)*(AB X BD) 와 (CD X DA)*(CD x DB)의 부호로 보았을 때+ + 이거나 0 + 이거나 - + 이면 무조건 안 만남0 - 이거나 - - 이면 무조건 만남0 0 이면은 외적 결과의 부호 만으로 알 수 없음! 따라서 0 0인 경우에..

CCW 알고리즘은 2차원 평면 상의 3개의 점의 위치 관계를 알고자 할 때 유용한 기하 알고리즘이다.2차원 평면상에 세 점으로 만들 수 있는 두 개의 벡터의 방향성(시계 or 반시계)을, 두 벡터의 외적을 통해서 파악할 수 있다.두 벡터의 외적 결과가 음수이면 시계 방향, 0이면 직선, 양수이면 반시계 방향이 된다. 외적 (벡터 곱) : u x v = |u||v|sin(seta)두 벡터의 외적 결과는 두 벡터와 수직인 법선 벡터가 된다. (스칼라 x)외적은 내적(스칼라 곱)과 다르게 교환 법칙이 성립하지 않는다. (a x b != b x a)두 벡터의 외적 결과의 크기는 두 벡터가 만들어 내는 평행사변형의 넓이와 같다.두 벡터의 외적 결과의 방향을 알아내기 위해서는 오른손 법칙을 사용하면 된다.오른손으로..

문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.입력첫째 줄에 수열 A의 크기 N(1둘째 줄에는 수열 A을 이루고 있는 Ai가 주어진다.(-1,000,000,000 출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.일단 dp를 채우면서, dp에 저장된 원소의 순서가 arr 상에서 역순인지 아닌지를 파악하고 역순인 원소가 끼어있지 않은 경우에는 lis = dp[:], 역순인 원소가 끼어 있는 경우에는 체크하면서 관리하는 방법으로 해당 문제를 접근해 보았다. 그런데 이러한 방법은 위와 같은 문제가 있기 때문에 다른 방법을 찾아야 했다.lis에서의 역추적lis 알고리즘에서는 fo..

최장 증가 부분 수열(Longest Increasing Subsequence) 문제는 주어진 수열에서 정렬된 가장 긴 부분 수열을 찾는 문제이다.예를 들어 주어진 수열이 10, 20, 10, 30, 20, 50이라고 하면찾을 수 있는 가장 긴 증가하는 부분수열은 10, 20, 30, 50이다.LIS의 길이를 구하기 위한 알고리즘은 두 가지가 있다.1. 시간 복잡도가 O(n^2)인 방법이중 반복문으로 구현되므로 O(n^2)의 시간 복잡도를 요구하는 방법이다.크기가 len(arr)인 dp테이블을 선언한다.각 인덱스(i)를 순회하면서 가능한 LIS의 최대 길이를 채워 넣는다. 이때 최초 인덱스 부터 i 직전 인덱스 까지 값들 중 arr 값이 arr[i] 보다 작은 값들 중, dp 값이 최대인 경우를 찾아 ..

입력첫째 줄에 수열의 크기가 주어짐둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어짐셋째 줄에는 홍준이가 한 질문의 개수가 주어짐넷째 줄부터 M개의 줄에는 홍준이가 한 질문 s,e가 한 줄에 하나씩 주어짐출력총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서대로 출력, 팰린드롬인 경우 1, 아닌 경우 0을 출력풀이 1 : Two-Pointer, Dp : 시간 초과 !# Two Pointer, DP : 시간 초과!import sysn = int(sys.stdin.readline())arr = list(map(int,sys.stdin.readline().split()))m = int(sys.stdin.readline())d = [[None for _ in range(n+1)..

Manacher's algorithm문자열이 주어지면, 포함된 부분 문자열의 회문(팰린드롬) 여부를 빠르게 찾아내는 알고리즘으로, 각각의 문자(i번째)를 중심으로 하는 가장 긴 팰린드롬의 반지름을 dp테이블에 저장하는 방식으로 구현한다.이 알고리즘의 경우, 특정 문자를 중심으로 가지는 팰린드롬을 찾기 때문에 문자의 개수가 홀수개인 부분 문자열의 회문 여부만을 찾아낼 수 있는데, 짝수 길이의 부분 문자열의 회문여부도 찾고 싶으면 각 문자 사이에 “#”와 같은 더미 문자를 넣어서 구현하면 된다. 예) 1,2,2,1 -> #,1,#,2,#,2,#,1O(N)의 시간 복잡도로 부분 문자열의 회문 여부를 찾아낼 수 있다.각각의 문자를 중심으로 하는 가장 긴 팰린드롬의 반지름을 저장하는 dp테이블을 d라고 하면,s..

문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다3. 1을 뺀다정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 자연수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다.이 문제는 입력값의 최대가 10^6으로 매우 큰 반면, 시간 제한은 0.5초이므로 시간 복잡도를 신경쓰지 않으면 시간 초과가 날 가능성이 높다.풀이 1 : 일반적인 bfsimport..

문제왕국은 N개의 행성으로 이루어져 있다. 행성은 3차원 좌표의 한 점으로, 두 행성을 터널로 연결할 때 드는 비용은 min(abs(xa-xb),abs(ya-yb),abs(za-zb))이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오입력첫째 줄에 행성의 개수 N이 주어진다 (1다음 N개의 줄에는 각 행성의 x, y, z 좌표가 주어진다.출력첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.이 문제의 시간 제한은 1초이고, 입력 값은 최대 100,000개 이므로 O(n^2)으로 코드를 짜게 되면 시간 초과가 발생하게 된다.잘못된 풀이 : 완전 탐색 + 크루스칼 ->..