백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 2252번: 줄 세우기 (Python)

접근 위상 정렬에 대한 공부를 하고 나서 풀었다. 위상 정렬은 사이클이 없고, 방향만 존재하는 그래프에서 정점들을 나열하는 방법이다. 학생들의 순서를 앞 학생에서 뒤 학생으로 연결된 한개의 방향 화살표라고 할 때, 뒤 학생에는 진입루트가 한개 증가한 것이다. 주어진 비교 측정들을 모두 확인하여 뒤에 있는 학생들의 진입루트를 한개씩 더해주고 나서 보았을 때, 진입루트가 없는 학생은 가장 앞에 서게 될 것이다. 따라서 진입 루트가 0인 학생들을 모두 queue에 넣고 해당 학생들과 연결된 학생들의 진입루트를 한개씩 없애준다. 이 과정에서 진입 루트가 0이 된 학생은 추가로 queue에 넣어주게 된다. 진입 루트가 0이 되었다는 말은 앞선 학생들이 빠지고 난 상황에서 가장 앞에 있다는 의미이기 때문이다. 코드..

2021. 6. 20. 18:18
코딩/백준 (Python)

백준 5670번: 휴대폰 자판 (Python, PyPy3)

접근 트라이를 이용하여 풀었다. 트라이를 생성하여 입력받는 문자열들을 트라이에 저장해주고, 나중에 평균을 구해주기 위해 문자열을 저장할 때, 해당 string 이 몇번 사용되었는지 각 노드에 저장하는 식을 추가해주었다. 평균을 구할 때에는 해당 노드의 자식 수에 따라서 자식이 한개일 경우 카운트하지 않고, 자식이 있을 경우 각 자식이 몇번 쓰이는지를 체크하여 모두 더해주었다. 더해진 모든 수를 총 단어 수로 나누면 평균 입력 수를 구할 수 있었다. Python 으로는 50% 시간 초과 발생하여 PyPy3으로 문제 해결하였다. 트라이 기본 문제: 2021.06.19 - [코딩/백준 (Python)] - 백준 14725번: 개미굴 (Python) 코드 import sys from collections imp..

2021. 6. 20. 15:51
코딩/백준 (Python)

백준 14425번: 문자열 집합 (Python, PyPy3)

접근 트라이에 insert, search 함수를 구성하여 문제를 풀 수 있었다. 코드 import sys class Node: def __init__(self, key): self.key = key self.children = dict() class Trie: def __init__(self): self.head = Node(None) def insert(self, string): curr_node = self.head for char in string: if char not in curr_node.children: curr_node.children[char] = Node(char) curr_node = curr_node.children[char] def search(self, string): curr_..

2021. 6. 19. 23:58
코딩/백준 (Python)

백준 14725번: 개미굴 (Python)

접근 처음에는 트라이가 무엇인지 모르고 풀었고, 이후에 트라이에 대해 공부하고 다른 분의 코드도 참고하여 트라이를 이용하여 풀었다. 첫번째 풀이는 모든 리스트를 저장 및 sort 한 후, 이전 문자열과 동일한 문자가 몇번 나오는지 체크하여 중복되지 않는 부분부터 결과를 출력하도록 코딩하였다. 트라이를 이용한 방법은 Node 에 자식 노드들을 저장하여 점점 내려가면서 자식들을 순서대로 표시하는 방법이다. 코드1 트라이를 사용하지 않은 코드 import sys n = int(sys.stdin.readline()) array = [] for _ in range(n): tmp = list(sys.stdin.readline().split()) array.append(tmp[1:]) array.sort() for ..

2021. 6. 19. 23:09
코딩/백준 (Python)

백준 10266번: 시계 사진들 (Python)

접근 각도는 1부터 360,000까지의 값을 가진다. 각 시계에 해당하는 0의 요소를 360,000개 가진 리스트 두 개를 만들고, 각각의 시계 사진이 가지는 각도 값들에 해당하는 요소를 1로 바꾸어준다. 그리고 KMP 알고리즘을 이용하여 두 개의 리스트를 비교하면 된다. 주의할 점은 360,000 각도를 지나가서 일치할 수 있기 때문에 첫 번째 시계를 두번 반복해서 표시한다. ex ) [0, 1, 2, 3, 4] [359998, 359999, 0, 1, 2] 왼쪽 두개의 시계 사진은 모두 바늘끼리 1 차이가 나는 5개의 바늘을 표시하고 있지만, 위의 주의점을 확인하지 않으면 KMP 알고리즘을 이용하여 일치하는지 확인할 수 없다. 2021.06.18 - [코딩/백준 (Python)] - 백준 1786번:..

2021. 6. 19. 19:07
코딩/백준 (Python)

백준 1305번: 광고 (Python)

접근 KMP 알고리즘을 이용하면 쉽게 구할 수 있는 문제였다. KMP 알고리즘을 이용하여 failure funtion table 을 구하고 전광판의 길이에서 table의 가장 마지막 값을 빼주면 답을 구할 수 있었다. KMP 알고리즘 기본 문제: 2021.06.18 - [코딩/백준 (Python)] - 백준 1786번: 찾기 (Python) 백준 1786번: 찾기 (Python) 접근 접근 방법은 문제에 주어져 있다. 주어진 방법대로 문제를 풀었는데 혼자서는 40% 시간초과를 넘기기가 힘들어 KMP 알고리즘에 대해 공부도 하고, 다른 분들의 코드를 참고하여 풀 수 있었다 ca.ramel.be 코드 import sys def kmptable(a): n = len(a) table = [0] * n j = 0..

2021. 6. 19. 18:18
반응형