알고리즘
1.백준 1978 소수찾기, 4948번 베르트랑 공준
소수시간복잡도제곱근을 사용할 수 있는 이유베르트랑 공준 풀이베르트랑 공준 문제를 풀기 위해 여러 알고리즘들을 찾아보았는데 소수를 찾을때 이 알고리즘을 사용하면 매우매우 효율이 좋아지는걸 알게되었다.그리고 개인적으로 소수가 실생활에서 사용되는 예시들은 어떤게 있을까 궁금
2.백준 1436번 영화감독 숌, 브루트포스(완전탐색)
숫자에서 666을 찾자처음 이 문제를 접하고 30분동안 수를 직접 구해보며 규칙이 있는지 찾아보았다.그때 첫번째부터 18번째까지 규칙이 있는걸 찾아내어 주어진 수를 18로 나누어 몫, 나누기, 배열을 이용하려 하였다. (나중에는 저 규칙도 틀린것을 알게되었다.)하지만
3.백준 25501 재귀의 귀재
재귀기존 재귀 vs 꼬리 재귀재귀의 귀재재귀란?자기 자신을 호출하여 작업을 수행하는 방식특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.러시아 인형과 알고리즘 간에 어떤 상관관계가 있을까? 러시아 인형 속에 더 작은 러시아 인형이 있고
4.자료구조 - 힙 (백준 11279)
수업시간에 배운 내용을 활용하여 백준 문제에 도전하였다.배운대로 실행하여서 예제 테스트 케이스는 통과하였지만 바로 런타임 에러가 난 것을 볼 수 있었다.이번에는 알고리즘의 에러였다(신난다 !! 드디어 환경설정의 에러가 아닌 알고리즘 문제 해결 과정의 에러를 만나서 내심
5.알고리즘 공부
평소 알고리즘에 대해 부족하다고 생각되어 어떻게 알고리즘 공부를 시작하면 좋을까 하고 찾아보던 중 좋아보이는 커리큘럼과 자료들이 있어 이 내용들을 가지고 시작해보려 합니다위 문제들을 순차적으로 푸는 것이 알고리즘의 기초 입니다.알고리즘 기법 관련한 강의는 영리한 프로그
6.알고리즘 - 구간 합
백준 11659 구간 합 구간합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다 구간 합의 문제 분석 N 개의 수가 주어졌을때 일정 범위 내에 있는 구간의 합을 구하라는 문제입니다 입력은 최대 100,000 이며 합을 구
7.알고리즘 - 투포인터
이번 글에서는 알고리즘의 투포인터에 대해 알아보겠습니다투포인터란 배열에서 원래는 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘2개의 포인터가 배열을 돌때 각 포인터가 모든 배열을 1번 돌때마다 N의 시간복잡도가 나
8.알고리즘 - 버블정렬
이번 시간에는 정렬 중 버블정렬에 대해 알아보겠습니다버블 정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법입니다간단하게 구현할 수 있지만 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느린편이다위에서는 오름차순으로 정렬한다고 가정합니다1번째 루프에서
9.알고리즘 - 선택정렬
최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 핵심N개의 숫자를 정렬한다고 가정하면1번째 루프에서 N개를 탐색하며 최솟값을 찾고 그 값과 남은 정렬 부분의 가장 앞에 있는 데이터와 swap합니다두번째 루프에서는 N-1개를 탐색
10.알고리즘 - 삽입정렬
선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 핵심수행방식현재 인덱스에 있는 데이터 값을 선택한다현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다삽입위치부터 인덱스에 있는 위치까지 shift 연산을 수행합니다삽입 위치에 현재
11.알고리즘 - 병합정렬
병합정렬은 분할정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘입니다병합 정렬의 시간복잡도는 O(NlogN) 입니다위 그림의 숫자 개수는 8개 입니다병합정렬이 시간복잡도가 O(NlogN)인 이유는3번의 병합만에 결과가 나왔는데 여기서 3번은
12.알고리즘 - 기수정렬
기수정렬은 값을 비교하지 않는 특이한 정렬입니다기수정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교합니다기수정렬의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를 말합니다기수정렬은 10개의 큐를 이용합니다각 큐는 값의 자릿수를 대표합니다큐가
13.알고리즘 - 퀵정렬
퀵정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘입니다기준값이 어떻게 선정되는지가 시간복잡도에 많은 영향을 미치며, 평균 시간복잡도는 O(NlogN) 이며 최악의 경우 O(N^2)입니다퀵 정렬의 동작방식
14.알고리즘 - DFS 깊이 우선 탐색
깊이 우선 탐색 DFS 는 그래프 완전 탐색 기법 중 하나입니다 깊이 우선 탐색은 그래프의 시작노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘입니다아래 사진을 통해 쉽게 이해해보겠습니다
15.백준 1517 - 버블 소트
https://www.acmicpc.net/problem/1517분명 문제 이름은 버블 소트인데 버블 정렬 알고리즘으로 풀면 시간초과가 나는 아이러니한 문제입력으로 주어진 500,000 개의 숫자를 버블 정렬 알고리즘으로 풀면 시간 복잡도 O(N^2)이 발생하
16.알고리즘 - BFS 너비 우선 탐색
너비 우선 탐색은 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다 아래 사진을 통해 쉽게 이해해보겠습니다 핵심이론 BFS도 DFS와 마찬가지로 한 번 방문한 노드는 다시 방문하