코린이의 일기장

정렬이란? 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말합니다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됩니다. 선택정렬(Selection sort) 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬입니다. [STEP0] 처리되지 않은 데이터 중 가장 작은 '0'을 선택해 가장 앞의 '7'과 바꿉니다 [STEP1] 처리되지 않은 데이터 중 가장 작은 ‘1’을 선택해 가장 앞의 ‘5’와 바꿉니다. [STEP2] 처리되지 않은 데이터 중 가장 작은 ‘2’를 선택해 가장 앞의 ‘9’와 바꿉니다. [STEP3] 처리되지 않은 데이터 중 가장 작은 ‘3’을 선택해 가장 앞의 ‘7’과 바꿉니다. [STEP4] 이러한 과정을 ..

안녕하세요 파이썬에서 좋은 라이브러리죠 itertools에서 accumulate를 정리를 해보겠습니다. accumulate itertools.accumulate(iterable[, func, *, initial=None]) 누적 합계나 다른 이항 함수(선택적 func 인자를 통해 지정됩니다)의 누적 결과를 반환하는 이터레이터를 만듭니다. func가 제공되면, 두 인자를 취하는 함수여야 합니다. 입력 iterable의 요소는 func에 대한 인자로 허용될 수 있는 모든 형일 수 있습니다.(예를 들어, 기본 더하기 연산에서 요소는 Decimal 이나 Fraction을 포함하는 모든 더할 수 있는 형일 수 있습니다.) 일반적으로, 출력되는 요소 수는 입력 iterable과 일치합니다. 그러나, 키워드 인자 i..

안녕하세요 오늘은 누적합을 이용하는 백준 알고리즘 문제를 풀어보고 정리하는 시간을 가져보겠습니다 백준 11659번 URL : https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 반복문으로 구간 합을 구할 때의 문제점 최대 10만 개까지 배열에서, 최대 10만 개의 질문에 대해 i번째부터 j번째까지의 합을 출력해야 한다. N개의 수를 입력받아둔 배열을 arr (N+1개 크기의 배열을 만들고 0번은 사용하지 않습니다.)이라고 할..

안녕하세요 알고리즘을 블로그 정리해보는 시간을 가져볼게요 이번 시간에는 백트래킹 알고리즘 정리와 BOJ 문제를 풀어보도록 하겠습니다. 백트래킹(Backtracking) "가능한 모든 방법을 탐색한다" 모든 경우의 수를 전부 고려하는 알고리즘 상태 공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(DFS)과 너비우선탐색(BFS), 최선 우선 탐색이 있다. 모든 경우의 수를 고려해야 하는 문제라면 DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS로 구현했다간 큐의 크기가 심지어 속도도 똑같다. 따라서 경우의 수 구하기는 일반적으로 DFS가 편리하다. 대다수의 문제들은 DFS를 써도 일단 답은 나온다. 즉, 백트래킹은 현재 상태..

안녕하세요 저번 시간에 DFS와 BFS 사용하기 위해서 알아야할 개념과 DFS와 BFS 개념 그리고 간단한 예제를 통해서 알아보았는데요 2022.10.20 - [python] - [Python] 알고리즘 DFS, BFS 정리 [Python] 알고리즘 DFS, BFS 정리 안녕하세요 카카오 서버 문제로 티스토리를 활용을 못해서 복구된 기념으로 알고리즘 정리를 해보려고 합니다 DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지를 해야합 nosechild.tistory.com 이번 시간에는 여러 개의 문제를 통해서 DFS와 BFS 푸는 방법에 대해서 알려 드리겠습니다. DFS 예제( 백준 2606 ) https://www.acmicpc.net/problem/2606 2606번: 바이러스..

