결국 빛나리라

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 다이나믹 프로그래밍이란? 메모리를 적절히 사용하여 수행시간의 효율성을 향상시키는 방법이다. 즉 한번 계산된 결과는 별도 메모리 영역에 저장해 다시 계산하지 않도록한다. 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용한다. 1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있어 작은 문제를 모아 큰 문제를 해결할 수 있을 때 2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결할 때 현재 주어진 문제가 다이나믹 프로그래밍 유형인지 아닌지 고민하여 파악한느 것이 중요하다. 문제를 보고 위의 조건들..

▶ 입국심사 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr > 이진탐색 활용 나와있는 문제보다 더 쉬운 예제를 들어보자. time= [2,3] n= 3이라고 해보자 이때 탐색가능한 범위로는 3분에 3을 곱한 9분이 된다. [1,2,3,4,5,6,7,8,9] - left=1, right= 9, mid= 5이다. 5이하의 수 중 2와 3의 배수로는 3개가 있다. 즉 5분이면 3명의 입국심사를 마칠 수 있다. 그러..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 이진탐색이란? 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 시작점, 끝점, 중간점을 이용해 탐색 범위를 설정한다. 찾고자 하는 값보다 중간값이 크면 오른쪽에 위치한 데이터는 중간값보다 큰값들이므로 모두 무시하고 왼쪽에 위치한 데이터들을 범위로 잡고 시작값, 중간값, 끝값을 다시 설정한다. 이를 반복하다 중간값이 찾고자하는 값과 같으면 실행이 종료된다. - 시간복잡도: 데이터를 탐색할 때마다 탐색범위가 반씩 좁혀지기 때문에 O(logN)이다. 데이터를 처음부터 탐색해야하는 순차탐색이..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 정렬이란? 데이터를 특정 기준으로 나열하는 것을 말한다. 문제에 따라 정렬 알고리즘이 달라지는데 그 알고리즘들 중 선택정렬, 삽입정렬, 퀵 정렬, 계수정렬에 대해 정리해보고자 한다. ▶ 선택정렬이란? 현재 탐색범위인 데이터에서 가장 작은 데이터를 선택해 맨 앞으로 보내고 맨 앞에 있던 데이터를 가장 작은 데이터가 있던 자리로 바꿈으로써 오름차순으로 정렬한다. 다른 정렬들에 비해선 시간 비효율적인 알고리즘이지만 코딩테스트에서 가장 작은 데이터를 찾는 문제가 자주 출제되기 때문에 숙지하고 있어야한다. 시간복잡도-..

▶ 기능개발 https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr > 큐 사용 먼저 들어온 원소가 먼저 나가는 구조이기 때문에 queue를 사용하였다. 먼저 val에 소요일수를 넣은 후 queue에 삽입한다. 다음 소요일수를 val에 넣은 후 queue의 가장 첫번째 요소와 val을 비교했을 때 val이 작거나 같으면 result에 1을 더해주고 더 크면 result를 answer리스트에 넣은 후 resul..

▶ 타겟 넘버 https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr >dfs 풀이 숫자의 추가가 numbers리스트 길이까지 이뤄지면 재귀함수 호출을 종료한다. 만약 numbers 리스트 길이까지 숫자가 추가되고 이들을 모두 더한 값인 value가 target 수와 같아지면 answer에 1씩 더해준다. def dfs(numbers, target, idx, va..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ DFS (Depth-First Search) 란? 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 시작노드에서 시작하여 인접한 노드들을 방문하며 가장 깊숙이 위치하는 노드에 닿을 때까지 탐색한다. 인접한 리스트가 여러개일 경우 노드의 숫자가 가장 낮은 방향으로 탐색한다. > 다음 그래프가 있을 때 DFS는 어떤식으로 탐색할까? (설명 뒤의 []는 쌓이는 스택을 표현한 것이다) - 1에서 탐색을 시작한다. [1] - 연결된 노드 2,8,6중 가장 낮은 수인 2로 탐색한다. [1,2] - 2에서 3으로 방문한다. [1..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. ▶ 재귀함수(Recursive Function)란? 자기 자신을 다시 호출하는 함수로 DFS와 BFS에 자주 활용되는 형식이다. 파이썬에서 재귀함수는 무한히 함수를 호출하다가 최대 재귀 깊이를 초과하게 되면 최대 재귀 깊이 초과메시지가 출력되며 함수실행이 종료된다. 따라서 반복문 대신 재귀함수를 사용하여 반복문을 사용하지 않고 코드를 반복할 수 있다 ▶ 재귀함수의 종료조건 재귀함수 실행을 종료시키는 조건을 명시함으로써 특정 조건을 만족하면 함수가 종료되도록 설정해야한다. 그렇지 않으면 함수가 최대 재귀깊이까지 반복될 것이다. i가 10이 되었을 때 재귀함수 호출을 중단하도록 조건을 명시하였다. 재귀함수는 호출 될 때 메모리 ..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. ▶ 탐색이란? 탐색이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정으로 DFS와 BFS가 있다. 이 유형은 코딩테스트에서 매우 자주 출되는 유형이라고 한다. DFS와 BFS에 대해 설명하기 전 먼저 알아야할 개념인 스택과 큐 자료구조에 대해 알아보고 가자. ▶ 스택 자료구조란? 먼저 들어온 데이터가 나중에 나가고 나중에 들어온 데이터가 먼저 나가는 형식으로 선입후출의 자료구조이다. 파이썬에서 스택은 append를 사용하여 원소를 추가하고 pop을 사용하여 나중에 들어온 데이터를 빼서 활용할 수 있다. 최상단 원소(나중에 들어온 원소)부터 출력하기 위해선 print(lst[::-1])로, 최하단 원소부터 출력하기 위해선 p..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. 본 포스팅에서 작성한 코드문제는 해당 저서에 나와있는 문제 일부입니다. 예시답안코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 구현이란? 내가 생각한 아이디어를 소스코드로 바꾸는 과정을 말한다. 주로 알고리즘 문제에서 구현유형이란 아이디어를 떠올리는 건 쉽지만 코드로 구현하기 어렵거나 복잡한 문제를 말한다. 해당 유형의 문제를 풀기위해 다양한 라이브러리와 사용법을 알고 많은 문제를 풀어볼수록 더 유리할 수 있다. ▶ 구현 유형 대표적으로 시뮬레이션 및 완전 탐색 문제가 자주 출제된다. 해당 유형의 문제에서 2차원 공간은 행렬을 의미한다. 특히 행렬에서 방향벡터가 자주 활..