본문 바로가기

Algorithm

(48)

[백준] Python - 10816 숫자 카드 2 문제 링크 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 풀이 처음에는 상근이가 가지고 있는 숫자 카드 리스트의 개수를 count 함수를 사용하여 구하려 하였지만, 시간 초과가 발생했다. 그래서 알게된 것이 Counter 모듈이다. 또 다른 풀이 방법으로 Dictionary를 사용하여 개수를 카운트 해주었다. 1. Counter 2. Dictionary 전체 코드 1. Counter 사용 from col..

[백준] Python - 10989 수 정렬하기 3 문제 링크 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 이 문제는 메모리 할당에 주의해서 풀어야 했다. 숫자를 입력 받아서 정렬 함수를 사용하는 것으로는 메모리 초과가 되기 때문이다. 문제를 보면, 10,000보다 작거나 같은 자연수라고 되어있다. 이에 따라 처음부터 저 만큼의 메모리를 할당해두고, 입력되는 주어지는 수들의 개수를 카운트하여 해결하였다. 전체 코드 from sys import stdin input = stdin.readline num..

[백준] Python - 1931 회의실 배정 문제 링크 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 풀이 이 문제의 포인트는 회의가 끝나는 시간을 우선순위로 정렬해야 한다는 것이다. 회의가 빨리 끝날수록 다음에 시작할 수 있는 회의가 많기 때문이다. 회의 끝나는 시간을 우선순위 정렬 이전 회의 끝나는 시간

[백준] Python - 17609 회문 문제 링크 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 풀이 이 문제는 회문(팰린드롬(palindrome))인지 혹은 유사회문인지 아닌지를 판단하는 문제였다. 그래서 나는 입력받은 문장에 대해서 제일 처음과 끝을 가리키는 포인터를 두 개 두고, 문장의 가운데로 좁혀가면서 확인하는 방법을 사용했다. 이 때, 주의할 점은! 앞 문자와 뒷 문자가 다를 경우에, 앞 문자 제거 후 회문인지/ 뒷 문자 제거 후 회문인지에 대한 검사를 두 번 다 해야한다. 왜냐하면 아직은 어디..

[백준] Python - 20291 파일 정리 문제 링크 https://www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net 문제 풀이 입력받은 문자열에서 확장자만 잘라낸다. 확장자를 키값으로 가지는 딕셔너리에 값을 업데이트 한다. 만약 이미 딕셔너리에 추가된 확장자라면 값을 1 더해준다. 딕셔너리에 없는 확장자라면, 새롭게 확장자를 키값으로 값을 1 추가해준다. 딕셔너리의 키값을 기준으로 오름차순 정렬하여, 키와 값을 출력한다. 다음엔 2번의 복잡한 과정 대신 defaultdict를 사용해 봐야겠다! 전체 코드 f..

[백준] Python - 11279 최대 힙 문제 링크 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 문제 풀이 파이쎤 heapq 모듈만 알고 있으면 쉽게 풀 수 있는 문제였던 것 같다. 주의할 점은 heapq 모듈이 기본적으로 최소힙으로 구현되었기 때문에 최대힙으로 바꿔주기 위해 (-n, n) 처럼 튜플로 만들어서 추가해주는 것이다. 혹은 - 를 곱하여 음수로 저장하는 것도 방법이다! Heap에 (-n, n) 튜플 push() Heap에서 두번째 원소를 pop() ..

[백준] Python - 2512 예산 하아... 이 문제.. 금방 풀릴 것 같더니, 은근히 오래 걸렸다..ㅠㅠ 난 이분탐색 알고리즘 문제를 풀 때마다 left, right 범위를 포함하는 부분이 너무 어렵다. 풀고 나서도 찝찝한 부분이다. 문제 링크 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제 풀이 이 문제는 정해진 총액 내에서 가능한 한 최대의 총 예산을 결정하는 문제로써, 이분 탐색 알고리즘을 적용한다. 문제에서 상한이 주어지면 이분 탐색 알고리즘 문제인지 고려해..

[백준] Python - 9012 괄호 문제 링크 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 풀이 이 문제는 스택을 활용해서 풀었다. 문제를 보자마자 별 생각없이 쉽게 풀긴 했는데, 현재 하고 있는 코테 스터디에서 간단한 사칙연산만 해주어도 같은 결과가 나왔다. 시간 효율성에서도 비슷했다. 전체 코드 from sys import stdin input = stdin.readline num = int(input()) ps = [list(input..

티스토리툴바