알고리즘

· 알고리즘
1. DFS (깊이 우선 탐색, Depth-First Search)🔥DFS란?한 길로 쭉 들어가서 더 갈 수 없으면 다시 돌아와서 다른 길로 가는 방법이다.한 방향으로 계속 가다가 막다른 길이 나오면, 다시 뒤로 돌아와 다른 길을 찾는 방식이다.🔥구현 원리Stack(스택)을 써서 구현한다.Stack은 책을 쌓듯이, 마지막에 들어온 책이 먼저 나가는 방식 이다. (LIFO, Last-In First-Out)🔥시간복잡도O(V+E)이다.O(정점의 수 + 간선의 수)이다.🔥주로 쓰이는 곳미로 찾기처럼 모든 경우의 수를 확인하거나, 특정 경로를 찾을 때 유용하다.2. BFS (너비 우선 탐색, Breadth-First Search)🔥BFS란?BFS는 먼저 입구에서 가장 가까운 길부터 확인하고, 그다음 조..
· 알고리즘
1. 세그먼트 트리란? - 목적, 내부 구조, 동작 원리목적:배열의 특정 구간에 대해 계산(예: 합계, 최소값, 최대값)을 빠르게 수행하기 위함이다.이를 위해 미리 구간별 연산 결과를 저장한다.내부 구조:리프 노드: 배열의 각 단일 원소이다.내부 노드: 자식 노드들의 값을 특정 연산(예: 덧셈, 최솟값, 최댓값)으로 결합하여 구간 전체에 대한 결과를 저장한다.동작 원리 :세그먼트 트리 구현의 원리는 분할 정복(Divide and Conquer) 이다.쉽게 말하면 미리 싹 다 계산해서 트리를 만들고 그 트리를 탐색하는 것이다.(구간 별 연산 결과를 미리 계산)성능 :2. 어디에 사용? - 백준 2042예시) 백준 2042번1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 ..
· 알고리즘
📘 이분 그래프 판별 (DFS 활용)📌 문제 설명K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.사이클이 발생하지 않으면 이분 그래프로 나눌 수 있다.🔍 이분 그래프의 성질DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 이전 노드와 같은 집합이면 이분 그래프가 아님연결된 두 노드가 서로 다른 그룹에 속해 있으면 이분 그래프 조건을 충족한다.이분 그래프는 두 개의 집합으로 나눌 수 있는 그래프다.그래프의 모든 간선이 A 그룹의 노드와 B 그룹의 노드를 연결한다.같은 색의 노드들끼리는 서로 연결되지 않고, 항상 다른 색의 노드들끼리만 연결된다.📝 예시v1 -- v2 | | v4 -- v3이 그래프도 이분 그래프이다..
· 알고리즘
kadane 알고리즘주어진 배열에서 최대 연속합을 찾아라.와 같은 문제를 DP로 O(N)의 시간복잡도로 해결한다.dp[i]는 0부터 i번째 요소까지 고려했을 때, i로 끝나는 최대 연속 부분합이다.dp[i] = max(a[i], dp[i-1] + a[i])와 같은 점화식의 DP 알고리즘이 카데인 알고리즘이다.위의 점화식을 해석하면,i로 끝나는 최대 연속 부분합 = max(현재 요소 하나의 값,i-1로 끝나는 연속 부분합 + 다음 요소를 추가)이다.그리고 dp[0]~dp[i]중에 최대를 택하면 그게 배열에서의 최대 연속 부분 합이다.어떻게 이런 아이디어를..?기존에 계산했던 걸 바탕으로 연속 부분합을 누적적으로 계산하려는 아이디어인 것이다.그런데 단순히 dp[i]를 i요소까지 고려했을 때 최대 연속 부분합..
· 알고리즘
🔎 문제 설명https://www.acmicpc.net/problem/32350몬스터들이 순서대로 배열되어 있고, 각 몬스터의 체력이 주어진다.공격을 해서 데미지(d)를 입힐 수 있다.만약 공격으로 몬스터의 체력이 0보다 적게 떨어지면, 초과 피해량(Overkill Damage)이 다음 몬스터에게 일정 비율(p)로 전달됩니다.몬스터들을 모두 처치하는데 필요한 총 공격 횟수(cnt)를 구하는 문제이다.🔧 변수 값n : 몬스터의 수d : 한 번의 공격으로 입히는 기본 데미지p : 오버킬 데미지가 다음 몬스터에게 전달되는 비율(%)m : 각 몬스터의 체력 배열rem : 마지막 공격으로 죽기 전에 남는 체력over : 오버킬 데미지🚀 풀이 과정for문으로 몬스터 배열을 순회해야 함.그리고 몬스터를 죽이기 ..
· 알고리즘
https://school.programmers.co.kr/learn/courses/30/lessons/150370?language=cpp문제 설명이 줄줄이 길게 있다.하지만 결국에 이 문제를 요약을 하면은 이런 문제다.다음과 같이 today와 terms, privacies가 주어지고privacies와 terms 더 한 거(만료일)을 today와 비교하는 문제이다.그리고 만료일 string today = "2022.05.19"; vector terms = {"A 6", "B 12", "C 3"}; vector privacies = {"2021.05.02 A", "2021.07.01 B", "2022.02.19 C", "2022.02.20 C"}; vector solution(string today,..
· 알고리즘
https://www.acmicpc.net/problem/2252⭐ 문제 요약이 문제를 읽어보고 요약하면 이런 것이다.학생들이 N명 있고 아래와 같은 정보가 M개가 주어진다.1이 2보다 키가 크다, 2가 3보다 키가 크다, ...그리고 그 M개의 조건을 위배하지 않는 순서대로 학생들을 출력하는 문제이다.답은 여러가지가 존재하고, 그 중에 하나의 답만 출력하면 된다.🪜 STEP 1이걸 단순히 아이디어 없이 정렬하려고 하면 상당히 어렵다.어떻게 정렬해야 할 지 감이 안오게 된다.단순히 이런 방식을 생각해볼 수 있기는 하다.먼저 1,2,3,4,5..., N까지 값이 있는 배열을 둔다.그리고 M개의 조건을 하나 하나 읽을 때마다 그 조건에 성립하는지 확인한다.성립하지 않으면 성립하도록 만든다.이런식으로 로직을..
· 알고리즘
다익스트라 알고리즘언제 사용?하나의 시작 노드로부터 모든 다른 노드까지의 최단경로를 찾는 알고리즘이다.(벨만포드와 같다)가중치가 0이거나 양수인 경우만 사용할 수 있다.가중치가 음수라면 사용할 수 없다.구현 방법사용 변수vertex 개수 , edge 개수, start_node 값,사용 자료구조최소거리를 담은 배열, 방문했는지 기록하는 배열, 이전 노드를 기록하는 배열(방문순서를 기록하기 위함) 인접리스트,우선순위 큐어떻게 작동?우선순위 큐에 시작 노드를 넣는다.아래를 반복한다.우선순위 큐가 비면 반복을 멈춘다.우선순위 큐에서 노드를 꺼낸다.방문한 노드면 즉시 continue한다.방문하지 않는 노드면 방문 표시를 하고, 인접노드를 전부 순회한다.매 순회마다 이를 반복한다.더 좋은 최단 경로를 찾았다면 인접..
· 알고리즘
백준 32714번 방벽 게임문제를 보면 가로 또는 세로로 연속하는 두 칸을 선택해서 방벽을 설치할 수 있다고 한다.쉽게 말해 그냥 방벽을 설치하는 것이다.세로로도 방벽을 설치할 수 있다.건덕이가 움직이는 걸 시뮬레이션으로 직접 코딩할 필요가 없다. 위치를 추적하거나 규칙을 확인할 수 없지 않기 때문이다.(다시 생각해보니 위치추적도 시뮬레이션으로 안해도 될 것 같긴 함) 규칙성만 발견하여 움직이는 횟수만 계산하면 된다.규칙성도 바로 보일 것 같이 생겨서 만만하게 봤는데 만만한 게 맞았다. 한 10분정도 걸렸다. 구구단 문제는 8분 걸렸고, 비슷한 수준의 문제 같다.그런데 처음에는 지그재그로 막게 하면 될 거라고 생각하고 1+1+(2(k-3)) + 1로 식을 세웠다. 그런데 오답이 나와서 지그재그보다 효율적..
· 알고리즘
세그먼트 트리세그먼트 트리는 배열의 데이터에 대한 구간 질의(구간합, 최대,최소, 구간곱),배열 값 업데이트를 빠르게 수행하기 위해 고안해 낸자료구조이다.세그먼트 트리는 완전 이진 트리로 구현한다.세그먼트 트리 이해하기샘플 데이터 {5, 8, 4, 3, 7, 2, 1, 6}가 있다. N = 8 (배열의 크기, 트리배열의 크기도 8이다)그리고 그 샘플 데이터로 만든 배열 위에 세그먼트 트리를 그려보았다.질의 결과 값 구하기i=1부터 시작한다고 가정했을 때, i=3~7까지의 합이 구간 질의로 주어졌다고 하자.(세그먼트 트리를 사용할 때는 i를 반드시 1부터 시작하도록 하자. 그래야 죽지 않고 오래 산다)그러면 일반적인 방식으로는 4 + 3 + 7 + 2 + 1 이런식으로 구한다.하지만, 세그먼트 트리 방식을..