본문 바로가기

분류 전체보기165

[백준/Python] 14425번 문자열 집합 문제 ■ 14425번 문자열 집합 문제 ■ 코드 풀이 처음에는 리스트를 활용하여 풀었습니다. 시간 초과는 나오지 않았지만, 상당히 시간이 오래 걸렸습니다. 코드 개선을 위해 다른 분들의 글을 참고하니, 재미있는 사실을 발견했습니다. import sys N, M = map(int, sys.stdin.readline().split()) S = [] count = 0 for _ in range(N): word = sys.stdin.readline().strip() S.append(word) for _ in range(M): check = sys.stdin.readline().strip() if check in S: count +=1 print(count) 파이썬에서는 set 또는 딕셔너리와 같은 자료형이 리스트 대.. 2023. 5. 26.
[백준/Python] 10815번 숫자 카드 문제 ■ 10815번 숫자 카드 문제 ■ 코드 풀이 문제를 보자마자 느낀 것은 배열의 크기가 비정상적으로 크다는 것이었습니다. 그러나 아무리 궁리해서 풀어도 시간 초과가 나오더군요. 그래서 인터넷에서 찾으니, 이 문제의 핵심은 '큰 배열을 얼마나 효과적으로 탐색할 수 있는가'였습니다. 그리고 여기서 이진 탐색이라는 기초적인 알고리즘에 대해 배웠습니다. 이진 탐색은 오름차순으로 정렬된 리스트의 목록에서 절반씩 탐색 범위를 줄여가며 목표를 찾습니다. 자세한 설명은 코드 아래에 링크로 넣어두었습니다. 아래는 코드입니다. 핵심은 while문인데, 중간 지점을 갱신하는 과정입니다. 중간 지점이라 함은 start와 end 포인트의 절반 지점을 의미합니다. 예를 들면, 0과 100 사이의 범위에서 목표가 77일 경우 중간.. 2023. 5. 23.
[백준/Python] 18870번 좌표 압축 문제 ■ 18870번 좌표 압축 문제 ■ 코드 풀이 여러분, 좌표 압축에 대한 개념을 알고 있으신가요? 저는 이 개념을 몰라서 문제를 한참 읽었습니다. 역시 알고리즘이란 배워도 배워도 끝이 없네요. 좌표 압축이란 좌표를 정렬하고 이를 순서로 표현한 것입니다. 예를 들어 볼까요? 먼저 1, 50, 1000, 50,000, 10,000,000의 5가지 숫자가 있다고 가정하겠습니다. 이 숫자를 그냥 심플하게 1, 2, 3, 4, 5로 표현한 것이 좌표 압축입니다. 이런 맵핑은 특히 입력받는 숫자의 범위가 아주 큰 경우에 유용합니다. 예를 들어 입력값이 -10억부터 10억까지이고 이 사이에서 어떤 연산을 해야 할 경우, 20억 개의 숫자를 모두 업데이트하는 것은 비효율적입니다. 그저 입력받은 숫자들을 정렬하고 순위로.. 2023. 5. 22.

티스토리툴바