우디의 성장일기

처음에는 recursion을 이용하려 했지만 시간 초과가 날 것 같아서 다른 방식을 찾아봐야했다. 결국 스터디에서 친구의 코드를 참고해서 문제를 풀게 되었다. DP 문제는 보통 dp[n] = dp[n -1] + dp[n - 2] dp[n] = max(dp[n - 1], dp[n - 2]) ... 이런 느낌의 점화식으로 풀 수 있는 문제인데 이번 문제도 그랬다. 로직 [10, 20, 30, 40, 50, 60] 이 있으면 인덱스가 2인 위치에서 최대가 될 수 있는 경우는 max(30 + 10, 20) -> max 값을 3의 위치에 업데이트 [10, 20, 40, 40, 50, 60] 인덱스가 3인 위치에서 최대가 될 수 있는 경우는 max(40 + 20, 40) -> max 값을 4의 위치에 업데이트 [1..

로직 문제를 해결하기 위해서는 크게 두 가지를 구해야 한다. 기본 설정이 모두 A라고 했을 때 조이스틱을 1. 아래 혹은 위로 최소 몇 번을 움직여야 하는지 2. 옆으로 최소 몇 번을 움직여야 하는지 아래 혹은 위로 해당 문자의 아스키 값을 이용해서 구했다. 옆으로 옆으로 가는 경우는 세분화 해보면 아래와 같다. 1. 한 쪽으로만 가는 경우 (1) 왼쪽으로만 (2) 오른쪽으로만 가장 왼쪽 혹은 가장 오른쪽에 연속된 A가 몇 개인지 확인한 다음 방향을 결정한다. (연속된 A의 길이를 확인하는 이유는 A가 있는 구간은 굳이 조이스틱이 거쳐가도 되지 않기 때문에 최대한 A의 길이가 긴 곳의 반대방향을 선택한다.) right_most_A = count_continuousA(reversed(name)) left_..

로직 불량 사용자 후보군 추출 먼저 불량 사용자 리스트를 통해서 제재 대상이 될 후보군들을 추출한다( 추출 시에 정규 표현식을 사용했다) 만약에 아래와 같은 예시가 있다면 user_id = ["frodo", "fradi", "crodo", "abc123", "frodoc"] banned_id = ["*rodo", "*rodo", "******"] 각 불량 사용자에 대한 후보군들은 아래와 같다. *rodo ['frodo', 'crodo'] *rodo ['frodo', 'crodo'] ****** ['abc123', 'frodoc'] DFS 탐색 이후 dfs로 제재 아이디 목록을 찾아낸다. 만약 leaf까지 탐색했다면 완성된 제재 리스트가 현재 이미 만들어진 제재 리스트에 없다면( stack not in c..

첫 번째 코드 - 실패 처음 코드의 로직은 len(numbers) - k 번 만큼 (즉, 최종적으로 나오게되는 숫자의 길이만큼) 최댓값 찾는 탐색을 수행한다. 최댓값 탐색의 범위는 이전 최댓값이 나왔던 index + 1부터 현재 탐색할 수 있는 최대 영역까지이다. 예를 들어 만들어야 하는 숫자의 총 길이가 3이고 현재 "1234"라는 숫자 안에서 첫 번째 숫자를 선택 해야할 때, 첫 번째 숫자를 위해 탐색해야하는 영역은 "12"이다. 만들어야하는 숫자의 총 길이가 3이기 때문에 첫 번째 숫자가 선택된 이후 두 번째, 세 번째 숫자를 선택해야하는 상황까지 고려해야하기 때문이다. def solution(number, k): answer = [] start, end = 0, k + 1 while end num..

Two Sum 문제 링크 문제는 쉬웠지만 여러가지 방식으로 접근할 수 있어서 흥미로운 문제였다. 내가 접근한 방법은 Brute-force였다. 간단하게 그냥 모든 경우의 수를 다 따져보는 방식이었다. # Python class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: indice = [i for i in range(len(nums))] for pair in combinations(indice, 2): if nums[pair[0]] + nums[pair[1]] == target: return pair return [0, 0] 그런데 Solution을 보니 a + b = target -> a = target - b라는 점을..

로직 로그들을 endtime이 큰 순서대로 탐색하면서 현재 탐색하고 있는 로그보다 endtime이 큰 로그들을 가지고 [현재 로그의 endtime] ~ [현재 로그보다 endtime이 큰 로그의 starttime] 사이의 거리를 체크해서 1초 구간 안에 있는지 확인해준다. 현재 로그보다 endtime이 큰 로그들을 모두 체크해주어도 좋지만, 그리고 1초 구간 안에 있는지 확인해주는 작업을 보다 효율적으로 처리하기 위해서 최대힙을 사용하였다. 현재 탐색하고 있는 로그보다 endtime이 큰 로그들의 starttime을 최대힙에 넣어 가장 starttime을 가진 로그부터 확인해준다. 글로 설명하는건 항상 어렵다😂 예를 들어 아래와 같은 상황이 있다고 가정해보자 이렇게 되면 최대 힙에서는 start_time..

뭔가 정직하지 못한 방법을 사용 한 것 같은 죄책감... 이 살짝 들었지만 일단 성공적..ㅎ 로직 비교연산자를 다시 정렬해주고 소팅해서 해결했다. 비교연산자를 재정의 해줄 때, 두 인자를 두 가지 방식으로 (A + B 혹은 B + A) 합쳤을 때 더 큰 수가 되는 경우를 기준으로 했다. 코드 from functools import cmp_to_key def solution(numbers): answer = '' numbers = [str(num) for num in numbers] numbers.sort(key = cmp_to_key(compare)) for num in numbers: answer += num return str(int(answer)) def compare(item1, item2): n..

로직 완전탐색으로 열쇠와 자물쇠가 한 칸이라도 겹치는 경우의 수가 있다면 모두 체크해주는 것이다. 예를 들어 lock과 key 모두 3 X 3인경우, key가 lock 주위 혹은 위를 모두 탐색하면서 키와 겹치는 부분들을 체크한다. 이때 고려해주어야할 파트는 크게 두 가지가 있다. lock - key (key와 겹치지 않는 lock 영역) 현재 key와 겹치지 않는 lock의 영역 중 하나라도 0이 있다면 자물쇠는 열릴 수 없으므로 False 이다. 그렇기 때문에 zero_count라는 변수를 두어 lock에 남아있는 0들을 세어준다. 👉 골드가 말해주지 못했다면 한참 고민했을거다. 문제를 잘 읽자 제발!! key ⋂ lock (key와 lock이 겹치는 영역) 만약 key와 lock이 겹치는 부분 값의..

programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 해시... 문제였지만 해시로 풀진 않았다. 로직 1. phone_book을 소팅해준다. 2. length == 1일 경우는 명백히 True 케이스이므로 바로 리턴해준다. (⁕ 매우 쵸큼이지만 효율성을 높여줘서 그냥 넣었다.) 3. prefix를 하나 설정하고, prefix 이후 ~ prefix와 맨 앞자리가 달라지기 전까지를 target으로 삼고 find()로 prefix..

2887번: 행성 터널 멋모르고 도전했던 행성 터널문제.. 테스트 케이스는 통과가 되는데, 제출 결과는 '틀렸습니다'..😂 백준 문제를 오랜만에 풀어봤는데.. 개인적으로는 프로그래머스가 해당 문제에 대해 서로 공유할 수 있는 커뮤니티 형성이 더 잘 되어 있어서 문제가 막힐 때 힌트를 얻어가기 더 쉬워서 좋다. 물론 물어볼 곳이 따로 있다면 상관없지만, 혼자 공부하는 사람들에게는 가끔 벅차😅ㅠㅠ 로직 0. 문제에서 주어진 input으로 예시를 들어보겠다 5 11 -15 -15 14 -5 -15 -1 -1 -5 10 -4 -1 19 -4 19 1. 먼저 x, y, z에 대해서 각각 (value, index)를 원소로 한 minHeap을 만든다. 예를 들면 minheap에는 아래와 같은 순서로 정보가 저장되어..