코딩못하는사람

CCW ( Counterclockwise) 말 그대로 시계 반대 방향이다. 외적을 이용하여 유도할 수 있다. CCW알고리즘을 이용하여 세점의 방향성을 알 수 있다. 1. 반시계 방향인 경우 2. 시계 방향인 경우 3.세 점이 평행한 경우 출처: https://jason9319.tistory.com/358 [ACM-ICPC 상 탈 사람] 각각의 점을 A(x1, y1) , B(x2, y2), C(x3, y3) 이라고 좌표를 두고, A,B,C 순서로 방향관계를 구한다면, CCW 함수의 return값은 x1y2 + x2y3 + x3y1 - (x2y1 + x3y2 + x1y3) 이 된다.(신발끈 공식과 같다) RETURN값이 음수이면 시계방향. 양수이면 반시계방향. 0이면 세점이 평행하다. 이 알고리즘을 이용하여..

플로이드-와샬 알고리즘 다익스트라 알고리즘이 한 정점에서 모든 정점까지의 최단거리를 구해주는 알고리즘이라면 플로이드-와샬 알고리즘은 모든정점에서 모든정점으로의 최단거리를 구해주는 알고리즘이다. 다이나믹 프로그래밍을 기반으로 거쳐가는 정점을 기준으로 한다는 특징이 있다. 다익스트라와 다른점은 다익스트라는 힙을 이용하여 일차원 배열에 값을 나타냈으므로 입력을 받을 때 adj[시작점]=(가중치,목적지)를 받았다면 플로이드는 2차원배열 adj[시작점][목적지]=가중치로 저장한다는 차이가 있다. 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다. 식으로 설명해보자면 현재의..

유니온 파인드 말 그대로 집합,공동체를 찾는다는 것이다. 집합으로 묶어서 풀면 좋은 문제를 풀 때 효율적으로 풀기좋다. 특히 집합끼리 묶는것을 쉽게 만들어 준다. 모든 원소들을 자기 자신을 부모노드로 초기화 한다. 집합을 합치는 것은 부모노드를 같게 만들어줌으로써 집합을 만들 수 있다. 같은집합에 속해있는것은 find를 통해 부모노드를 찾는 함수를 활용하여 같은 부모노드를 가르키면 같은 집합,아니면 다른 집합에 포함되있는 것이다. 유니온 파인드에는 3가지 과정이 있다. 1.각자 자신으로 부모노드를 초기화한다. 2.find(부모노드 찾기) def find(v): if parent[v]==v: return v else: parent[v]=find(parent[v]) return parent[v] 사실 els..

두개의 문제는 전위,중위,후위순회을 활용해서 문제를 풀어봐야한다. 2263 트리의 순회 https://www.acmicpc.net/problem/2263 1.접근 생각하기 어려웠지만 직접 트리를 그려서 중위탐색과 후위 탐색을 해보면 전위 탐색을 어떤식으로 해야할지 보였다. 2.풀이 중위순회과 후위순회을 그려보면 규칙을 찾을 수 있다. 후위 탐색된 리스트에서 맨 마지막 값은 중위 순회의 루트노드일 것이다.따라서 중위 탐색에서 그 루트노드의 인덱스를 구해서 왼쪽 오른쪽 나눠서 재귀적인 문제로 만들어 풀면 된다. 여기서 후위순회에서 구한 루트값의 인덱스를 구할 때 일일이 탐색하게 되면 시간초과가 날게 분명하므로 for i in range(n): num[in_order[i]-1]=i 루트값이 어디있는지 인덱스를..

1.접근 모든 정점을 기준으로 DFS를 들어가보는 생각밖에 나지 않아서 풀어봤지만 시간초과가 났다(2≤V≤100,000) 도저히 생각나지 않았는데 트리의 지름을 구하는 쉬운 방법이 있었다. 2.풀이 트리의 지름을 구하려면 임의의 점을 잡고 그 점으로부터 최대거리를 가진 곳의 인덱스에서 다시 최대 거리를 구하면 그것이 지름이 된다.(처음 임의의 점에서 최대거리를 구할 때 트리의 지름과 겹치는 부분이 생길 수 밖에 없기 때문에 이라고 한다.) 따라서 DFS를 두번 써주면 된다 (임의의 점,임의의 점에서의 최대 거리 인덱스) 트리의 지름을 구하는 공식은 이곳에 자세히 있다.https://blog.myungwoo.kr/112 3.코드 4.배운점 DFS나 재귀를 쓸때는 습관적으로 sys.setrecursion을 ..

https://www.acmicpc.net/problem/1086 1.접근 방문했던곳들의 상태를 표기하기 쉽도록 비트마스크를 사용하고 n이 15일때 15!로 숫자가 크므로 DP를 사용해줘야 한다. 2.풀이 분모를 N!,분자를 k로 나눠떨어지는 경우의 수로 두는 문제이다.그래서 나는 DP배열을 DP[방문한곳][현재 나머지]로 만들고 DP[방문한곳][현재 나머지]=방문할 수 있는 곳들에서의 경우의 수 합 으로 점화식을 만들었다.그렇게 DFS를 사용하여 방문했던 곳이 나오면 그대로 값을 리턴하고 만약 모든 곳을 방문하고 나머지가 0일 때는 1을 리턴해주는 함수DFS를 만들었다. 나머지는 (이번에 추가하는 숫자*10**현재수의 길이) 현재 나머지를 더하고 k로 나눠주면서 저장하면 된다. DP를 0으로 초기화 해..

비트 마스크란? 비트는 컴퓨터에서 다루는 최소 단위이다. 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술을 비트마스크 라고 한다 프로그래밍을 하며 비트마스크가 왜 필요한지 알아봤다. 비트연산을 통한 삽입, 삭제, 조회 등이 간단해짐 더 간결한 코드 작성이 가능 더 빠른 연산이 가능 비트마스크를 이용한 정수 표현으로 다이나믹 프로그래밍이 가능함 사실 4번 DP를 활용하기 위해 파이썬을 이용해서 비트마스크를 쓰는 방법을 연습했다. DFS를 할때 내가 방문했던 곳들의 상태를 저장하기 까다로울텐데 비트마스크를 쓰면 간단하게 쓸 수 있다.(n이 작다면) 파이썬에는 bin함수가 내장되있어서 쉽게 2진수로 출력이 가능하다 기본 계산 AND연산 bin(0b1010011010 & 0b110110110..