[프로그래머스] 무지의 먹방 라이브 - Python
2022. 1. 1. 23:08
Algorithm/프로그래머스
문제 https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 풀이 이 문제는 효율성을 고려해서 풀 때 어떻게 해야할지 고민을 좀 하게된 문제입니다. 효율성을 고려하지 않은 경우 문제에 주어진 대로 시간이 1초씩 줄어듬에 따라 배열에 있는 숫자를 순차적으로 1씩 빼주는 과정을 거쳐주면 쉽게 풀립니다. 하지만 효율성 테스트의 제한 사항 입력 크기를 보면 이러한 방법은 당연하게도 시간초과가 날 것 같아 다른 방법을 생각해야만 했습니다. 가장 먼저 떠오른 생각은 다음과 같습니다. k 값이 충분하다면 음식을 다 먹는데 드는 시간이 가장 적은 것부터 처리해버리자! 위와 같은 생각을 거치니 우선순위 ..
[프로그래머스] 문자열 압축 - Python
2021. 12. 30. 17:56
Algorithm/프로그래머스
문제 https://programmers.co.kr/learn/courses/30/lessons/60057?language=python3 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 풀이 입력으로 주어지는 문자열 s의 길이가 1000이고 문제 상황에 맞게 모든 압축 단위로 압축을 해보아도 시간 상 무리가 없을 것 같아 완전 탐색을 시도해보았습니다. 문자열이 압축될 수 있는 모든 경우 즉, 압축 단위를 1 부터 (s의 길이 // 2) 까지 바꿔가며 전부 압축을 해보고 이전까지 구한 가장 짧은 압축 길..
[BOJ] 1655 가운데를 말해요 - Python
2021. 12. 5. 04:34
Algorithm/백준
문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 이 문제를 보고 가장 먼저 떠오른 방식은 입력을 받을 때마다 배열에 추가하고 배열을 정렬하여 가운데 값에 해당하는 인덱스를 출력으로 내보내는 것이었습니다. 하지만 문제에서 주어진 N의 최댓값과 시간 제한을 고려해보았을 때 위와 같은 방식은 시간초과가 날 것이 뻔하여 다른 풀이로 호다닥 전환했습니다. 문제에서 요구하는 가운데 숫자는 그 값을 기준으로 좌측과 우측 숫자의 개..
[BOJ] 2075 N번째 큰 수 - Python
2021. 12. 4. 15:52
Algorithm/백준
문제 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 해당 문제는 N의 최대 크기가 1500으로 시간 제한만 고려한다면 입력되는 숫자 모두를 받아서 정렬하는 방식을 사용해도 풀이가 가능합니다. 하지만 메모리 제한으로 인해 위와 같은 풀이를 제출 시 메모리 초과가 납니다. 따라서 N^2 개의 숫자 모두를 배열에 저장하고 그 후에 문제 조건에 따라 무언가를 처리하는 방식으로는 해당 문제를 풀기 어렵습니다. 이에 N^2의 숫자들을 모두 살펴보면서 로직..
[BOJ] 1927 최소힙, 11279 최대힙 - Python
2021. 12. 2. 03:12
Algorithm/백준
문제 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 풀이 위 두 문제는 python의 heapq 모듈을 사용하면 쉽게 풀 수 있는 문제입니다. 문제 제목에서도 풀이를 유추할 수 있었지만 입력으로 주어지는 최대 N이 100,000..
[Python] heapq 모듈
2021. 12. 2. 02:54
Python
Python heapq 모듈 사용법 heapq 모듈에 대한 내용에 들어가기 앞서.. heap에 대한 내용은 아래 블로그 포스팅을 참고하시면 이해하시는데 도움이 될 것 같습니다. [자료구조] 우선순위 큐와 heap 우선순위 큐와 Heap 우선순위 큐는 일반적인 큐와 다르게 우선순위가 높은 데이터가 먼저 나갈 수 있도록 만들어진 자료구조입니다. 그래서 어떻게 구현하는데? 우선순위 큐는 배열 또는 연결리 kjhoon0330.tistory.com 모듈 임포트 heapq 모듈은 python 내장 모듈이기 때문에 아래와 같이 간단히 불러올 수 있습니다. import heapq 최소 힙 생성 heapq 모듈은 파이썬의 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와줍니다. 따라서 heapq 모듈을 통해서 리스트에 원..
[자료구조] 우선순위 큐와 heap
2021. 12. 2. 02:02
CS/자료구조
우선순위 큐와 Heap 우선순위 큐는 일반적인 큐와 다르게 우선순위가 높은 데이터가 먼저 나갈 수 있도록 만들어진 자료구조입니다. 그래서 어떻게 구현하는데? 우선순위 큐는 배열 또는 연결리스트을 단순하게 사용하여도 구현이 가능합니다. 배열과 연결리스트의 맨 앞 원소부터 차례대로 우선순위가 높은 data를 넣는다면 어렵지않게 우선순위 큐를 구현할 수 있습니다. 이러한 방식으로 우선순위 큐를 구현하게 되면 우선순위에 맞춰 data를 알맞은 자리에 삽입해야 하기 때문에 이 과정이 O(n)의 시간복잡도가 소요됩니다. 하지만 heap 자료구조를 사용한다면 조금 더 효율적인 방식으로 우선순위 큐를 구현할 수 있습니다. heap을 사용한다면? 우선 heap이 무엇인지에 대해 알아보겠습니다. heap 이란? 힙(hea..
[BOJ] 22781 징검다리 건너기 - Python
2021. 11. 20. 01:03
Algorithm/백준
문제 https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 풀이 문제를 처음 보면서 첫 번째 돌에서 마지막 돌까지 가는 모든 케이스(조합)를 체크해보면 답을 구할 수 있겠다라는 생각은 쉽게 떠올릴 수 있었습니다. 하지만 이러한 방법은 N의 크기와 시간 제한때문에 불가능함을 알 수 있습니다. 경험상 문제가 특정 원소를 선택하거나 하지않거나(이 문제의 경우 발판으로 특정 돌을 선택 할지 말지)..
[BOJ] 백준 20444: 색종이와 가위 - Python
2021. 11. 19. 23:36
Algorithm/백준
문제 https://www.acmicpc.net/problem/20444 20444번: 색종이와 가위 첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1) www.acmicpc.net 풀이 가위질을 가로로 자른 횟수(rowCut)와 세로로 자른 횟수(colCut)로 나눠보면 (즉, n = rowCut + colCut) 조각의 개수는 (rowCut + 1) * (colCut + 1) 만큼 나옵니다. 따라서 rowCut이 정해지면 조각의 개수가 정해집니다. 또한,, 1. 조각의 개수는 rowCut 과 colCut 개수에 대해 대칭적?이기 때문에 rowCut을 0 ~ n 까지 확인할 필요 없이 0 ~ n // 2 까지만 확인하면 됩니다. 2. rowCut을 0 ~ n //..