알고리즘/백준 알고리즘 강의 (40) 썸네일형 리스트형 백준 알고리즘 중급 - 브루트 포스 : 재귀 (연습) - 1 주로 풀었던 문제를 다른 방법으로 푸는 식이었다. 더 빨리 풀리는 문제도 있었고, 오히려 더 느리게 풀리는 문제도 있었다. 어쨌든 재귀를 사용하면 식 자체는 간단해진다. 하지만 까딱 잘못하다가는 메모리가 오버 되거나 무한 루프에 빠지기 쉽다. 제한 조건을 잘 걸어줘야 한다. 정리 시작! - * 로또 (mid) : 앞에서 순열을 사용해서 풀었던 문제를 재귀로 풀어봤다. 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net #include using namespace std; int k, a[13],.. 백준 알고리즘 중급 - 브루트 포스 : 순열 (연습) 드디어 중급 강의 시작! 오픽의 늪에서 드디어 벗어났다. 다시 차근차근 알고리즘 공부 해보자. 처음엔 많이 헤맸는데, 요령을 알고 나니까 술술 풀렸던 파트였다. 그리고 몇가지 기억하면 좋을 꿀팁들이 있었다. 정리 잘 해뒀다가 나중에 문제 풀 때 써먹자. 정리 시작! - * 부등호 (mid) : 앞에서 풀었던 부등호 문제를 순열을 이용해 풀어보자, 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제�� www.acmicpc.net - 브루트 포스를 사용한다면, 최댓값은 9부터 제시된 부등호 개수 + 1 만큼의 수를 모두 배열해서 부등호를 성립하는 값을, 최.. 백준 알고리즘 기초 - 트리 어느새 기초 강의의 마지막 챕터다. 한달이 좀 덜 걸렸다. 여기까지만 정리하고 당분간은 오픽에만 집중하고, 시험 치고 나서 중급도 시작해야겠다. 이론적인 내용의 이해가 특히 중요했던 트리 파트였다. 정리 시작! - * 트리 : 사이클이 없는 연결 그래프. (정점 v개, 간선 v-1개) - 조상, 자손 개념은 자기 자신을 포함한다. - 이진 트리 (binary tree) : 자식을 최대 2개만 갖는 트리. 가장 많이 사용한다. - 포화 (perfect) 이진 트리 : 꽉 찬 이진트리. 높이가 h이면 노드 개수 2^h - 1 - 완전 (complete) 이진 트리 : 포화에서 가장 오른쪽에서부터 몇 개가 사라진 형태 * 트리 순회 : 프리오더, 인오더, 포스트오더 - 프리오더 : 노드 -> left -> r.. 백준 알고리즘 기초 - bfs 최대한 스스로 풀어보려고 노력했던 파트였다. bfs에 대한 감은 어느정도 왔지만, 아직 연습이 더 필요하다. 특히 덱 부분은 많이 새로웠다. 이번 기회에 잘 정리를 해놓자. 정리 시작! - * bfs : 임의의 정점에 시작해서 모든 정점을 한번씩 방문하는 것. (dfs도 마찬가지) - 너비를 우선으로 탐색하므로, 최단 거리를 구할 수 있는 알고리즘이다. - bfs로 해결할 수 있는 문제는: 최소 비용 문제, 간선의 가중치가 1, 정점과 간선의 개수가 적어야 문제 바로 풀어보자. * 숨바꼭질 (mid) : 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제다. 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 .. 백준 알고리즘 기초 - 그래프1 (도전) 푹 쉬고 나니 좀 낫다. 뭘 해도 건강이 우선이다. 다시 차근차근 해나가보자. 정리 시작. - * BFS 스페셜 저지 (mid) : 주어진 경우가 bfs 탐색이 맞는지 확인하는 문제다. 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net - 처음엔 단순하게 모든 bfs 경우를 생각했을 때 해당 경우가 나오는지 생각해서 풀어봤다. #include #include #include using namespace std; int n, cnt = 1; vector a[100000], ans; bool check[100000]; void bfs(int e) { queue q; check[e] = true; q.push(e); while (!q.. 백준 알고리즘 기초 - 그래프1 (연습) 2문제 밖에 없는 파트였다. 근데 엄청 헤맸다. 어려웠다. 뭔가 dfs, bfs 문제는 어느정도 감을 잡았다고 생각했는데 진짜 바보 같은 생각이었다 ㅋㅋ 2문제를 잘근잘근 씹어서 내껄로 한번 만들어 봐야겠다. 정리 시작! - * Two Dots (mid) : 사이클이 있는지 판별하는 문제다. 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문�� www.acmicpc.net - 여기서 말하는 사이클은 4개 이상의 서로 다르고 인접한 점의 집합을 말한다. 당연히 색은 다 같아야 한다. - 사이클을 판별하기 위해서 배열 d[i][j]를 .. 백준 알고리즘 기초 - 그래프1 (연결요소, 이분그래프, 그래프 예제) 요즘 오후 시간이 유독 힘들다.. 체력적인 문제라기보다는 멘탈의 문제인듯 하다. 좀 더 단계적인 목표를 세우고 효율적으로 움직여보자. 정리 시작! - * 연결 요소 : 연결 되지 않고 나눠진 각각의 그래프. 연결 요소의 개수는 dfs, bfs로 구할 수 있다. 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net #include #include using namespace std; int n, m; vectors[1001]; bool check[100.. 백준 알고리즘 기초 - 그래프1 (BFS, DFS) 그래프 챕터의 시작이다. BFS, DFS 가 꽤나 중요한 알고리즘이기도 하고, 그래프 문제가 어려워지면 끝도 없다는 말을 들었기에 확실하게 하고 넘어가야 할 것 같다. 정리 시작! - * 그래프 : 자료구조의 일종. 어떻게 문제 상황을 구조화 하는지가 관건이다. - 정점 (node, vertex), 간선 (edge) : 정점간의 관계 - 경로 (path), 사이클 / 단순 경로, 단순 사이클 : 같은 정점을 두 번 이상 방문하지 않은 것 - 차수 : 정점과 연결되어 있는 간선의 개수 * 그래프의 표현 - 인접 행렬 : V * V 크기의 이차원 배열 이용. 간선 있으면 1, 없으면 0. - 인접 리스트 : A[i]에 i와 연결된 정점을 리스트로 포함하고 있음. 크기를 동적으로 변경할 수 있어야 함. 인접 .. 이전 1 2 3 4 5 다음
