백준 사이트 코딩 문제/그 외 문제 (11) 썸네일형 리스트형 백준 9663번: N-Queen (C++) 문제 링크 : www.acmicpc.net/problem/9663 단순 백트래킹 문제다. 그냥 무작정 다 배치한 다음 확인을 하면 n^n이라는 어마어마한 시간복잡도가 나오게 된다. 결국 백트래킹을 사용해야한다. 1. 한 줄씩 queen을 놓아본다. 2. queen을 놓을 수 없는 상황이오면 바로 돌아간다.(백트래킹) #include #include using namespace std; vector queen; int n; int result = 0; bool can_exist(int x,int y) //해당 위체에 queen놓을 수 있는지 { for (int i = 0; i < queen.size(); i++) { int x2 = queen[i].first; int y2 = queen[i].second;.. 백준 1753번: 최단경로 (C++) 문제 링크 : www.acmicpc.net/problem/1753 단순한 다익스트라 알고리즘 문제다. 내 블로그에 다익스트라 알고리즘에 대해 다 설명해 놓았다. 다익스트라 알고리즘 : wlshddlek.tistory.com/36?category=887632 #include #include #include using namespace std; vector a[20002]; int d[20002]; int INF = 987654321; void dijkstra(int start) { fill(&d[0], &d[20001], INF); priority_queue q; q.push(make_pair(0,start)); d[start] = 0; while (!q.empty()) { int node = q.top(.. 백준 1717번: 집합의 표현 (C++) 문제 링크 : www.acmicpc.net/problem/1717 응용없는 단순한 유니온 파인드(disjoint set)알고리즘이다. 1-1. type이 0이면 두 노드들의 root를 합친다. -> d배열에 각 노드들의 부모를 가리키도록 저장한다.(재귀로 끝까지 가보면 root가 나오게 됨) 1-2. type이 1이면 두 노드의 집합 여부를 출력한다. (root노드가 같으면 결국 같은 집합임) #include using namespace std; int d[1000002]; int find_root(int a) //해당 집합의 root 찾아서 반환 { if (d[a] == a)return a; return find_root(d[a]); } void make_union(int a, int b) //두 집합.. 백준 1167번: 트리의 지름 (C++) 문제 링크 : www.acmicpc.net/problem/1167 tip) 임의의 한 점에서 제일 먼 점은 반드시 지름의 양 끝 점 중에 하나라는 사실만 생각해내면 된다. 1. 임의의 한 점에서 제일 먼 점을 찾는다. (지름의 끝 점 중 하나를 찾는다) 2. 그 점으로 부터 제일 먼 점까지의 거리를 구한다 -> 제일 먼 점을 찾는건 bfs 나 dfs로 구한다. #include #include #include #include using namespace std; vector a[100002]; bool check[100002]; int max_cost = 0; int result = 0; int find_corner(int start) { queue q; q.push(make_pair(start, 0));.. 백준 12865번: 평범한 배낭 (C++) 문제 링크 : www.acmicpc.net/problem/12865 다이나믹 프로그래밍 문제이다. (knapsack 문제) 1. 특정 아이템을 넣을지 말지의 경우를 모두 저장하며 구해나간다. - 아이템 마다 결정할 때 가방의 무게가 w ~ k일 때의 모든 경우를 저장하여야 한다. (w미만은 어차피 넣을 수 없으니 고려할 필요가 없음) 2. 마지막 아이템까지 다이나믹 프로그래밍을 진행하면 결국 가방 무게가 k일때의 d[k]값이 정답이다. - knapsack문제를 2차원 배열에 저장하며 계산한다면 좀 더 이해하기 직관적일 것이다. 하지만 메모리를 아끼기 위해 1차원 배열로 알고리즘을 구현하였다. - 1차원 배열을 이용한다면 배열을 계속 갱신할 때 뒤에서 부터 갱신하여야 한다. 뒤에서 부터 갱신하여야 그 전의.. 백준 7569번: 토마토 (C++) 문제 링크 : www.acmicpc.net/problem/7569 배열을 전부 탐색해나가며 토마토를 익게 하면 당연히 시간초과가 난다. 이 문제는 bfs로 간단히 해결할 수 있다. bfs 알고리즘 : wlshddlek.tistory.com/8?category=883327 1. bfs로 토마토를 익게하며 제일 늦게까지 탐색되는 토마토가 몇일만에 탐색되었는지 구한다. 2. 토마토다 다익었으면 제일 늦게 익은 토마토 day를 반환, 안익은게 있으면 -1반환 *bfs로 탐색을 할 때 queue안의 각 점에서 모두 탐색을 한다는 것을 이용한다 -> 시작점을 여러개 넣어도 각 시작점에서 모두 탐색해 나감. #include #include using namespace std; class ins { public: in.. 백준 1766번: 문제집 (C++) 문제 링크 : www.acmicpc.net/problem/1766 위상정렬 문제이다. 위상정렬 알고리즘 : wlshddlek.tistory.com/39?category=887828 위상정렬을 이용해야 한다. 위상정렬을 이용할 때 일반 큐가 아니라 우선순위 큐를 사용하면 실시간으로 탐색할 수 있는 것 중에 작은거 부터 탐색할 수 있다. #include #include #include using namespace std; int n, m; vector a[32002]; int indegree[32002]; void topology() //우선순위큐를 이용한 위상 정렬 { priority_queue pq; //실시간으로 선택할 수 있는 것 중 가장 작은거 선택 위함 for (int i = 1; i > m; f.. 백준 1005번: ACM Craft (C++) 문제 링크 : www.acmicpc.net/problem/1005 위상정렬과 dp를 이용한 문제이다. 위상정렬 알고리즘 : wlshddlek.tistory.com/39?category=887828 1. 위상정렬 알고리즘으로 순서대로 건물을 짓는다. 1-1. 건물을 탐색할 때 마다 더 오래 걸리는 시간으로 갱신해준다. #include #include #include using namespace std; int time[1002]; vector a[1002]; int indegree[1002];// int d[1002];// int n,w; void topology() { queue q; for (int i = 1; i > test; for (int t = 0; t < test; t++) { int k; c.. 백준 2776번: 암기왕 (C++) 문제 링크 : www.acmicpc.net/problem/2776 문제 자체는 간단한 문제이지만 조금 문제점이 있다. nlogn 복잡도로만 풀면 되는 문제이기에 set을 이용하는 방식과 이분탐색을 이용하는 방식 둘다 통과해야하지만 set으로 풀면 통과가 되지 않는다.(set 자체가 느리기 때문) 문제를 읽어보면 정수의 개수만 1000000개이다. 이것을 그냥 배열에 넣어서 순차 탐색으로 수를 찾는다면 1000000*1000000수준의 복잡도가 나온다. 그러므로 방법은 set을 이용하는 방법과, 이분 탐색을 이용하는 방법이 있다. -set을 이용하는경우 -> 균형 이진 트리 구조임으로 해당 값을 찾는데 logn수준의 복잡도이다. -이분탐색을 이용하는 경우 -> 역시 분할 정복임으로 logn수준의 복잡도이다.. 백준 1541번: 잃어버린 괄호 (C++) 문제 링크 : https://www.acmicpc.net/problem/1541 너무 간단한 문자열 문제이다. 1. 수를 최소로 만드려면 '-'로 최대한 많은 수를 묶어야 한다는 것을 알 수 있다. 2. '-'가 나오기 전까지는 '-'로 묶을 수가 없으니 당연히 더하는 방법밖에는 없다. 결국 '-'가 나오기 전까지는 모두 더해준 다. 3. '-'나온 후에는 모두 빼면 된다는 것을 쉽게 알 수 있다. '-'가 한번이라도 나온 후에는 모두 음수로 만들 수 있다. ex) 1+2-3+4+5+6+7 -> 1+2-(3+4+5+6+7) ex) 1+2-3+4+5-6+7 -> 1+2-(3+4+5)-(6+7) #include #include using namespace std; int main() { ios_base::s.. 이전 1 2 다음