Scat

yongmin's dev blog

알고리즘 정리

"Algorithm"

알고리즘 에라토스테네스의 체 : 찾고자 하는 범위의 최대값의 제곱근까지 2, 3, 4씩 곱한 수들을 제거해나간다. (=배수는 소수가 아님) 제거되지 않은 수들은 소수이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import sys import math def isPrime(num): ...

Posted by Yongmin on October 20, 2021

Python 함수 정리 - Python

"Python"

정리 sort() : 오름차순으로 리스트를 정렬 reverse() : 리스트의 순서를 뒤바꿔주는 정렬 ord() : 문자의 아스키 코드를 리턴하는 함수 ex) ord(a) chr() : 아스키 코드 입력을 받아 문자를 리턴하는 함수 [::-1] : 리스트의 역순으로 읽는다 ex) num = 123 –> reverse_num =...

Posted by Yongmin on October 20, 2021

[BOJ] 1509번 팰린드롬 분할 - Python

"동적 계획법 4"

문제 팰린드롬 분할 풀이 동적계획법을 활용한 문제이다. 팰린드롬이란 앞에서 읽었을 때와 뒤에서 읽었을 때 같은 문자열을 의미한다. palindrome[][] 이중 리스트를 선언한다. palindrome[start][end]는 start에서 end까지 문자열이 팰린드롬인지 아닌지 bool형의 이중 리스트다. 문자열이 한 개인 경우는 모두 펠린드롬이므...

Posted by Yongmin on October 14, 2021

[BOJ] 2836번 수상 택시 - Python

"스위핑"

문제 스위핑 풀이 전형적인 스위핑 문제이다. 정방향으로 가는 루트는 어찌됐든 무조건 M의 거리를 가야한다. 그러므로 역방향만 고려해주면 되는데, 역방향으로 갈 경우는 내려줬다가 다시 정방향으로 가야되므로 2배를 해준다. 역방향으로 가는 루트들을 list에 넣어준 뒤, 시작점의 내림차순으로 정렬해준다. 스위핑 문제에서 했듯이 루트가 이어지는 경우를 ...

Posted by Yongmin on October 13, 2021

[BOJ] 2170번 선 긋기 - Python

"스위핑"

문제 선 긋기 풀이 스위핑, 훑는 문제이다. 시작점을 오름차순으로 sort하고 난 뒤, 선이 이어지는지 안이어지는지 여부를 따진다. 이어진다는 것은 기존의 끝점보다 시작점이 더 작은 경우가 이어진다. 이 때, 끝점은 기존의 끝점과 새로운 끝점 중에 큰 값이 되게 된다. 이어지지 않는 경우는, 기존의 끝점보다 시작점이 더 큰 경우로, 이 경우는 새롭...

Posted by Yongmin on October 12, 2021

[BOJ] 17435번 합성함수와 쿼리 - Python

"최소 공통 조상"

문제 합성함수와 쿼리 풀이 sparse table을 이용한 문제이다. 기존 o(n)의 시간복잡도에서 o(log2(n))으로 시간복잡도를 줄여 정답을 도출하는 문제이다. f1(x), f2(x), f4(x)… f2^(n)(x)의 값들을 dp를 통해 저장해놓는다. 이 때 점화식은 dp[i][x] = dp[i-1][dp[i-1][x]]이다. 그 이후, n...

Posted by Yongmin on October 12, 2021

[BOJ] 3584번 가장 가까운 공통 조상 - Python

"최소 공통 조상"

문제 가장 가까운 공통 조상 풀이 최소 공통 조상(LCA, Lowest Common Ancestor)에 대한 문제이다. 찾고자 하는 node의 부모 노드들을 다 넣는다. 그 이후, 맨 뒤 index인 root 노드에서 차례대로 한개씩 내려오면서 다를 때까지 while문을 진행한다. 달라진다면, 그 직전이 바로 가장 깊은 부모 노드이므로 그것을 출력...

Posted by Yongmin on October 8, 2021

[BOJ] 1766번 문제집 - Python

"위상 정렬"

문제 문제집 풀이 위상 정렬에 대한 문제이다. 최소힙을 통해 상황마다 낮은 값을 출력하게 하면 정답 도출이 가능하다. 파이썬 내에서 heapq는 최소힙이다. heap = []으로 리스트를 선언해 준 뒤, heapq.heappush(heap, i)로 heap에 값을 넣고, heapq.heappop(heap)으로 최소값을 pop하고 return하도록 ...

Posted by Yongmin on October 7, 2021

[BOJ] 3665번 최종 순위 - Python

"위상 정렬"

문제 ACM Craft 풀이 위상 정렬에 대한 문제이다. 해당 index보다 뒷순위에 해당하는 것들이 담긴 인접 리스트와 뒤에 몇명이 있는지를 나타내는 degree배열을 선언해준다. 예를 들어, 5 4 3 2 1 순위라면 5 -> 4, 3, 2, 1 // 4 -> 3, 2, 1 // 3 -> 2, 1 … 이런식이다. 그 이후, dp...

Posted by Yongmin on October 7, 2021

[BOJ] 3665번 최종 순위 - Python

"위상 정렬"

문제 최종 순위 풀이 위상 정렬에 대한 문제이다. 해당 index보다 뒷순위에 해당하는 것들이 담긴 인접 리스트와 뒤에 몇명이 있는지를 나타내는 degree배열을 선언해준다. 예를 들어, 5 4 3 2 1 순위라면 5 -> 4, 3, 2, 1 // 4 -> 3, 2, 1 // 3 -> 2, 1 … 이런식이다. 바뀐 값이 나오면 인접...

Posted by Yongmin on October 6, 2021

FEATURED TAGS
Format BOJ C++ Python Algorithm
ABOUT ME

짱구