안녕하세요 카카오 서버 문제로 티스토리를 활용을 못해서 복구된 기념으로 알고리즘 정리를 해보려고 합니다 DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지를 해야합니다. DFS랑 BFS를 알기 전에 알아야 할 개념에 대해서 정리를 해보겠습니다. 스택 자료구조 - LIFO 먼저 들어 온 데이터가 나중에 나가는 형식(선입 후출)의 자료구조입니다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있습니다. 큐 자료구조 - FIFO 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조입니다. 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있습니다. BFS를 활용할 때는 Queue의 단점을 극복한 Deque 라이브러리를 사용해서 문제를 풉니다. Deque에 관..

안녕하세요 알고리즘을 공부하면서 블로그에 정리하는 시간을 가졌는데요 2022.09.19 - [python] - [Python] 그리디 알고리즘의 응용(백준 알고리즘) [Python] 그리디 알고리즘의 응용(백준 알고리즘) 안녕하세요 저번 시간에 했던 최대힙, 최소힙 다음으로 알고리즘 중에서 그리디 알고리즘에 대해서 정리를 해보겠습니다. 2022.09.16 - [python] - [Python] 자료구조 - 최소힙, 최대힙 [Python] 자료구조 - nosechild.tistory.com 저번 게시물에는 그리디 알고리즘을 자세히 정리해보았는데, 이번에는 이진 탐색(이분 탐색)에 대해서 설명해드릴게요 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법입니다. 이..

안녕하세요 저번 시간에 했던 최대힙, 최소힙 다음으로 알고리즘 중에서 그리디 알고리즘에 대해서 정리를 해보겠습니다. 2022.09.16 - [python] - [Python] 자료구조 - 최소힙, 최대힙 [Python] 자료구조 - 최소힙, 최대힙 안녕하세요 알고리즘 공부를 하다가 힙 문제가 나와서 정리를 해서 블로그에 정리를 해보려고 하는데요 다들 참고하고 부족하신건 댓글로 달아주세요 힙 자료구조 힙은 특정한 규칙을 가지는 nosechild.tistory.com 그리디 알고리즘 그리디 알고리즘은 일명으로 탐욕법이라고도 하는데요. 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적으로 그리디 알고리즘 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 구합니다. 그리디 알고리즘..

안녕하세요 알고리즘 공부를 하다가 힙 문제가 나와서 정리를 해서 블로그에 정리를 해보려고 하는데요 다들 참고하고 부족하신건 댓글로 달아주세요 힙 자료구조 힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진트리 기본으로 한다. 각 노드의 key 값이 해당 노드의 자식 노드의 key 값보다 작지 않거나 크지 않은 완전 이진트리 키 값의 대소 관계는 부모-자식 노드 사이 간에만 성립하며 형제 노드 사이에는 영향을 미치지 않음 자식 노드의 최대 개수는 힙의 종류에 따라 다르지만 이진트리에서는 최대 2개(완전 이진트리를 사용한다고 가정) i번째 노드의 자식 노드가 2개인데 왼쪽 자식 노드는 2i, 오른쪽 자식 노드는 2i+1이고, 부모노드는 i/2가 됩니다. 최소..

안녕하세요!! Python 알고리즘을 공부하면서 알고리즘에 대해서 자세히 정리를 해보려고 하는데요 개념적으로 알고 있으면 코딩 테스트할 때 도움이 되지 않을 까..? 생각해서 정리를 해보겠습니다. 동적 계획법(DP, Dynamic Programming) 큰 문제를 작은 문제로 나눌 수 있다 작은 문제에서 구한 정답을 그것을 포함하는 큰 문제에서도 동일하다 피보나치 수열은 다이내믹 프로그래밍의 사용 조건을 만족합니다. 재귀 함수를 이용하다 보면 러닝타임이 기하급수적으로 늘어남을 관찰을 할 수 있습니다. 이러한 문제를 해결하기 위해 다이내믹 프로그래밍을 사용해야 한다. 다이내믹 프로그래밍의 포인트는 바로 한 번 결과를 수행한 것을 메모리에 저장해 놓고 다음에 똑같은 결과가 필요하면 그때 다시 연산하지 않고 ..