유진's 공부로그

https://school.programmers.co.kr/tryouts/32181/challenges 문제의 핵심은 주어진 skill이 skill_trees 내 skill_tree에 올바른 순서로 들어가있는가이다. skill의 subsequence만 들어가도 무방하다. 문제에서 주어진 배열의 길이를 보았을 때 시간 복잡도를 고려할 만한 문제는 아님을 판단할 수 있어야 한다. 그리고 문제 요구 사항을 보고 어떤 자료구조를 사용할 것인지에 대한 감이 빨리 와야 할 것 같다. 나의 첫 풀이 def solution(skill, skill_trees): """ skill_trees 탐색하되...skill의 순서가 어떻게 되는지 체크 """ answer = 0 for sk in skill_trees: sk = "..

백준이 프로그래머스나 리트코드에 비해 짜증나는 부분은 인풋이 들어가는 형태도 고려해줘야 한다는 점이다. 오랜만에 백준으로 문제를 풀려니까 입력을 어떻게 할지부터가 난관이어서 입력 형식을 정리해보고자 한다. (언어는 파이썬) 백준 예제 입력은 위와 같이 들어올 때가 종종(아니 대부분) 있다. 그럼 \n으로 split을 하면 되지 않나? 하는데 왜인지 모르게 계속 오류가 났다. 공백 기준으로 해도 똑같은 에러가 계속 발생한다. (나 이전까지는 어떻게 해온 거지..머리에 든 게 없는 것을 겸허히 받아들이고 정리하기로 했다..) 위의 에러가 발생하는 이유는 애초에 input이라는 함수 자체가 \n이 들어오면 아예 입력을 마치는 것처럼 동작하기 때문이다. 따라서 여러 개의 입력값을 받기 위해서는 반복문을 활용해야..

https://leetcode.com/problems/daily-temperatures/ 문제 설명 매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨가 될 때까지 며칠을 더 기다려야 하는지 리스트로 리턴하라. 문제 접근 및 풀이 [1st Try] - 투 포인터 1) 현재를 가리키는 포인터를 left, 미래를 가리키는 포인터를 right으로 설정. 2) 미래의 기온이 현재의 기온보다 높지 않다면 right 포인터를 한 칸 옮긴다. 3) 미래의 온도가 현재의 온도보다 높다면 결과가 되는 리스트에 right과 left의 차이를 append하고, left 포인터를 한 칸 이동, right 포인터를 left의 바로 다음 칸으로 이동시킨다. 4) left가 마지막에서 두번째 원소를 가리킬 때까지 반복한다...

https://leetcode.com/problems/remove-duplicate-letters/ 문제 설명 주어진 문자열에서 중복된 문자를 제외한 후 사전식 순서가 가장 작은 문자열을 리턴하라. (즉, 원래 문자열에서의 문자 순서를 완벽히 무시할 수는 없다는 뜻. 중복조합처럼 자리를 정해주는 식으로 생각하면 좀 더 수월할 듯하다) 문제 접근 및 풀이 [1st try] 1) 중복을 제거한다는 것은, 각 글자가 있을 자리를 정해준다는 것 → 원래 있던 자리를 무시하는 게 아님 2) 사전식 순서로 가장 작은 것을 리턴해야하는 것 → 쉽게 생각하면 가장 작은 글자 앞으로, 가장 큰 글자 뒤로 → 그러나 문제가 되는 점은 원래 문자열에서의 각 글자의 자리는 보존되어야 한다는 점 → 뚜렷한 자료구조는 생각나지 ..

https://leetcode.com/problems/valid-parentheses 문제 설명 괄호로 된 입력값이 올바른지 판별 (기본기 점검으로 좋은 문제) 문제 풀이 접근 1) 각 여는 괄호는 짝이 맞는 닫는 괄호가 있다 2) 닫는 괄호의 순서는 여는 괄호의 순서와 반대로 이루어져야 한다. 가장 마지막에 오는 여는 괄호는 가장 처음에 오는 닫는 괄호와 만나게 되고, 이런 패턴이 계속 반복된다. → 스택으로 접근 (LIFO) → 여는 괄호는 스택에 넣고, 닫는 괄호를 만나면 pop해서 짝이 맞는지 대조하는 방식 → 짝이 맞는지 대조하는 데에 편리한 자료구조는 딕셔너리 문제 풀이 class Solution: def isValid(self, s: str) -> bool: parentheses = { "(..

이진 탐색 (Binary Search) 이진탐색은 배열의 중앙값(median)을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 대략 반으로 줄여가며 재귀적으로 진행하는 알고리즘이다(물론 반복으로도 구현 가능하다). 정렬된 배열에서의 탐색에 적합한 알고리즘이다(연결리스트에서는 부적합함. 가운데 지점을 빠르게 찾을 수 없기 때문이다). 시간복잡도는 $O(\log_2{n})$ 으로 빠른 수행시간을 보여준다. 이진 탐색 알고리즘 1) 재귀 구현 2) 반복 구현 투 포인터를 어떻게 활용하느냐의 차이로 투 포인터의 응용이라고 볼 수도 있을 듯하다. 이진 탐색 in Python bisect 모듈에 구현이 되어 있으며, bisect_left를 사용하면 된다. 원래는 정렬된 ..

런너(Runner) 기법 연결 리스트 순회 시 2개의 포인터를 동시에 사용하는 기법. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다. 연결리스트의 경우 중간 위치나 길이를 파악하는 데에 배열에 비해 상대적으로 복잡하다. (전체를 다 탐색해야 하므로 O(n)의 시간이 소요됨) 따라서 fast runner와 slow runner 간의 step을 2배 차이를 두는 식으로 (ex. fast, slow = 2,1) 지정한 후 fast runner가 리스트의 끝지점에 도착하면 slow는 정확히 리스트의 중간 지점에 도달하게 된다. 중간위치를 찾아냄으로써 값 비교 (palindrome linked list 문제), 뒤집기를 시도하는 등의 연결 리스트..

브루트 포스 (brute force) 가능한 모든 조합을 다 탐색 (답이 나올 때까지) 답을 무조건 찾을 수는 있으나, 답을 찾는 데에 비용이 너무 크다는 단점이 있음. (시간 복잡도가 크다. 탐색해야 할 것이 많다면 코테에서 타임아웃이 뜰 것) 대체적으로 완전 탐색의 시간 복잡도는 O(n!) or O(2^n) Ex) 리트코드 15번 3Sum 합이 0이 되는 3개의 수의 조합을 찾는다. 이때 brute force는 가장 간단한 방법. but, 3개이므로 배열에서 3번의 loop을 돌아야 하기 때문에 (double nested loop) 시간 복잡도가 O(n^3)임. 따라서 매우 비효율적인 방법이라고 할 수 있다. 또한 코드 가독성 또한 떨어짐. (아래 참고) for i in range(len(nums)-..