분류 전체보기
-
[파이썬] 리트코드 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를 만족하는 요소의 최대 인덱스를 나타내므로 조건..
-
백준 파이썬 11947번 : 이런 반전이 풀이기타/알고리즘 2020. 12. 2. 22:53
11947번: 이런 반전이 첫째 줄에는 테스트 케이스의 개수를 나타내는 하나의 자연수 T가 주어집니다. 다음 T개의 각 줄에는 하나의 양의 정수 N이 주어집니다. (1 ≤ N ≤ 1,000,000,000) www.acmicpc.net 숫자 n이 주어질 때 '반전'은 각 자리 숫자 a에 대해 9-a를 한 것이다 '사랑스러움'은 숫자 n과 '반전'의 곱이다 이때 단순히 숫자 n의 '사랑스러움'을 구하는 것이 아님에 주의해야 한다. 한 숫자에 대해서만 계산한다면 간단한 문제지만, range(1,n+1) 범위에서 '사랑스러움'의 최댓값을 구해야하기 때문에 복잡해 보인다. 그러나 쉽게 유추할 수 있는 규칙성이 있어서 의외로 간단하다. 한 자리 숫자가 주어진다면 이들 수의 '사랑스러움'의 최대값은 4*5다. n 1..