[백준] Sil2 | 이진탐색 | 2512 예산 Pythonhttps://www.acmicpc.net/problem/2512 구상총예산을 넘기지 않는 선에서 최대가 되는 그 시점! 을 찾아야 함 → 이진탐색내 구상대로 풀어봤는데 테케는 통과하나 채점 시 틀렸습니다가 뜬다질문 게시판의 반례들 찾아보기반례로 고쳐봐도 코드가 다른 분들 코드보다 너무 복잡한게 뭔가 내 논리 자체에 근본적인 문제가 있는 것 같아서 솔루션을 보기로,,결론적으로는 이진탐색을 잘못 활용하고 있었고, 다시 제대로 써서 풀었다. 트러블 슈팅이분탐색 시 left, right 가 꼭 인덱스일 필요는 없다. 찾으려는 값으로 해도 됨.. 그냥 이분탐색 원리 그대로 중간값으로 잡아서 계산해나가면 이분탐색 종료 후 최적의 상한액이 남게 됨ㅎㅎ....
DSA/Algorithm
[백준] Sil4 | 이진탐색 | 1789 수들의 합 Pythonhttps://www.acmicpc.net/problem/1789 구상두가지 방법으로 풀이했다.손구상 풀이 (greedy)내가 손구상한 풀이로도 가능했음. 답까지 모든 경우에 조건을 확인해야해서 더 오래걸리지만..이진탐색문제라고 해서 이진탐색으로도 풀었다이진탐색으로 한번 더 풀어보자 트러블 슈팅이분탐색 시 다음 범위는 현재 중간값을 포함하지 않는 범위로 설정해줄 것!숫자 합 계산에 sum(range()) 를 썼더니 시간초과 발생. 1~n까지의 합 = n(n+1)/2 임을 활용하자! 코드 - greedy# v1 : greedy (60ms)# 그리디 / 이진탐색 둘 다로 풀리는 문제# TS : range 범위 경계값에 걸리는 경우 ..
[프로그래머스] LV3 | DP | 코딩 테스트 공부 Pythonhttps://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 구상모르겠어서 솔루션 함 읽고 해봄..dp면 점화식이 있겠지. 뒷쪽에 계산해둔 결과를 재사용할거고.점화식 : dp[alp][cop] = min(dp[alp-1][cop]+1, dp[alp][cop-1]+1, 문제를 풀어서 도달시켜둔 값)dp는 과거 계산결과를 사용한다 = 앞에걸 먼저 업데이트해둬도 됨..!!!...!!TS 1 : 인덱싱..
[프로그래머스] LV2 | DP? | 가장 큰 정사각형 Pythonhttps://school.programmers.co.kr/learn/courses/30/lessons/12905 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 구상DP로 어떻게 푼다는 건지 모르겠어서 솔루션 봄인덱스를 처음부터 돌고싶어서 그 방향으로 풀어보려고 고집했는데 인덱스 위치는 내 생각보다 중요함.. DP가 이전의 계산값을 활용하는 개념이니 뒤쪽 값을 사용하는 방향으로 설정하는 게 당연했을지도.. 이것저것 해보기점화식dp테이블에 저장할 값은 정사각형 한 변의 최대 길이이다. (답은 ..
[프로그래머스] LV3 | 구현 | 광고삽입 Pythonhttps://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr Think누적합 이라는 개념을 사용하는 문제라고 한다.말그대로 누적한 합인데, 이 개념을 사용하면 쉽게 원하는 구간의 구간합을 구할 수 있다.누적합 계산법 1. 주어진 데이터에서 숫자 변동이 생기는 부분만 +, -로 표시한 배열 만듦 2. +, - 되는 만큼 해당 부분의 현재 값 담은 배열 만듦 3. 현재값 배열로 누적값 ..
https://leetcode.com/problems/search-a-2d-matrix-ii/ Search a 2D Matrix II - 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 Think 정렬된 mXn행렬과 target값이 주어지고, 행렬에서 target값이 존재하는지 T/F를 구하는 문제 행렬은 왼->오, 위->아래 방향으로 오름차순 정렬되어있음 존재하면 true 리턴 이진 검색 문제처럼 보이지만 이진 검색 보다는 다른 탐색을 사용하여 풀이해야 함 1...
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ Two Sum II - Input Array Is Sorted - 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 Think 정렬된 배열과 타겟 수가 주어지고, 배열에서 어떤 두 수를 더해야 타겟 수를 만들 수 있는지 두 수의 인덱스를 구하는 문제 주의할 점은 인덱스를 1부터 시작하는 것으로 셀 것. 주어지는 배열이 정렬되어 있으므로 투 포인터 기법으..
https://leetcode.com/problems/sort-list/ Sort List - 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 Think 주어진 연결리스트를 정렬하는 문제 파이썬 내장함수를 사용해 풀이 연결리스트 -> 리스트로 만들어서 sort -> 연결리스트 (이외에 병합정렬로 풀이할 수도 있다. 코테 면접 등 설명이 필요할 때에는 내장함수를 사용하지 않는 방법을 써야 함) Solution # Definition for singly-linked ..
이진 탐색 트리(BST) 노드 간 최소 거리 https://leetcode.com/problems/minimum-distance-between-bst-nodes/ Minimum Distance Between BST Nodes - 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 Think 값들이 BST형태로 주어지고, 노드들 중 가장 작은 값 차이를 출력하는 문제 트리에서 현재 노드와 값 차이가 가장 적은 노드는 딱 두 개 중 하나이다. 두 개가 어느것인지는 그림으..
정렬된 배열의 이진 탐색 트리 변환 https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/ Convert Sorted Array to Binary Search Tree - 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 Think BST의 원리를 이해한다면 쉽게 풀 수 있는 문제였다! (기억이 잘 안나서 BST 개념이랑 특징 따로 읽어봤음) 주어지는 배열도 정렬된 배열이라 간단했다~ So..
Think https://www.youtube.com/watch?v=XEmy13g1Qxc k번째 큰 수를 찾는 문제. 자연스럽게 정렬을 생각하게 되는데, 위 영상에서 그냥 정렬을 하면 O(nlogn)의 시간이 들지만 힙으로 만들면 정렬 시간을 O(n) 으로 줄일 수 있다고 한다. 대신 힙으로 만들어서 제일 큰 수부터 하나씩 꺼낼 경우, 꺼낼 때마다 logn 의 시간이 든다. 따라서 k번째 큰 수를 찾으려면 n+klogn 의 시간이 들게 된다. 이는 대체적으로 nlogn보다 좋은 값이지만, k값에 따라서 더 오래 걸리는 경우도 있다. 평균적으로 보았을 때에는 더 좋은 값이라고 할 수 있다. 파이썬의 heapq모듈을 활용한다. heapq모듈은 최소힙이므로, 음수로 바꾸어서 힙에 저장한 다음 가장 작은 수부터..
https://leetcode.com/problems/balanced-binary-tree/ Balanced Binary Tree - 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 Think 재귀로 풀 수 있는 문제 이진트리의 균형은 효율면에서 중요한 부분이라고 한다. Solution # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None..
https://leetcode.com/problems/maximum-depth-of-binary-tree/ Maximum Depth of Binary Tree - 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 Think 책대로 스택을 사용하는 BFS 반복구조로 풀이해보자! 파이썬의 큐 자료형보다는 데크를 쓰는 게 성능이 좋다. Solution # Definition for a binary tree node. # class TreeNode(object): # de..
https://leetcode.com/problems/subsets/ Subsets - 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 Think dfs 탐색 과정의 모든 걸 저장하면 됨 Solution class Solution(object): def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ def dfs(index, path) : # 매번 결과에 추가함. 그래프 끝까지..
https://leetcode.com/problems/combinations/ Combinations - 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 Think 이번에도 영상을 보자..~ https://www.youtube.com/watch?v=q0s6m7AiM7o Solution 1. 파이썬 답게,, 라이브러리를 사용하는 풀이 class Solution(object): def combine(self, n, k): """ :type n: int :type k:..
