기타/알고리즘
-
백준 파이썬 17952번 : 과제는 끝나지 않아! 풀이기타/알고리즘 2020. 12. 15. 23:35
https://www.acmicpc.net/problem/17952 17952번: 과제는 끝나지 않아! 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이 www.acmicpc.net 과제를 최근에 나온 순서대로 하고있다. 그러므로 스택을 이용한 문제임을 알 수 있다 스택을 이용하면 조건 1, 2, 3을 자동으로 만족하기 때문에 간단히 풀 수 있다 굳이 데크를 이용하지 않아도 풀 수 있다 1. 과제의 정보를 입력받고 과제의 점수와 시간을 따로따로 저장해준다 2. 시간이 지남에 따라 가장 마지막에 받은 과제의 시간을 -1해준다 3. 가장 마지막 과제의 시간이 0이 되면 시..
-
[파이썬] 리트코드 20. Valid Parentheses 풀이기타/알고리즘 2020. 12. 15. 22:52
https://leetcode.com/problems/valid-parentheses/ Valid Parentheses - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 스택을 이용하는 대표적인 문제다. 큐의 경우 데크를 이용하여 푸는 것이 속도 면에서 이득이지만, 스택은 리스트로도 충분히 구현할 수 있고, 시간에서 큰 차이가 발생하지 않는다. 실제로 이 문제를 리스트로 풀 때와 데크를 이용해서 풀 때 걸리는 시간은 차이가 없다. 1. 괄호 요소를 검사하기 위해..
-
[파이썬] 리트코드 15. 3Sum 풀이기타/알고리즘 2020. 12. 14. 22:45
https://leetcode.com/problems/3sum/ 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com n개의 숫자리스트가 주어졌을 때 세 수의 합이 0이 되는 세 수를 구해야 한다. 이 문제를 투 포인터를 이용하여 풀었다. 반복문의 인덱스를 i로 두었을 때, 나머지 두 수를 포인터로 두고 이동시켜주며 0이 되는 케이스를 탐색했다. 1. 정렬해준다. 세 수의 인덱스를 출력하는 문제가 아니라 정렬을 해두는 것이 편리하다. 그리고 중복된 숫자가 ..
-
[파이썬] 리트코드 121. Best Time to Buy and Sell stock 풀이기타/알고리즘 2020. 12. 14. 22:30
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ Best Time to Buy and Sell Stock - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 한 번의 거래의 최대 이익을 구하는 문제다. 따라서 가장 가격이 낮을 때 사서 가장 가격이 높을 때 팔면 된다. 이 역시 시간제한이 존재하기 때문에, 단순히 모든 경우의 수를 탐색하며 풀면 시간초과가 난다 그러므로 반복문을 한 문장으로 만들어줘야..
-
[파이썬] 리트코드 238. Product of Array Except Self 풀이기타/알고리즘 2020. 12. 14. 19:11
https://leetcode.com/problems/product-of-array-except-self/ Product of Array Except Self - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 자신을 제외한 모든 수의 곱을 구해야 하는 문제다. 모든 수를 곱한 뒤 자기자신을 나누면 되는 간단한 문제지만, '나누기를 사용해서는 안 된다'고 되어있다. 따라서 다른 방법을 이용해야 한다. 그리고 복잡도를 O(n)으로 제한하고 있기 때문에, 이중 반복문..
-
[백준 파이썬 1966번 : 프린터 큐] 큐를 이용한 풀이기타/알고리즘 2020. 12. 5. 19:11
https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음 www.acmicpc.net 일반적인 큐 문제에 중요도라는 개념을 더해서 조금 복잡해졌다. 특히 중요도가 중복될 수 있기 때문에 주의가 필요하다. 예시에서처럼 중요도로 1,1,9,1,1,1이 들어오면 '중요도가 1인 문서의 출력 순서'를 구하는 방법은 통하지 않기 때문이다 나는 입력받은 큐를 que, 인덱스를 원소로 넣은 idx_que를 이용하여 풀었다. que에 대한 푸시, 팝을 동일하게 i..
-
백준 파이썬 10828번 : 스택 시간초과 해결기타/알고리즘 2020. 12. 3. 22:35
10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 스택을 몰라도 충분히 풀 수 있다. solved.ac에서 실버4 판정을 받고 있는데, 절대 그럴만한 문제는 아니다. 다만 정답률이 상당히 낮은데, 시간이 빡빡해서 그렇다. 별다른 궁리가 필요하지는 않고, input대신에 값을 입력받는 데 더 빠른 readline을 쓰면 된다. 백준 문제에서 시간초과가 날 때는 대부분 readline을 쓰거나 PyPy로 제출하면 해결된다. 참고로 import sys input = sys.stdin.readline ..
-
백준 파이썬 2428번 : 표절 이진탐색 풀이기타/알고리즘 2020. 12. 3. 21:52
https://www.acmicpc.net/problem/2428 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net 솔루션 파일의 크기가 a,b,c...로 주어졌을 때 a=b*0.9를 만족하는 문자쌍의 개수를 구해야 하는 문제다 입력값이 정수라는 데 주의하자. 따라서 리스트를 받을 때 float로 받아줘야 한다 1. 리스트를 입력받아 오름차순으로 정렬해준다. 그러면 모든 요소에 대해 a=b*0.9를 만족하는 요소의 최대 인덱스를 나타내므로 조건..