본문 바로가기

전체 글165

[백준/Python] 10816번 숫자 카드 2 문제 ■ 10816번 숫자 카드 2 문제 ■ 첫 번째 코드: 시간초과 먼저 제가 처음 작성했던 코드입니다. 저는 파이썬 딕셔너리를 활용하여 문제를 풀려고 했습니다. 먼저 모든 값을 list로 받고, count 메서드를 활용하여 '숫자: 개수' 쌍의 딕셔너리를 만들었습니다. 그리고 확인해야 하는 숫자를 key로 해서 값이 있으면 개수를 출력하고 없으면 0을 출력하도록 코드를 작성했습니다. 결론적으로 아래의 코드는 시간 초과가 발생했습니다. 코드를 쭉 살펴보니 시간이 크게 소요되는 구간은 list의 값을 하나하나 count 하여 dict를 만드는 구간 정도인 것 같았습니다. 그래서 이 구간을 이미 사전에 정의된 라이브러리를 활용해 두 번째 코드로 바꿔 봤습니다. M = int(input()) card_list =.. 2023. 5. 30.
[백준/Python] 1620번 나는야 포켓몬 마스터 이다솜 문제 ■ 1620번 나는야 포켓몬 마스터 이다솜 문제 ■ 코드 풀이 포켓몬에는 이름과 번호가 있으므로, 딕셔너리 자료유형을 사용해야 한다는 것은 어렵지 않게 추측할 수 있습니다. 그래서 포켓몬 번호가 key이고 이름이 value인 pokenmon_dict를 선언했습니다. 최종 정답을 출력할 때는 try & except 구문을 활용했습니다. 우선 정답 target을 int로 변환해 보고, 성공하면 입력받은 값은 숫자이므로 그대로 key값을 활용하여 이름을 출력합니다. 입력받은 값이 이름이면 int로 변환 시, 'ValueError'가 나오게 됩니다. 이 경우에는 value 값을 이용하여 key값, 이름을 출력하도록 코드를 작성했습니다. 그게 아래의 최초 코드입니다. 그러나 아래 코드는 시간초과가 발생했습니다. .. 2023. 5. 28.
[백준/Python] 7785번 회사에 있는 사람 문제 ■ 7785번 회사에 있는 사람 문제 ■ 코드 풀이 저는 이 문제를 딕셔너리를 활용하여 풀었습니다. 기본적으로 파이썬에서 문자열 탐색은 set이나 dict 자료유형이 속도 측면에서 유리합니다. 그 이유는 해시 테이블(hash table)을 사용하기 때문인데요. 임의의 단어를 숫자로 맵핑하고 이를 인덱스처럼 활용해서 속도가 빠르다고 합니다. (아래 링크의 글에서 제가 처음 배웠기 때문에, 거기에 자세히 적어두었습니다.) 우선 출입 기록을 저장할 수 있는 딕셔너리(record_dict)를 선언합니다. 그리고 사람의 이름을 key값으로 상태가 enter이면 True를, leave이면 False를 value로 저장합니다. 그럼 결과적으로 출입 기록에 'leave'가 없는 사람의 value만 True가 됩니다. .. 2023. 5. 27.
[백준/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.

티스토리툴바