개발세리의 성장기🌿

안녕하세요 :) 오늘은 그래프라는 자료구조를 표현하는 방법에 대해 알아보고, 그래프 탐색 알고리즘인 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. 유형 쉬운 구현 - 자료구조 - 어려운 구현 으로 정리가 되는 듯하다. 난이도는 실버3-골드4 정도로 예상된다! 문제 자체 난이도로 접근하자면 풀어낼 수 있는 난이도였지만, 모든 시험이 그러하듯이 시간 내에 푸는 것이 실력이자 결과인지이라.. 나의 한계를 다시 되짚게 되었다 :) (솔직히 너무 긴장 안했다 너) #2. 구현 요즘 코테를 경험하는 사람들은 공감할테지만, "구현"이 정말 까다롭게 다가온다. 특정한 알고리즘 지식을 요구하는걸까 고민하게 하다가도, 결국 정답은 노가다로 끈기있게, 차분하게 문제를 구현해내는 것을 요구하는 경우가 있기 때문이다. 즉 시험 시간 내의 차분함과 꼼꼼함이 먹고 들어가는 유형이라는 생각이 든다. 이건 지난 카카오 코테 볼 때, 문자열 필터링 문제를 풀면서도 느낀 부..

0. set 헤더 #include 1. set 특징 -중복되는 값을 넣어도 안들어감, 수학적 집합의 개념임 -자동으로 작은 수 부터 정렬됨 2. set 사용법 #incldue //헤더 set s; //set 선언 s.insert(10); //삽입 현재 set: 10 s.insert(2); //삽입 현재 set: 2, 10 set::iterator it; //set형 반복자 (포인터 같은거임) for (it = s.begin(); it != s.end(); it++) { //set 출력하려면 반복자 사용해야함 cout > m; int a, b; for (int i = 0; i> a >> b; if (a == 1) { //상근이랑 친구인 관계 f.insert(b); invite..

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

0. #include 1. 사용 문법 2. 사용자 정의 3. 두 개의 정렬 기준을 정의 4. vector p; 자료형 정렬 예제

0. #include //vector #include //pair #include //sorting 1. 선언 vector > meeting; 2. 할당 meeting.resize(N); for (int i = 0; i < N; i++) { meeting[i] = make_pair(0, 1); } 3. 사용 meeing[i] == meeting[i].first == 0 meeting[i].second == 1 4. 정렬 이후에 링킹