알고리즘

최단 경로 알고리즘 - 다익스트라

최단 거리 알고리즘 - 플로이드 워셜

알고리즘 - 카데인 알고리즘

에라토스테네스의 체

merge sort(합병정렬)

퀵정렬

버블정렬

삽입정렬

힙 자료구조

BST

가장 먼저 구현하려고 했던 것은 바깥 쪽 테두리 배열을 돌리는 것이다.이것은 상, 하, 좌, 우 방향을 나누어서 구현하였다.현재 배열의 값을 다음 배열에 덮혀 씌워야 하므로 다음 배열의 값을 저장할 변수 tmp를 선언한다.이것을 코드로 나타내보자depth는 쉽게 말해

이렇게 구현하기 위해서 재귀함수를 사용해야 한다.start => 시작지점mid => 경유지점end => 도착지점 이다.재귀함수를 통해 n-1개를 start지점에서 end지점을 경유해 mid지점으로 둔다. 그래야지 마지막 원판을 end지점에 놓을 수 있기 떄문이다.그 다

이 문제와 비슷한 문제를 풀어본 적이 있었다.리트 코드 문제였는데 연결해서 가장 긴 체인 수를 구하는 문제이다. 이 때에는 다이나믹 프로그래밍 방법으로 해결하였다.\[1, 2, 7, 8, 4, 5]를 설명하면 처음으로 left를 기준으로 정렬한다. \[1, 2, 4,

3잔을 연속으로 마실 수 없다는 것이 키포인트이다.포도주가 1개 있을 때 생각해보자n=1일 때에는 1번째 잔을 마시면 된다.(dp1 => wine1)포도주가 2개 있을 때 생각해보자n=2일 때에는 1번째 잔, 2번째 잔을 마시면 된다.(dp2 => wine1 + win

A를 B번 곱하면 O(n)만큼 시간이 소요가 된다. 조건에서 A,B,C는 대략 21억 정도가 되니 시간제한 0.5초에 비하면 턱없이 오래 걸린다. 따라서, 분할 정복을 통해 시간 복잡도를 O(logn)으로 변경해야 한다.시간복잡도를 어떻게 O(logn)으로 줄일 수 있

이 문제는 전에 풀었던 쿼드트리 문제랑 비슷했다.쿼드트리:https://www.acmicpc.net/problem/1992분할 정복으로 풀기 위해서 mid_row, mid_col을 알아야 했다.mid_row와 mid_col을 어떻게 구하지?🤔순서는 1, 2,

예제 입력배열을 서류 점수로 오름차순 정렬해보자1\. 첫 번째 TC\[1, 4, 2, 3, 3, 2, 4, 1, 5, 5]2\. 두번째 TC\[1, 4, 2, 5, 3, 6, 4, 2, 5, 7, 6, 1, 7, 3]여기서 알 수 있는 것은 면접시험만 생각하면 된다는

다이나믹 프로그래밍 방법으로 풀어야 한다.3가지 경우가 있다.오른쪽에 있을 경우왼쪽에 있을 경우아무것도 없을 때N = 1일 때 생각해보자dp0 => 왼쪽에 있을 때 하나만 가능하다. = 1dp0 => 오른쪽에 있을 때 하나만 가능하다. = 1dp0 => 왼쪽 오른쪽 둘

예제 1일 때 생각해보자3 => 1114 => 1111이다.1111 , 111의 최대공약수는 1이다.마찬가지로3 => 1116 => 111111111, 111111의 최대공약수는 111이다.여기서 알 수 있듯이 a, b의 최대공약수를 구하고 최대공약수만큼 1을 써주면

단순히 list의 기능 중 pop과 insert를 이용해서 풀었다.하지만 pop, insert를 하게 될 경우 O(n)이라는 시간복잡도 때문에 시간초과가 발생하였다.https://corin-e.tistory.com/entry/%EB%B0%B1%EC%A4%80-

문제에서 이동할 수 있는 범위는 3가지로(r + 1, c)(r, c + 1)(r + 1, c + 1)이다.이 3가지 경우에서 최대값을 구하는 DP형식으로 문제를 풀었지만 시간초과가 발생하였다.처음 푼 풀이와 다를 것이 없다. 하지만 한 가지가 다른데 이동할 수 있는 범

이 문제의 핵심은 팩토리얼에서 소인수분해를 하는 것이다.물론 소인수분해를 다 하는 것이 아니다.우리가 필요한 것은 2, 5뿐이다.ex) 25! => 2의 지수는?답은 12+6+3+1 = 22이다.2가 포함된 수 => 2,4,6,8,10,12,14,16,18,20,22,

브루트 포스로 구현하였다. 땅의 높이는 256블록까지라고 명시를 했으므로 earthHeight를 땅의 높이를 0 ~ 256까지 나타내는 변수로 지정하였다.만약 earthHeight보다 현재 땅이 높다면 그 차이 만큼 inventory에 넣을 수 있다. 넣을 때 시간은

예제를 기준으로 설명하면arr1 = 12, 13, 21, 48, 52arr2 = 7, 8, 10, 14, 20arr3 = 9, 11, 26, 28, 32arr4 = 15, 19, 31, 35, 41arr5 = 5, 6, 16, 25, 49로 입력받을 수 있다.항상 ar

Combination을 사용해 풀었다.만약 headgear의 개수가 3, face의 개수가 2, eyewear = 1이라고 가정하자그럼 arr = 3, 2, 1이 될 것이고 이것을 컴비네이션으로 풀게 되면i = 1일 때 => 3, 2, 1i = 2일 때 => 3\*2,

2, 3, 6, 5, 4, 1라는 순열이 있을 때, 오른쪽 끝에서부터 순회하여, 내림차순 배열이 끝나는 지점을 찾는다.2,3/6,5,4,1 => 2,3과 6,5,4,1사이에서 내림차순 배열이 끝이난다.교체할 자리를 찾는다.앞서 내림차순이 종료되는 숫자 (3)을 찾았다

처음에 승률 100%일 때와, 현재 승률 구하는 공식으로 int((y / x) \* 100)을 했다.하지만 이렇게 하니 통과하지 못했다.승률 100% 뿐만 아니라 99%도 해줘야 한다. 왜냐하면 절대 100%는 될 수 없기 때문이다. 또한 int((y\*100 / x)

정렬하는 문제이다.첫 번째 정렬기준은 길이 순으로 정렬하는 것이다.두 번째 정렬기준은 모든 자릿수의 합과 비교하여 작은 합을 기준으로 정렬한다.세 번째 정렬기준으로는 사전순으로 정렬하는 것이다.파이썬에서 lamda를 사용해서 3가지 기준으로 정렬을 할 수 있다.len(

배열을 만들기 위해서 달팽이를 거꾸로 생각을 했다.(0, 0, 25) ~ (4, 0, 21) => 아래방향(4, 1, 20) ~ (4, 4, 17) => 오른쪽방향(3, 4, 16) ~ (0, 4, 13) => 위쪽방향(0, 3, 12) ~ (0, 1, 10) => 왼

문제 knapsack알고리즘 물건 1. 무게: 6, 가치: 13일 때 가방 무게가 1~5까지일 때에는 6을 담을 수 없으므로 0이 된다. 하지만 6, 7에서는 6을 담을 수 있다. dp1 = dp0 + 13 이라고 할 수 있다. (이전 최대값) dp1 = dp0 +

위에 표는 규칙을 찾아낸 표이다.ex) 0~1일 때 => 10~2일 때 => 110~3일 때 => 111...0~20일 때 => 12344321이제 2^31인 큰 수의 값을 구하기 위해선 1~2^31까지 하나씩 찾는 것이 아니라 규칙을 찾아야 한다.반복 횟수에서 해답을

이 문제는 다익스트라를 사용해서 풀면 된다.그래프로 나타내보자이것을 표로 나타낼 수 있다.각 노드별 최소 경로를 inf로 초기화 한다.1\. 시작경로는 1이다.즉 1에서 2 => 21에서 3 => 31에서 4 => 11에서 5 => 10 이다.현재 최소경로는 전부 in

이 문제는 유니온 파인드 알고리즘을 사용하여 풀 수 있다.유니온 파인드란 무엇일까? 1\. 먼저 1~6까지 있을 때 세팅을 먼저 하자표에서 첫째 줄은 노드 번호둘째 줄은 부모 노드 번호 이다.현재 노드와 부모 노드는 같다고 세팅을 하자1 -> 6 연결6의 부모 노드는

그래프를 그리면 문제를 쉽게 이해할 수 있다.6은 수신받을 탑이 존재하지 않으므로 0이 된다.9는 6이 있지만 낮으므로 0이 된다.5는 9가 있으므로 2가 된다.7은 9가 있으므로 2가 된다.4는 7이 있으므로 4가 된다.처음에 2중 포문으로 찾으려고 했지만 시간초과가

처음 이 문제는 그리디 문제라고 생각했다.즉 많이 겹치는 부분을 먼저 삭제하고 더 이상 겹치는 부분이 없을 때까지 진행하였다.쉽게 말해1 - 8 => 5겹침2 - 2 => 2겹침3 - 9 => 4겹침6 - 4 => 2겹침7 - 6 => 2겹침9 - 7 => 2겹침10

배열 \[1, 2, 3, 2, 5] 가 주어졌을 때 합이 5인 부분 연속 수열 갯수를 알고 싶다 라고 가정해보자브루트포스 사용하면 O(N^2)를 사용해서 찾을 수 있다.하지만 투 포인터를 사용하면 O(N)으로 찾을 수 있다.초기단계 시작점과 끝 점이 첫 번째 원소 인덱

아이디어는 다음과 같다.만약 정렬된 배열 \[-99 -2 -1 4 98]이 있을 때\-99가 0이 되려면 99가 되어야 한다.즉 이진탐색을 사용하면 \[-99 -2 -1 4 98 99]가 될 것이고 반환되는 인덱스는 5가 될 것이다.즉 배열에서 99와 가장 가까운 것은

처음엔 bfs로 모든 경로를 탐색했다.하지만 시간 초과가 발생하였다.Top - down DP로 변경하여 문제를 풀었다.아이디어는 다음과 같다.가로일 때를 생각해보자 가로가 나올 수 있는 방향은 가로, 대각선 2개이다.세로일 때는 세로, 대각선 2개이다.대각선일 때는 가

앞서 내가 실수했던 부분은 이진트리만 생각해서 풀었던 것이다.자식노드가 2 이상이 될 수 있다는 점을 고려하고 풀어야 한다.또한 루트 노드가 항상 0번째 인덱스가 아닐 수가 있다는 것이다.이 것을 고려하고 풀어야한다.파이썬에서 노드를 선언해 보자이진트리이진 트리일 때에

처음에 이진 검색 트리를 만들고 해당 트리에서 후위 순회하는 코드를 작성하였다.하지만 시간초과가 발생하였다.다른 블로그를 참고하였는데 전위 순회를 가지고 후위 순회를 나타낼 수 있다는 것이다.전위 순회 특성상 루트, 왼쪽 서브트리, 오른쪽 서브트리 순으로 출력이 된다는

처음 풀었을 때 잘못 접근했던 부분이 2가지가 있었다.1\. 그리디로 접근하기 (그리디로 하면 안된다.)집과 편의점 사이 거리 중 가장 가까운 편의점 부터 접근을 하였다.하지만 이렇게 하면 문제점이 발생하는데음수일 때를 생각을 해야 한다.(TestCase)집 => 0,

1\. 최대 높이 찾기3 1 2 3 4 1 1 2에서 최대값은 4인 것을 알 수 있다.2\. 최대 높이 기준 왼쪽에서 최대 높이 찾기3 1 2 3에서 최대값은 3인 것을 알 수 있다. 3이 다른 인덱스에도 나오지만 먼저 나온 0번째 인덱스인 3 기준으로 한다.이제 화살

다각형 면적을 어떻게 구할까라는 의문이 들었다.삼각형, 사각형 이런 것들은 잘 알고 있지만, N 다각형은 도무지 몰랐다.처음 생각한 것은 N각형은 삼각형의 집합으로 이루어져 있다는 것이다.또한 삼각형의 좌표를 알면 넓이를 알 수 있기 때문이다.하지만 삼각형을 어떻게 안

문제 풀이 1 (DP?) 처음 문제를 보고 DP가 아닐까 생각을 했다. 십의 자리가 3일 때를 생각해보면 올 수 있는 일의 자리는 2, 1, 0이 된다. 마찬가지로 백의 자리가 3일 때를 생각해보면 올 수 있는 십의 자리는 2, 1, 0이 된다.

처음엔 백트래킹으로 문제를 풀었다.전형적인 백트래킹이라 생각하였고, 2 \*\* 100 이라는 큰 수지만 조건 때문에 줄어들지 않을까 생각하였다.하지만 역시나 시간초과가 발생하였다.이런 큰 연산을 처리하기 위해선 이전 값을 토대로 계산하는 DP 알고리즘을 사용해야 한다

DP문제이고 입력값은 백만이 넘는 수가 주어지기 때문에 일차원 배열에서 단일 포문으로 문제를 풀어야 했다.예제 입력 1 기준으로 설명하자면Day1일 때 시간은 3만큼 걸리므로 4에 10을 추가한다.하지만 이렇게 할 경우 1만큼 걸릴 때에는 당일치기이기 때문에 -1을 해

처음 S에서 T를 찾는 경우를 모두 탐색하였다.하지만 이렇게 하면 시간초과가 발생한다.왜냐하면 S길이는 999이므로 2\*\*100이라는 큰 연산이 발생하기 때문이다.다른 방법은S에서 T를 찾는 것이아니라 T에서 S를 찾아가는 방법인 것이다.ABBA1\. 마지막 문자가

그리디로 풀면 되는 문제이다.수신 가능 영역의 길이의 합을 최소화 해야 한다.예제 입력1\[ 1, 6, 9, 3, 6, 7 ] 을 정렬 해보자\[ 1, 3, 6, 6, 7, 9 ] 가 된다.각 사이의 차이를 구해보자\[ 2, 3, 0, 1, 2 ]가 된다.문제에서 k는

기존 BFS 문제에서는 2차원 배열로 해결하였다.하지만 이 문제에서는 2차원 배열로 해결할 수 없었다.그 이유는 열쇠가 6개 존재하고, 열쇠 상황에 맞게 방문처리를 해야 한다.처음 열쇠가 없는 상태에서 BFS 탐색하다가 열쇠를 만나면 열쇠가 추가된 상황에서 다시 BFS

유니온 파인드makeset => 자기 자신을 부모로 하는 배열을 만든다.find => 자기 자신의 부모 노드를 찾는 함수로서, 재귀함수를 이용하여 찾는다.기저조건은 자기자신이 부모일 때 해당 값을 리턴해주면 된다.union은 합치려는 node의 부모노드와 new_nod

A~Z까지 피연산자가 나오면 더해준다.스택이 비어있고 연산자가 나오면 스택에 추가한다.스택이 비어있지 않다면 스택의 top과 현재 연산자와의 우선순위를 비교한다.3.1 만약 현재 연산자 우선순위가 더 크다면 스택에 그냥 넣어준다.3.2 만약 현재 연산자 우선순위가 같거

위상정렬해당 인풋을 기준으로 위상정렬을 해보자1 -> 02 -> 13 -> 14 -> 15 -> 16 -> 17 -> 28 -> 1즉 from, to 기준으로 to로 들어오는 개수를 세준다.개수가 0인 것을 기준으로 출발하면 시작할 수 있는 노드는 1말곤 없다.1부터

크루스칼 알고리즘 사용하기최소 신장 트리는 그래프 내의 모든 정점을 포함하고, 트리사용된 간선들의 가중치 합이 최소인 트리를 의미한다.즉 노드가 7개가 있으면간선 6개를 사용해서 모든 노드가 연결되고 이 중 최소 비용의 간선을 찾는 것이다.이 문제에서 이 아이디어를

일반적으로 DP테이블을 만들어서 LCS를 찾는 것은 할 줄 알았다. 하지만 LCS의 경로를 찾는 것은 처음 접해 본 문제였다.일단 LCS 구하는 DP 테이블이다.DP 테이블을 갱신하면서 만약 str1row == str2col이라면 이전 dprow - 1에서 개수를 가져

순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위한 알고리즘이다.여기서 보면 정보처리기사 합격하기 전에 4학년 되기가 되어야하고 4학년되기전에 대학생 되기가 수행되어야 한다. 이렇게 순서가 정해져 있을 때 사용하는 알고리즘이다.문제에서 보면 학

여러 지역을 돌면서 물건을 판매해야 하는 판매원이, 모든 지역을 돌고 다시 출발점으로 돌아와야 한다고 할 때, 가장 최적의 경로를 찾는 문제즉 출발점이 어디에서든 같은 최단 경로를 도출한다는 의미이다.통상적으로 첫 번째에서 시작하여 첫 번째에서 끝이 난다.만약 N이 2

이 문제의 키포인트는 다음과 같다.1\. postorder는 left => right => root 순으로 항상 마지막에 root가 나온다.2\. inorder에서 left => root => right 순으로 root 기준으로 왼쪽은 left, 오른쪽은 right 이

최소 연산 횟수를 구해야 한다. 그렇기 때문에 bfs를 생각해야 한다.조건에서 가능한 경우는 4가지가 있다. 한 행, 한 열, 대각선 \\, 대각선 / bfs를 사용하려면 방문처리를 해야한다. 이 때 비트마스킹이 사용된다.HTTHTTTHH가 있을 때 비트마스크로 나타내

주어진 그래프에서, 1번 노드는 루트 노드라고 가정합니다.1번 노드가 가질 수 있는 상태는 다음 두 가지입니다:얼리 아답터일 때얼리 아답터가 아닐 때이때, 자식 노드들의 상태는 다음 두 가지 중 하나일 수 있습니다:자식 노드가 얼리 아답터일 때자식 노드가 얼리 아답터가