개발세리의 성장기🌿

안녕하세요 :) 오늘은 그래프라는 자료구조를 표현하는 방법에 대해 알아보고, 그래프 탐색 알고리즘인 DFS, BFS의 구현 방법에 대해 알아보겠습니다. 그럼 오늘도 화이팅 입니다🌿 그래프란 ? 그래프란 정점과 간선으로 정보를 표현하는 자료구조입니다. 보통 알고리즘 문제에서 다루는 그래프의 종류는 크게 방향의 유무, 가중치의 유무, 사이클의 유무로 분류 됩니다. 그래프의 차수란 정점과 연결되어있는 간선의 개수를 의미합니다. (코드상으로) 그래프를 저장하는 방법엔 크게 3가지가 있습니다. 인접 행렬 인접 리스트 간선 리스트 그래프를 저장한다는 것은 어떤 정점 x와 연결된 간선을 효율적으로 찾을 수 있게, 저장하는 방법을 의미합니다. 정점의 개수 → V 그래프 → A[][] 특정 간선의 각 정점 → i, j ..

안녕하세요 :) 오늘은 순열을 사용하는 BF 알고리즘에 대해 알아보겠습니다. 줄서는 방법, 특정 작업 순서의 모든 경우의 수 등, 순서가 중요한 작업에 있어 BF + 순열을 사용합니다. 그럼 오늘도 화이팅 입니다🌿 순열이란 ? 순열이란 1~N까지 이루어진 수열을 의미합니다. 따라서, 크기가 N인 순열은 총 N!개 존재하게 됩니다. 어떤 수열의 다음 수열을 알아내는 연산의 시간 복잡도는 O(N)이 됩니다. BF에서 순열은 순서가 중요할 때, 사용되곤 합니다. (ex. 과일을 먹는 순서 ) 다음 순열 찾기 알고리즘 시간 복잡도 A[0] ~ A[N-1] 에서, A[i-1] > A[i] 을 만족하지 않는 지점 찾기 -> 조건이 만족하지 않는 지점 A[i-1] 🕖 최대 N 번 실행되므로, O(N) A[i] ~ A..

안녕하세요 ! 이번에 알아볼 것은 순한맛일땐 온순하지만, 매운맛일땐 정말 극악의 난이도를 자랑하는 brute force입니다. brute force는 가능한 모든 경우의 수에 대해 직접 실행, 연산 해보는 알고리즘입니다. 이 글에선 brute force를 공부하려는 사람이 알아두면 좋은 것들을 간단히 정리해보았습니다. 그럼 오늘도 화이팅 입니다🌿 brute force 알고리즘의 접근 방식 문제의 가능한 경우의 수를 계산해봅니다. 브루트 포스 알고리즘은 시도해봐야하는 경우의 수가 중요합니다. 1초 -> 1억 -10억번의 연산 -> 몇 백만 - 몇 천만의 경우의 수 즉, 1초라는 제한시간이 있다면, BF로는 몇 백- 몇 천만의 경우의 수에 대해 해결할 수 있다고 생각하시면 좋습니다. 위 경우의 수에 대한 가..

1. 주어진 범위에 속한 소수를 모두 구할 때: 에라토스테네스의 체 for(int i = 2 ; i

그리디를 공부하면서 1. 극단적인 기준으로 접근하는 그리디 알고리즘은 정렬과 함께 쓰이는 경우가 많다. 2. 극단적인 기준으로 당장 눈 앞에 보이는 것에 대해서만 판단하므로, 눈 앞에 보이는 순서가 중요하다. 즉 정렬이 중요한데, 정렬을 여러 기준으로 여러 번 해서, 정확도를 높여주어야한다. ex> boj1931에서의 compare1과 compare2는 아래 테스트 케이스를 고려한 것이다. 3 1 2 3 3 2 3 3. 예외 케이스에 대해 이해하고 있어야하므로, 문제를 존나 열심히 꼼꼼히 읽어야한다. 4. 보통 문제에 최댓값, 최솟값, 최대 길이, 최대 가능 인원&수업&회의 등등의 키워드가 출현한다.

*그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 == 그래프의 탐색 알고리즘 ex> DFS, BFS *여기서 '탐색'의 의미는 find가 아니라 search에 가깝다. 즉, 특정 정점을 찾거나, 특정 경로를 찾는 것이 아니라, "모든 정점들을 정해진 순서로 둘러보는 것"에 가깝다는 의미이다. 1. DFS를 구현할 때의 고려사항 (선택지) 그래프의 표현 방법: 인접 행렬 or 인접 리스트 or 좌표 DFS 구현 방법: 스택 or 재귀 2. 구현 방법

*그래프를 표현(구현)한다 == 모든 정점을 기록하고, 두 정점간의 관계(간선)을 기록하여 저장한다. *V는 정점을 의미한다. 1. 인접 행렬 표현 -구현 방법 n개의 V에 대하여, n*n 이차원 배열에 두 정점간의 관계(간선)를 표현한다. 배열의 인덱스엔 두 정점이 들어가고, 배열의 내용엔 간선에 대한 정보가 들어간다. //1. 동적으로 인접 행렬을 구현할 때 (메모리 제약이 있을 때) //n은 정점의 개수 int n; scanf("%d", &n); //a는 간선을 인접 행렬 방법으로 표현하기 위한 이차원 배열 int** a; //정점의 이름대로 배열에 접근하기 위해서 n+1개의 공간을 할당 받는다. a = (int**)malloc(sizeof(int*) * (n + 1)); for (int i = 0..