본문 바로가기
728x90

Coding Test26

Leetcode 135 - Candy (Javascript) 1-pass 방식으로 풀기 https://leetcode.com/problems/candy/description/ 문제 난이도는 hard지만 기본 풀이법은 그다지 어렵지 않은 문제라고 생각햇다... 초기 풀이법(2-pass)1. 캔디 배열 1로 초기화 -> 무조건 1개는 받아야함2. 오른쪽으로 이동하면서 1차순회3. 다시 왼쪽으로 이동하면서 캔디 개수를 업데이트/** * @param {number[]} ratings * @return {number} */var candy = function(ratings) { let candies = Array(ratings.length).fill(1) for(let i = 0; i 0; i--) { if(ratings[i] a+b, 0)}; 근데 loop를 2번을 한다는.. 2025. 4. 22.
백준 12015 - 가장 긴 증가하는 부분 수열 2( Node.js ) 백준12015 가장 긴 증가하는 부분 수열 2이진 탐색(Binary Search)를 사용한 LIS( Longest Increasing Subsequence) 풀이 입력값이 1,000,000이 최대이므로 N^2으로는 풀 수 없음 최대 NlogN이진탐색을 써야하는 문제인 건 알고 있는데 도대체 어디에;; LIS 풀이법을 결국 떠올리지 못하고 해답을 찾아보았다.새로운 배열을 만들어서 원본 배열 원소와 비교하며 새로운 배열에 차례대로 넣으면 되는 아주 간단한 풀이 방식이였다.LIS를 저장할 배열(lisArr)을 유지하면서 이진 탐색현재 값이 lisArr의 마지막 값보다 크면 추가그렇지 않다면, lisArr에서 현재 값이 들어갈 위치를 이진 탐색(lower_bound)을 사용해 찾고 교체최종적으로 lisArr 배.. 2025. 2. 27.
백준 11561 - 징검다리( Python ) https://www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net 이진탐색 실버 3 레벨의 문제 등차수열로 풀어야한다는 것을 생각하지 못해서 다른 분의 풀이를 참고하여 풀게되었다. - 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야한다 -> 3, 4, 5, 6 과 같은 규칙이 있을 것으로 생각해야됨 3, 5, 9, 15 와 같은 불규칙적인 점프는 도출해낼 수 없음 - 최대의 징검다리 수 -> 점프마다 최소 거리를 뛰어야하므로 1이라 가정하고 규칙을 구할 수 있음 => 즉, 최소 거리를 뛰는 규칙을 찾아야하기 때문에 등차수열을 생각 할 수 있다. 공차를 구하는 것이.. 2023. 3. 14.
백준 9012 - 괄호( Python ) https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 아마 스택 기본 문제이지 않을까 싶다. 예제로도 많이 등장하는 괄호 문제 1차 답안 n = int(input()) for i in range(n): data = input() stack = [] result = 'YES' for i in data: if i == '(': stack.append(i) else: if i == ')' and len(stack) == 0:.. 2023. 3. 6.
백준 1049 - 기타줄( Python ) 1049번: 기타줄 (acmicpc.net) 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 백준 그리디 4실버 문제인데 반례를 생각하지 못해서 결국 도움을 받은 문제.. 아직 반례를 생각하는게 쉽지않다 조금 더 분기를 차근차근 나누는 연습이 필요할 듯 싶다. 처음에는 단순히 튜플로 패키지, 단품 가격 비교만 했는데 조금 더 자세한 비교가 필요했다. 총 4개의 케이스가 있으며 튜플로 비교하는 것보다 패키지 묶음, 단품 묶음으로 비교하는 것이 생각하는 것이 편하다 1. 6개 이하인 경우 낱개 가격만 비교 2.. 2023. 2. 22.
백준 16401 - 과자 나눠주기( Python ) https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 이진탐색으로 풀이가 가능한 파라메트릭 서치형식의 문제이다. 이진탐색으로 풀이를 생각하는 것은 어렵지 않았던 반면 과자하나를 어떻게 여러번 잘라야하나라는 생각이 쉽게 들지 않앗다. 나누기를 이용하면 되는 간단한 수준이였음에도 불구하고 아직 풀이 방향성을 잡는데 시간이 오래 걸린다. 풀이는 매우 간단하다 m,n = .. 2023. 2. 16.
728x90
반응형

티스토리툴바