PS-유형분석

이론📖 구간 합?합 배열을 이용하여 시간복잡도를 더 줄이기 위해 사용하는 특수 목적의 알고리즘.📖 합 배열 S 정의Si=A0+A1+A2+ ... + Ai-1+Ai미리 합 배열을 정의하여 문제풀이에 이용하면, 기존 리스트의 일정범위의 합을 구하는 시간 복잡도가 O(N

이론📖 투 포인터?2개의 포인터로 알고리즘의 시간 복잡도를 최적화하는 것.문제풀이📖 백준 2018 (🔗백준 2018 문제)📍 시간복잡도분석으로 사용할 알고리즘의 범위를 줄여야한다.✏ O(n) 시간복잡도알고리즘 사용.시간제한은 2초인데 N의 최대값은 10,000,

이론📖 슬라이딩 윈도우?2개의 포인터로 범위를 지정한 다음, 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘문제풀이📖 백준 12891 (🔗백준 12891 문제)✏ O(n) 시간복잡도알고리즘 사용.✏ 윈도우를 한 칸씩 이동하면서 현재 상태리스트를 업데이트.이때

이론📖 스택삽입과 삭제가 후입선출(LIFO : Last-In First-Out)로 이루어진 자료구조이다.삽입과 삭제가 한 쪽에서만 일어난다.📖 큐삽입과 삭제가 선입선출(FIFO : First-In First-Out)로 이루어진 자료구조이다.삽입과 삭제가 양방향에서

이론📖 버블 정렬데이터의 인접요소끼리 비교하고, SWAP연산을 수행하여 정렬.시간복잡도 : O(n^2) -----> 속도가 느린편이다.문제풀이📖 백준 1377

이론📖 삽입정렬대상을 선택해 정렬된 영역에서 적절한 위치를 찾아 삽입하면서 정렬.시간복잡도 : O(n^2) -----> 느린편이지만 구현하기 쉽다.문제풀이📖 백준 11399 (🔗백준 11399 문제)✏ 그리디 방식.✏ 정렬사용.시간의 합이 최소가 되려면, 각 사

탐색은 주어진 데이터에서 원하는 데이터를 찾아내는 알고리즘을 말한다.DFS , BFS , 이진탐색이 있다.이론📖 DFS (깊이우선탐색)그래프 완전 탐색기법 중 하나.그래프의 시작노드에서 출발하여 탐색할 한 쪽 분기를 정해, 최대 깊이까지 탐색을 끝낸 후 다른쪽 분기로

탐색은 주어진 데이터에서 원하는 데이터를 찾아내는 알고리즘을 말한다.DFS , BFS , 이진탐색이 있다.이론📖 BFS (너비우선탐색)그래프 완전탐색 방법 중 하나.시작노드에서 출발해 시작노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘.목표노드에 도착

탐색은 주어진 데이터에서 원하는 데이터를 찾아내는 알고리즘을 말한다.DFS , BFS , 이진탐색이 있다.이론📖 이진탐색데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘.대상 데이터의 중앙값과 찾고자 하는 값을 비교하여 데이터의 크기를 절반씩 줄여나가면서

이론📖 소수약수가 1과 자기자신뿐인 자연수.📖 에라토스테네스의 체소수를 판별할 때 사용된다.1) 구하고자 하는 소수의 범위만큼 1차원리스트를 작성한다.2) 2부터 시작해서 끝까지, 숫자의 배수에 해당하는 수들을 리스트에서 지운다.(처음 선택된 숫자는 지우지않는다.)

이론 📖 오일러 피 오일러 피 함수 P[N] 은 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.

이론📖 유클리드 호제법두 수의 최대공약수를 구하는 알고리즘.📍 최대공약수📍 최소공배수문제풀이📖 백준 1033 (🔗백준 1033 문제)

이론📖 확장 유클리드 호제법ax+by=c (a,b,c,x,y는 정수) 인 방정식의 해를 구하는 것.📖 ax+by=c 인 방정식의 해 구하기.위의 방정식은 c % gcd(a,b) == 0 인 경우에만 정수해를 가진다.따라서, c는 gcd(a,b)의 배수이다.이를 바탕

이론📖 그리디 알고리즘현재 상태에서 볼 수 있는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘.But, 항상 최적의 해를 보장하지는 못한다는 단점이 있다.문제풀이📖 백준 1715 (🔗 백준 1715 문제)✏ 그리디 알고리즘.✏ .s

이론📖 그래프노드와 에지로 구성된 집합.📖 노드와 에지노드(node) : 데이터를 표현하는 단위.에지(edge) : 노드를 연결하는 부분.📖 그래프 구현 방법.에지 리스트(edge list)에지를 중심으로 그래프를 표현하는 것.리스트에 출발노드와 도착노드를 저장하

이론📖 유니온 파인드여러 노드가 있을 때, 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find연산으로 구성되어있는 알고리즘.📖 union연산각 노드가 속한 집합을 1개로 합치는 연산.집합에서 합집합

이론📖 위상정렬사이클이 없는 방향그래프에서 노드순서를 찾는 알고리즘.시간복잡도 : O(v+e) , v=노드 수 e=에지 수📍 위상정렬을 항상 유일한 값으로 정렬되지 않는다.📍 사이클이 존재하면, 노드간의 순서를 명확히 정의할 수 없다. -> 위상 정렬 적용x📖

이론

이론📖 스위핑특정 선이나 공간을 한쪽에서부터 스캔하면서 쓸어가는 알고리즘.'정렬' 을 이용해서 구현.문제풀이📖 백준 2170📌 https://www.acmicpc.net/problem/2170✍️ 공부한 내용을 정리하는 공간이기 때문에, 정확하지 않은 사