728x90 반응형 백준 알고리즘55 [백준 17386][파이썬] 선분 교차 1 https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 이전 포스팅에서 CCW 알고리즘을 활용하여 선분 교차하는 방법에 대해서 배웠다. https://growth-coder.tistory.com/163 이 방식을 그대로 사용하면 된다. 우선 세 점이 일직선 상에 존재하는 경우가 없다고 했으므로 ccw의 값이 0인 경우는 신경쓰지 않아도 된다. 그럼 예외 사항은 아래 그림과 같은 경우만 신경쓰면 된다. 이 경우는 선분 AC를 기준으로 한 번, 선분 BD를 기준으로 두 번 .. 2023. 4. 25. [백준 13023][파이썬] DFS 구현 방법 DFS 구현 방식에는 여러 방법들이 존재하는데 DFS 문제를 풀 때마다 헷갈려서 이번에 확실하게 외우기 위해서 포스팅을 작성한다. https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 전형적인 DFS 문제이다. 연결 여부 가장 먼저 노드끼리 연결 여부를 판단해야 한다. 이 방법에는 크게 인접 행렬 방식과 연결 리스트 방식이 있다. 5개의 노드가 있다면 5x5 행렬을 만들어서 arr[a][b]가 True라면 a와 b가 연결되어 있다는 것을 의미한다. 1. 인접 행렬 위 문제에서 예제 입력1을 기준으로 행렬을 만들어보면 다음과 같다. 0 1 2 3 4 0 F.. 2023. 4. 10. [백준 17298][파이썬] 오큰수 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 우선 문제를 봤을 때 가장 먼저 생각나는 알고리즘은 수열의 모든 값을 조사하는데 각각의 수열마다 자신 다음 값부터 끝까지 자신보다 큰 값이 나올 때까지 찾는 방법이다. 9 8 7 6 ... 과 같이 내림차순으로 정렬된 수열이 최악의 경우인데 이럴 경우 1부터 n까지 더한 횟수를 반복해야 한다. 즉 시간 복잡도가 O(N^2)이 된다. n의 최대값이 1,000,000이고 파이썬은 1초에 1억번 정도의 연산을 할.. 2023. 3. 31. [백준 9251][파이썬] LCS (최장 공통 부분 수열) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net dp[x][y]를 다음과 같이 정의한다. dp[x][y]는 첫 번째로 입력받은 문자열을 s1이라 하고 두 번째로 입력받은 문자열을 s2라고 한다면 s1에서 x번째 문자까지와 s2에서 y번째 문자까지를 비교했을 때 최장 공통 부분 수열의 길이이다. 예를 들어 dp[2][4]라고 한다면 "AC"와 "CAPC"의 최장 공통 부분 수열의 길이인 "AC"즉, 2.. 2023. 3. 18. 이전 1 2 3 4 5 6 7 8 ··· 14 다음 728x90 반응형
