CODE_TEST

파이썬 특유의 문법이나 스타일로 코딩을 하는 경우가 있는데 다양한 레퍼런스 코드들을 보다보니 이해안되는 부분도 있고 해서 정리해봤다. 그리고, 실제로 for loop으로 append 하는 것보다 list가 조금 더 빠르다. 효율적인 면도 있고 아무래도 다른 파이썬 개발

greedy는 '탐욕스러운' 이라는 뜻을 가지고 있다. 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 선택지를 고르는 탐욕적인 방법을 의미한다. 해당 선택이 나중에 끼칠 영향 따위는 생각하지 않는다. 반대로 생각하면, 문제가 주어졌을 때 해당 문제가 단순히 현재 상황

재귀함수란? 함수에서 자기 자신을 다시 호출해 작업을 수행하는 함수이다. 재귀함수는 일정 조건이 충족되면, 함수를 이탈해 결과를 도출한다.주로 재귀함수를 종료시키는 기저사례가 코드의 최상단에 위치한다. 메인로직은 모두 같고, 전달인자만 변하는 것이기 때문에, 반복적인

정렬은 데이터를 특정 기준에 따라서 순서대로 나열하는 것을 말한다. 데이터를 오름차순이나 내림차순으로 정렬해서 사용하는 경우가 있기 때문에, 많이 사용되는 알고리즘 중 하나이다. 이진탐색을 위한 전처리 과정으로도 정렬이 필요하다. 선택정렬, 삽입정렬, 퀵 정렬, 계수

이진 탐색 알고리즘은 정렬된 데이터에서 원하는 값을 빠르게 찾을 수 있는 탐색 알고리즘이다. 먼저 기본적인 순차탐색에 대해 알아보자리스트 안의 특정 데이터를 찾기 위해서 앞에서부터 하나씩 차례대로 확인하는 방법이다. 정석대로 for문을 돌며 각 원소를 돌며 원하는 값을

연산속도, 메모리 공간을 최대로 활용할 수 있게끔 하는 알고리즘이 있다. 특히, 다이나믹 프로그래밍은 메모리 공간을 약간 더 사용해 값을 저장해두는 것으로 연산속도를 비약적으로 증가하는 알고리즘이다. 2가지 방법으로 구현 가능하다. 각각 Top down(재귀함수) Bo

탐색은 자주 등장하는 코딩 테스트 유형으로, 많은 양의 데이터 중 원하는 데이터를 찾는 과정이다. 그래프나 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있다. 이 두 탐색 알고리즘을 위한 기본 자료구

다익스트라 알고리즘은 시작 노드에서 graph에 존재하는 다른 모든 노드까지 걸리는 최단경로를 찾는 알고리즘이다. 노드를 연결하는 간선의 가중치가 모두 양수일때를 전제로한다.   우선순위 큐와 for문을 사용해서 구현 가능하다. 먼저 기본적인 알고리즘의 동작 원리를 살

