코딩테스트

그래프 탐색 : 어떤것들이 연속해서 이어질때, 모두 확인하는 방법Graph : Vertex(어떤것) + Edge(이어지는것)아이디어시작점에 연결된 Vertex찾기찾은 Vertex를 Queue에 저장Queue의 가장 먼저 것 뽑아서 반복시간복잡도O(V+E)자료구조검색할

깊이우선탐색은 재귀함수롤 많이 차용한다.자기 자신을 다시 호출하는 함수주의할점재귀 함수가 종료되는 시점 반드시 명시재귀함수의 깊이가 너무 깊어지면 Stack OverflowDFS, 백트래킹에서 주로 사용아이디어2중 for => 값 1 && 방문X => DFSDFS를 통

때로는 당장 눈앞의 최선이, 최고의 결과를 가져온다현재 차례의 최고의 답을 찾는 문제어려운 이유 : 왜 그런지 증명하기가 어려움예시 : 다른 금액의 동전이 여러개 주어졌을때 M원을 만드는 최소의 개수아이디어큰 금액의 동전부터 차감반례? : 동전의 개수가 무한대라서 없는

모든 경우의 수를 확인해야할 때for로는 확인 불가한 경우 ( 깊이가 달라질 때)

어떤 값을 찾을 때 정렬의 특징을 이용해 빨리 찾음정렬되어있을 경우, 어떤 값 찾을때: O(N) => O(logN)처음부터 생각하기 어려움, 쉬운방법부터 생각조건 : N(1 ≤ N ≤ 100,000) = 1e5, M(1 ≤ M ≤ 100,000) = 1e5처음 아이디

이전의 값을 재활용 하는 알고리즘예시 : 1~10 숫자 중, 각각 이전값들을 합한 값 구하기이전의 값을 활용해서 시간복잡도를 줄일 수 있음점화식을 세워야하는게 키포인트처음부터 대입해보면서 점화식을 찾아라아이디어A1:1, A2: 2, A3: 1+2An = A(n-1)+A

가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다

오늘의 문제는 임의의 배열 3개를 주고, answers 배열과 비교하여 가장 많이 일치하는 순서대로 answer를 반환하는 것이다.제한 조건시험은 최대 10,000 문제로 구성되어있습니다.문제의 정답은 1, 2, 3, 4, 5중 하나입니다.가장 높은 점수를 받은 사람이

10 5 15 3 7 null 17 low high 변수

이진트리를 주고 가장 깊은 노드의 level을 구하는 문제이다.주어진 문제의 노드는 다음과 같다.root = 3,9,20,null,null,15,7먼저 while문을 사용해서 깊이를 구하는 코드를 구현해 보았다이와 같은 코드로 오른쪽 노드에 해당하는 깊이도 계산한다음

Arr, BinarySearch 요약 : 오름차순으로 정렬된 배열과 정수를 주고, 목표값과 같거나 목표값이 삽입될 수 있는 최소한의 위치값을 구하는 문제주어진 배열이 오름차순으로 주어져 있었기에 목표값까지 순회하거나 커지는 수를 만날 경우 순서를 return 하는 방식

gird 형태로 n x m 으로 주어진 배열에서 음수인 값을 찾는 문제이다.단순 for loop를 활용해서 구할수 있으나, 문제의 의도는 이진탐색을 사용하여 O(n + m)의 코드를 구현해 내는 것이다. 이진탐색의 기본 풀이법인 다음과 같은 공식을 활용하였다.pivot

배열을 주어주고 Graph와 같은 형태로 만들어지는 상황에서 중앙 노드에 해당하는 값을 찾는 문제이다. 조건중에 모든 노드는 중앙 노드와 연결된다고 되어있다.처음에는 해당 문제를 일일히 탐색해야하는건가 싶었다. 근데 곰곰이 생각해 보아도 전체를 순회하는건 원하는 접근

무작위 값으로 만들어진 두 배열을 주고, 가장 근사치에 해당하는 값들의 합을 구하는 문제이다.즉, seats = 3,1,5 와 stduents = 2,7,4 에서 근사치들에 해당하는 값을 구하는 것인데해당 예시에 따른 예를 들어보자면,처음 학생의 위치는 2이므로 가장

해당 문제는 배열을 주어주고 절반씩 섞은 배열을 return 하는 문제이다.ex) x1,x2,...,xn,y1,y2,...,yn => x1,y1,x2,y2,...,xn,yn이번 문제는 금방 풀렸으므로, 다른 문제를 하나 더 풀어본다1부터 100까지의 정수 배열을 주고,

문자열 배열 n개와 단일 문자를 주고 배열의 문자열에서 단일 문자의 값을 포함하는 index들을 return하는 문제이다.Type,Color,Name으로 이루어진 n개의 배열과, 어느 키를 기준으로할지에 해당하는 ruleKey, 만족하는 값은 어떤것인지에 해당하는 ru

두 배열을 주고 각 첫번째 배열의 값을 비교하여 다를 경우 처음 배열을 꺼내서 맨 뒤로 넣고 같을 경우 각각의 배열 첫번째 값을 dequeue하여 남는 배열의 수를 return 하는 문제이다.

주어진 배열을 주고 이전 까지 있었던 값들 까지 계산해서, 3초 이내에 해당하는 값들을 count하는 문제이다.ex) input: \[\[], 1, 100, 3001, 3002] , output: null, 1, 2, 3, 3이번 문제는 좀 특이하게 생성자를 만드는 것

랜덤한 정수로 이루어진 배열을 주고 i 번째의 인덱스의 값이 i 이후의 인덱스의 값보다 클 경우 그 차이를 배열로 저장하여 return 하는 문제이다.ex)Input: prices = 8,4,6,2,3Output: 4,2,4,2,3값이 문자로 이루어진 배열을 주고 문자

정수값으로 이루어진 이중배열을 주고, 각 배열들에서 가장 큰 수대로 숫자 하나씩을 뽑은 뒤 비교하여 가장 큰 수들의 합을 return 하는 문제이다.ex)Input : \[1,2,4,3,3,1]output : 4 + 3 + 1 = 8최대 값을 찾고 Math.max(..

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에

파이썬은 코테의 적폐언어 중 하나이다. 그만큼 내부적으로 지원하는 함수가 많기 때문에 코딩테스트 진행시 다른 언어 보다 유리하다. 그렇기 때문에 파이썬을 제대로 활용하기 위해서 알아야할 몇가지를 정리한다.set은 다음과 같은 문제 유형에서 자주 사용됩니다:중복 제거: