기타
-
백준 파이썬 11501 : 주식 풀이 (시간초과 해결)기타/알고리즘 2020. 12. 16. 23:08
https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 미래의 가격을 알고 있고, 매일 한 주를 사거나 팔 수 있고, 아무것도 하지 않을 수 있다. 이때의 최대 이익을 구해야 한다. 주식은 싸게 사서 그보다 비싸게 팔면 되는 '매우 간단한' 게임이므로 1. 현재 가격이 미래 가격보다 싸면 사고 2. 미래 가격보다 비싸면 아무것도 하지 않고 3. 지금 가격이 최대 가격이면 팔면 된다 따라서 1. 현재 이후의 가격의 최대값을 구하고 2. 현재..
-
[파이썬] 리트코드 739. Daily Temperatures 풀이기타/알고리즘 2020. 12. 16. 19:09
https://leetcode.com/problems/daily-temperatures/ Daily Temperatures - 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 매일의 온도를 리스트 T로 입력받은 뒤 현재보다 더 따뜻한 날이 올 때까지 며칠이 걸리는지를 구하는 문제다 1. enumerate를 이용해서 특정 날짜의 인덱스와 온도값을 기억한다 2. T의 인덱스를 계속해서 스택에 쌓아두면서 1. 현재 온도가 스택에 쌓아둔 마지막 날의 온도보다 높다면 2...
-
백준 파이썬 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..