Algorithm/Baekjoon (17) 썸네일형 리스트형 [백준] Python - 21920 서로소 평균 문제 링크 https://www.acmicpc.net/problem/21920 21920번: 서로소 평균 첫 번째 줄에 입력될 수들의 개수 $N$이 주어진다. $(2 \le N \le 500,000)$ 두 번째 줄에는 수열 $A$를 이루는 자연수 $A_{i}$ 가 공백으로 구분되어 주어진다. $(2 \le A_{i} \le 1,000,000)$ 수열 $A$에 $X$와 서로 www.acmicpc.net 문제 풀이 처음에는 각 수마다 약수를 구해서 서로소(1 이외의 공약수가 없음)인지 비교하여 풀이하려고 했다. 하지만 계속해서 시간초과 ㅠㅠ 결국 파이썬의 math.gcd()를 사용하여 코드를 완성했다... 아래 더보기는 직접 약수를 구해주는 함수를 구현하여 이용한 코드(다른 블로그 도움..)인데, 시간이 더.. [백준] 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 문제 풀이 이 문제는 정해진 총액 내에서 가능한 한 최대의 총 예산을 결정하는 문제로써, 이분 탐색 알고리즘을 적용한다. 문제에서 상한이 주어지면 이분 탐색 알고리즘 문제인지 고려해.. 이전 1 2 3 다음