다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 사용할 수 있는 최단 경로 알고리즘이다. 플로이드 워셜 알고리즘은, 모든 지점에서 모든 지점까지의 최단 경로를 구해야 하는 경우 사용할 수 있는 알고리즘이다.시간 복잡도 : $O(N^

다익스트라나 플로이드 워셜과 같이 여러 기타 그래프 탐색 알고리즘에 대해서 정리해보고자 한다. 먼저, 서로소 집합이다. 서로소 집합 자료구조는 union-find 자료구조라고 불리기도 한다.먼저, 서로소 집합의 수학적인 의미는 공통적인 원소가 없는 두집합을 의미한다.

신장 트리는 모든 노드를 포함하면서, 사이클이 존재하지 않는 그래프를 의미한다. 이는 트리의 성립 조건이기도 하다.위와 같이 모든 노드를 포함하고, 사이클이 존재하지않는 것을 신장 트리라고 하며, 한개의 그래프에서 여러개의 신장트리가 존재할 수 있다.최소한의 비용으로

위상 정렬은 정렬 알고리즘의 일종이다. 순서가 정해져있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 정확히는, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다.📌 진입 차수진입차수란 특정한 노드로 '들어오는'

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 떄 생성되는 총 아이스크림의 개

유클리드 알고리즘이란? 유클리드 알고리즘은 2개의 자연수 혹은 정식($\frac 1 2$나 $\sqrt 3$과 같이 분모나 근호 속에 문자를 포함하고 있지 않은 식)의 최대공약수를 구하는 알고리즘의 하나이다. '호제법'이란 말은 두 수가 서로 상대방의 수를 나눠 원하는

백트래킹은 기본적으로 모든 경우의 수를 고려해 해를 찾는 방식 중 하나이다. 완전탐색과 중요한 차이는 탐색과정 중에서 조건에 맞지 않다면 빠꾸하고 다음 후보를 탐색하는 것이다. 백트래킹에서 검색할 후보는 트리형태로 표현한다. 상태 공간 트리 위의 그림에서 알 수

문자열 탐색을 효율적으로 수행하기 위한 Tree 기반 자료구조이다. 문자열 검색, 자동완성, 사전 구현 등에 사용된다.각 노드가 한개의 문자를 저장하는 트리 구조이다. 루트 노드는 공백이고, 각 간선은 문자를 나타낸다. 문자열이 삽입될 때, 각 문자의 경로를 따라 노드

해당 문제에 주어진 삼각형의 제일 아래층 부터 위로 거꾸로 거슬러 올라가며 최대값이 나오게끔 하는 경로를 구하였다. 마지막에서 두번째 층부터 차례로 값들을 저장했다. 어떤 값을 저장했냐면, 바로 다음 층에서 고를 수 있는 두가지 경우 중 큰 값을 골랐을 때를 기준으로

일단 간단하게 생각했다. N개의 사이트에서 M개의 사이트로 가능한 모둔 경우의 수를 구하는 문제이다. 몇가지 조건이 존재한다.$N \\leqq M$ 이기 때문에 도착지가 더 적은 경우는 없다.N이 0보다 크기 때문에, 출발지가 없는 경우는 없다.다리를 겹쳐둘 수 없고,

거스름돈을 계산하는 유사한 문제를 풀었던 기억이 있다. 그 문제는 동전의 값어치가 문제에서 주어졌었는데, 이 문제는 동전의 값어치를 입력받기 때문에, 동전간 배수관계를 확인할 수 없다.따라서, DP로 해당 문제를 접근했다. DP는 큰 문제를 작은 문제로 소분하고, 점화

간단하게 생각하기트럭에 실을 수 있는 짐이 한정되어 있는 점을 명시해야함출발지점과 가까운 도착점(두번째 idx) 기준으로 오름차순으로 정렬→ 문제의 조건에서 🛻은 한번 지나간 마을로 되돌아갈 수 없고, 실린박스도 도착 마을에서만 내릴 수 있다고 주어졌다.→ 트럭은 한

핵심은 치즈가 아닌 공기 기준 탐색.0과 1로 이루어진 graph에서 0인 부분만 탐색을 해보자.외부공기와 맞닿아 있는 치즈 벽 부분만 1번의 탐색과정에서 (nx,ny) 로 접근 가능하다.2-1. 외부공기에서 두번이나 접근 가능한 치즈들은 1시간 뒤에 사라지게 되는 치

1\. 평범한 DP문제처럼 보이지만 메모리 제한에 주의할 것2\. 일반적으로 메모리 사용량 기준은 MB 단위로 제시됨 \- 코테는 대부분 리스트 사용하는 데 정수형 int 타입 기준 아래와 같음 \- int a1000=4KB (int자료형은 4byte)

여행 계획에 속한 도시들을 어떤 경로로 가던지 가기만 하면 된다. 즉, 여러 번 방문하는 것이 가능하기 때문에, 여행 계획에 속한 도시들이 뭔가 하나로 연결이 되어있다면 방문할 수 있는 것이다. 문제의 예시를 보고 접근해보자문제의 예시는 아래와 같은 상황이다.1번 도시

1\. 노드가 각각 숫자가 아닌 사람 이름으로 주어진 것에 주의해야한다.1.1 숫자 테이블을 선언하여 문자별로 어떤 수에 대응되는지 확인할 수 있다1.2 부모 테이블에 바로 이름값을 넣는걸로 부모를 직접 가리킬 수 있다.1.2 방법을 선택했을 때, union과정에서 어

1\. 먼저 시간복잡도를 통해서 어떻게 팀가치를 계산할지 고민해보자.최대 인원이 참가했을 때 20명 중 10명을 고르는 경우의 수와 각 경우의 수 마다 팀가치를 계산하는 시간을 계산하면 이는 문제의 정해진 조건보다 작은 것을 알 수 있다.점수를 계산하는 과정은 two

1\. 도시 n개가 있고, 각 도시를 잇는 버스(비용)이 있음2\. A에서 B까지 가는데 비용을 최소화 해야함3\. 버스 비용은 무조건 자연수임위의 조건을 통해서 다익스트라라는 것을 알 수 있다.한 노드에서 다른 노드로 이동하는데 드는 최소 비용을 구해야하며, 노드 간

1\. 문제에서 로마 문자의 순서는 중요하지 않고, 개별로 각각 더해서 계산한다고 했다. 즉, \[1 5] 로 나오는 경우와 \[5 1]로 나오는 경우가 같은 의미라는 것이다. (편의상 로마자는 숫자로 대체했습니다.)2\. 시간 복잡도를 미리 생각해보면, 시간 제한 2

1\. 먼저 실제 경기가 몇번 치뤄지는지 판단해보자. 총 6개국으로 구성되어 있으니, $\_6C_2$ 이다. (순서는 신경 쓰지않고 2개를 뽑는 경우의 수다. 즉 15경기만 이뤄진다.2\. 1.에서 구한 경우의 수를 실제로 표현해보면, 아래의 표와 같다. (편의상 홈과

뒤죽박죽 섞여있는 B로부터 A배열을 찾아내야한다. 이전 수에서 3으로 딱 나누어 떨어지거나, 이전 수에서 2를 곱한 수가 다음 수로 오게끔 순서대로 이루어진 배열을 찾으려면 어떻게 해야할까?이 문제를 처음 읽어보고 하나의 트리 구조가 떠올랐다. 트리의 높이는 각 배열의

스티커를 붙이는 방법에 대해서 생각해보자. 일단 모눈종이 안에 스티커를 집어 넣어야한다. 문제에 두 스티커가 겹치면 안된다는 매우 중요한 조건이 있다. 그리고 스티커를 90도 회전하는 것도 가능하다. 당연히 모눈종이에서 스티커가 벗어나는 것도 안된다.스티커는 주어진 여

1\. 연산자의 우선순위를 무시하고 앞에서부터 진행하는 것이 포인트인 듯 하다. 하나의 트리로 연산결과를 정의할 수 있다.예를들어, 5개의 수에 대한 연산을 진행할때는 위와 같이 경우의 수를 계산할 수 있다. -로 시작하는 상황에서 2L로 오는 +가 사실 두개가 올 수

1\. 하루하루를 기준으로 연합을 체크한다. BFS로 탐색하면서, L이상 R이하인지를 확인하면서 따로 visited 했는지 체크해두면 연합별로 묶을 수 있다.BFS 내부 함수에는 인접한 나라와의 인구 수 차이가 L과 R 사이인지 체크하고, 이미 방문한 국가인지 아닌지

direction을 표현해야 한다. 동서남북으로 이동할때, 각각을 0,1,2,3으로 표현할 수 있다.매 시간마다 방향을 바꿔야 한다. 동서남북으로 이동할 수 있는 민식이는 직전의 이동방향과 다르게 이동해야하기 때문에, 직전의 이동방향을 저장해야한다. BFS 이동에 사

1\. 각 재료의 양은 정수다. 모든 재료는 비율로 입력이 제시된다는 것을 생각하면, 비율 계산 결과가 실수가 나오면 안된다는 것.예를들어, A재료의 질량이 10이고, A:B=1:4이면, B는 2.5가 되는데 이는 불가능하다.그러면, 우리는 기준 질량값을 최소공배수로

1\. 가지고 있는 예산 기준 가장 높은 방 번호를 구해야한다.2\. 방 번호가 높은 순서부터 차례대로 예산에 입력해보자.DP15=max(DP15,DP15-7\*10+2) 로 비교하게 된다.방 번호가 높은 순서부터 차례대로 고려하는 이유는, 23,32 모두 같은 예산이

일단 "anta"로 시작해서 "tica"로 끝나는 단어만 있어서, "antic" 5글자는 최소 알아야한다.26개 철자 모두 알면 주어진 n개의 단어 모두 읽을 수 있다.그 사이에 있는 단어들은 읽을 수 있는지 확인해야한다.학생이 배우는 글자의 경우의 수를 모두 탐색하면

1\. 322가 불가능하다 → 중복되는 수는 등장할 수 없다.2\. 직접 감소하는 경우들을 살펴보자. 0/10/21 20/32 31 30/43 42 41 40/... 자릿수 별로 구별해서 살펴보자. 한자리 수 → 0 두자리 수 → 10 / 21 20 / 32 31 30

1\. 문제에 주어진 예시로 한번 직접 LCS를 구해보자.2\. 다른 예시도 최장 공통 부분 수열을 구해보자.3\. 비교하는 두 문자열을 하나씩 추가해보며, 비교해보면 아래의 표와 같다.4\. 특히, ACA, CA를 비교하는 상황을 보자. 둘 다 마지막에 A로 끝나는

위의 사진은 다익스트라 알고리즘의 과정을 의미한다. 최종적으로 우리가 구하고 싶은 것은, 시작노드에서 다른 노드까지의 최단거리이다. 하지만, 위의 경우, 그리디 알고리즘 기반으로 하는 다익스트라 알고리즘은 4 가중치인 노드를 먼저 방문하기 때문에, -90의 결과를 얻을