Scat

[BOJ] 2252번 줄 세우기 - Python

"위상 정렬"

문제 줄 세우기 풀이 위상 정렬에 대한 문제이다. 순서를 세우는 알고리즘인데, 먼저 entry라는 배열을 선언해준다. 이 배열은 해당 index 앞에 몇개가 있는지를 나타내는 배열이다. 그 다음 연결 리스트를 표현하기 위한 graph를 2중 배열로 선언한다. graph[a].append(b)라는 의미는 a뒤에 b값이 있다는 소리이다. input단계...

Posted by Yongmin on October 5, 2021

[BOJ] 14725번 개미굴 - Python

"문자열 알고리즘 1"

문제 개미굴 풀이 Trie 구조에 대한 문제이다. 해당 값에 해당하는 노드가 없으면 만들고, 있다면 그곳을 따라가고 그 다음 노드를 향하게 하여 계속해서 반복하는 자료 구조이다. 후에 만들어진 자료 구조를 정렬하여 조건에 맞게 DFS로 정답을 도출해낸다. Referece를 참조하였다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 ...

Posted by Yongmin on October 5, 2021

[BOJ] 14425번 문자열 집합 - Python

"문자열 알고리즘 1"

문제 문자열 집합 풀이 Trie 자료 구조를 이용한 문제이다. root에서 add 함수를 이용하여 없는 단어는 추가하고, travel 함수로 root에 없으면 cnt+1이 되게끔 했다. 소스 코드 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 28 29 30 31...

Posted by Yongmin on October 5, 2021

[BOJ] 1069번 집으로 - Python

"기하"

문제 집으로 풀이 가장 짧은 루트인 원점에서 그 점까지의 length를 기준으로 생각한다. 점프를 할 수 있는 경우의 수들을 나눠 생각하는데, 다 걸어서 가는 경우, 최대 점프 횟수로 간다음 나머지를 걸어 가는 경우, 최대 점프 횟수+1로 간다음 넘은 거리만큼 다시 돌아오는 경우, 점프 최대 횟수 + 1로 가는 경우, 총 4가지를 고려하여 가장 작...

Posted by Yongmin on October 2, 2021

[BOJ] 2166번 선분 교차 3 - Python

"기하"

문제 선분 교차 3 풀이 Reference를 참조하였다. 소스 코드 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 import sys input = s...

Posted by Yongmin on September 30, 2021

[BOJ] 7869번 두 원 - Python

"기하"

문제 두 원 풀이 두 원의 관계와 코사인 법칙으로 theta를 구하는 것을 통해 정답을 도출한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import sys from math import * x1, y1, r1, x2, y2, r2 = map(float, input().split(...

Posted by Yongmin on September 29, 2021

[BOJ] 4354번 문자열 제곱 - Python

"문자열 알고리즘 1"

문제 문자열 제곱 풀이 KMP의 failure function을 통해, 해당 문자에 prefix == suffix인 최대길이를 확인한다.(index 1부터 counting하므로, aaaa -> a[3] = 4가 아니라 3이다.) 기존 문자열의 길이에 len(s)-1의 index에 위치한 것의 prefix == suffix인 pi[len(s)-...

Posted by Yongmin on September 28, 2021

[BOJ] 2166번 다각형의 면적 - Python

"기하"

문제 다각형의 면적 풀이 삼각형 넓이 구하는 신발끈 공식으로, 한 점을 기준으로 삼각형을 만들어내서 다 구한다. 이 때, 매 삼각형을 구할 때 부호를 고려하여 빼주고 더해주기를 연산시켜준다. 그 이후 최종 값을 절댓값을 취한 뒤 정답을 도출해낸다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ...

Posted by Yongmin on September 28, 2021

[BOJ] 17387번 선분 교차 2 - Python

"기하"

문제 선분 교차 2 풀이 CCW를 이용하여 선분 교차를 확인하는 문제이다. 선분 교차 1에서는 세 점이 일직선이 되는 경우가 없는 경우이며, 선분 교차 2 문제는 세 점이 일직선이 되는 경우도 포함한 문제이다. CCW를 이용하여 abc와 abd가 서로 반대 방향이면서, cda와 cdb가 서로 반대 방향이면 교차하는 가장 일반적인 경우이다. 세 점...

Posted by Yongmin on September 28, 2021

[BOJ] 11758번 CCW - Python

"기하"

문제 CCW 풀이 벡터 외적으로 0보다 크면 반시계, 작으면 시계, 0이면 평형인 것을 이용하여 정답을 도출해냈다 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import sys from math import * def ccw(x1, y1, x2, y2, x3, y3): return ...

Posted by Yongmin on September 28, 2021

[BOJ] 2252번 줄 세우기 - Python

"위상 정렬"

[BOJ] 14725번 개미굴 - Python

"문자열 알고리즘 1"

[BOJ] 14425번 문자열 집합 - Python

"문자열 알고리즘 1"

[BOJ] 1069번 집으로 - Python

"기하"

[BOJ] 2166번 선분 교차 3 - Python

"기하"

[BOJ] 7869번 두 원 - Python

"기하"

[BOJ] 4354번 문자열 제곱 - Python

"문자열 알고리즘 1"

[BOJ] 2166번 다각형의 면적 - Python

"기하"

[BOJ] 17387번 선분 교차 2 - Python

"기하"

[BOJ] 11758번 CCW - Python

"기하"

FEATURED TAGS

ABOUT ME