Coding Test

Dynamic Programming으로 문제 해결해보기

Dynamic Programming을 알 수 있는 간단한 문제

Linked List 앞에 Dummy 노드를 붙여서 if문을 줄이기

sorted 함수의 특성과 startswith()

list에 X를 추가해주면 그 list에서는 뽑지 않는 경우까지 고려할 수 있다.

nonlocal 변수 설정, DFS

프로그래머스 메뉴 리뉴얼. 2021 카카오 블라인드 테스트 문제

list 자료구조를 삼각형 모양으로 만들고 index를 바꿔가면서 숫자를 채워보기

re.findall, dict와 list에서의 in Function

간단한 DFS. 재귀함수 속에서도 변수가 영향을 주는 범위를 체크해볼 것

list나 str의 slicing 작업 대신 추가 메모리(자료구조)를 활용해서 속도를 빠르게 해보자

동일한 메모리상 개체를 가리키는 경우를 주의하자! DFS 응용문제

Multi Source BFS로 탐색 지점을 최소화해보자

두 개의 포인터로 문제를 해결하는 방식. 꼭 이동해야 하는 한칸씩 이동해가면서 문제를 해결하자.

Parentheses, DFS(재귀함수에 직접 값 입력하기)

Binary Search(이분탐색)로 target element의 첫번째, 마지막번째 index를 찾아보자

Dynamic Programing 기본 문제. 계단 오르기, 마지막 index에 도달하기

DFS 심화문제, 2021 카카오 채용연계형 인턴 코딩테스트 문제

2 dimensional DP와 combination 값 간의 관계를 활용해서 다리를 놓는 경우의 수를 구해보자

Gray code는 이진수로 나타냈을 때 한 글자씩 다른 수들의 나열이다. DP로 풀어가지만, 비트연산자를 활용할 때 좀 더 간단하게 해결 가능하다. 이진수 관련 문제에서 떠올려볼만한 메소드이다.

Time Complexity에 대한 설명, 괄호 문제를 풀 때 stack을 활용하게 되는데 답을 구하기 위해서는 이전에 열린 괄호들의 개수를 세어줘야 할 때가 있다.

DFS 시작점을 줄여줘서 전체 알고리즘의 시간 단축, list 대신 set을 활용하여 in function 시간 단축

이진법 표기 문제가 나왔을 때 기본이 되는 부분들을 다룬다. zip_longest에 대해서 소개한다.

Subarray 문제를 DP로 해결할 때 사용되는 Kadane's algorithm

그리디(greedy) 알고리즘, 중복되는 부분을 탐색하지 않도록 줄여보는 연습

백트래킹(back tracking)과 DFS에서 변수를 고정 시키기 위한 리스트 복사 [:]를 사용했다.

BFS로 최단 거리 구하기. (level 단위) DFS로 path 구하기 (재귀 호출 시 변수 고정)

n진법 수를 int type의 10진법 수로 변환하기. int()

Stack을 활용해서 사각형의 면적과 관련된 문제를 푼다. 코드로만 보면 이해가 힘들 것 같아서 그림으로 메모해둔다.

nonlocal 변수와 recursion을 사용해보기 (DFS 등을 풀 때 매우 유용)

백준 1148 단어 만들기 word1의 알파벳들로 word2를 만들 수 있을까? Counter를 만들어서 두 단어 비교해보기

DFS, DP, itertools를 모두 활용해 볼 수 있는 좋은 문제

DFS 문제이면서 cycle 개념과 수학적인 비용 계산이 포함된 좋은 문제