알고리즘/BOJ 썸네일형 리스트형 1976번 1976번 - 여행 가자 이 문제를 나는 처음에 연결요소의 갯수를 이용해서 문제를 풀었다. 도시들이 연결되어 있기만 한다면, 어떤 경로를 지나던 갈 수 있기 때문이다. 그리고 지금은 disjoint-set 을 배우고 있기 때문에 그 방식을 이용해서 풀어보았다. 하나의 트리 안에 있기 위해서는 각 도시들의 find 값, 즉 루트 노드가 같아야 한다는 점을 이용했다. 주의할 점 --> 나는 처음에 부모노드를 자기 자신으로 초기화 하는 것을 빼먹어서 처음에 문제를 틀림. 고칠 것 --> 처음에 나는 2중 for문에서 예를 들어 1은 0을 부모로, 0은 1을 부모로 해서 , 사이클이 생겨서 부모노드를 못찾는것이 아닌가 혼자 고민했는데, merge 함수에서 이미 부모가 같을 때, 다를 때를 처리해주기 때문에 문제.. 더보기 1717번 1717번 - 집합의 표현 union- find 를 통해서 문제를 해결했다. union을 할 때는 경로의 압축을 해주는 것이 시간초과를 해결하는데 주요했다. 그리고 이 문제의 경우, 입력,출력이 많기 떄문에 cin, cout 대신 printf,scanf 를 써줘야 했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include#include using namespace std;int n, m;vector p; int find(int x){ if (x == p[x]) { return x; } return p[x] =.. 더보기 3015번 3015번 - 오아시스 재결합 https://www.slideshare.net/Baekjoon/baekjoon-online-judge-3015 https://blog.naver.com/malmstee/220990386293 ↑↑↑ 문제를 푸는데 참고한 설명들... 이 문제 푸는데 정말 오랜시간이 걸렸다... 우선 핵심은 뒤에서 앞을 본다는 방식으로 생각해야 한다는 점이었다. 그리고 이 문제에서 가장 핵심은 stack에 같은 키를 가진 사람이 연속으로 서있을 때이다. 나는 이를 map 을 이용해서 구현하였다.. 같은 키를 가진 사람이 연속으로 몇명이 세워져있는지를 cnt[ 키 ] = 몇명 으로 계산하였고, 중간에 더 큰놈이 서 있는 경우는 다시 초기화해주었다.. 나중에 시간이 지나서 다시 풀어도 그때 또 .. 더보기 6549번 6549번 - 히스토그램에서 가장 큰 직사각형 이 문제는 종만북에서 분할정복, 스택을 이용한 문제풀이가 나와있는데, 나는 스택을 이용해서 문제를 풀어보았다. 접근법을 보고 이해하면서 문제를 풀었다. 어떻게 이런방법을 생각해서 푸는지, 아직 나는 저런 생각을 못하겠다. 다음에는 분할정복 방법으로 풀어봐야겠다.. 일단 이 문제는 x라는 높이의 직사각형에서 왼쪽으로 최대, 오른쪽으로 최대를 구해서 직사각형의 최대값을 구하는 방법이다. 어떤 사각형에서 자신보다 높이가 낮으면, 왼쪽,오른쪽으로 확장해갈 수 없다는 점을 이용했다. 따라서 그때, 직사각형의 최대값을 구하고면서 계속해서 스택에 최대값이 계산되지 않은 직사각형을 쌓게 된다. 따라서 스택에는 점점 커지는 직사각형이 쌓이게 된다, 마치 오름차순으로 쌓이듯 .. 더보기 1182번 1182번 - 부분 집합의 합 1. 재귀함수를 이용해서 풀이 2. 비트마스크를 이용해서 풀이 for문에서는 0인 공집합을 빼고 모든 부분집합을 도는 조건문이다. 아래의 for문을 for (int subset = set; subset; subset = set & (subset - 1)) 아래처럼 바꿔도 동일하다. for(int subset=1;subset> S; for (int i = 0; i > D[i]; } dfs(0, 0); if (S == 0) { ans -= 1; } cout S; v.resize(N); for (int i = 0; i > v[i]; } int set = (1 더보기 10974번 10974번 - 모든 순열 모든 순열을 구하는 문제인데, 사전식으로 출력하라고 했으니, next_permutation 을 쓰면 된다. ( 10972번) 단 시간 초과 문제로 cin,cout 대신 printf 를 사용해야한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include#includeusing namespace std; bool next(vector &v){ int inc = -1; int dec = -1; for (int i = 0; i 더보기 10973번 10973번 - 이전 순열 10972 번과 같은 방식으로 푼다. 다만 이전 순열이기 때문에 모든 걸 반대로 해줘야한다. 이전 순열의 경우는 내림차순일 경우 정렬할 구간, 오름차순일 경우 정렬된 구간이라고 생각하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include#includeusing namespace std;void prev(vector &v){ int increase = -1; int decrease = -1; //변곡점이 아닌 내림차순의 끝 구하기 for (int i = 0; i v[i + 1]) { decr.. 더보기 10972번 10972번 - 다음 순열 이 문제는 오름 차순과 내림차순을 잘 이용해야 풀 수 있었다. 일단 사전순으로 정렬된 가장 작은 순서는 오름차순이 된다. 그리고 순열의 가장 마지막 번호는 내림 차순이 된다. 예를 들어 1 2 3 4 는 가장 첫수는 오름차순으로 정렬된 상태이고 마지막 수 4 3 2 1 은 내림차순으로 정렬된 상태이다. 그리고 이 다음 순열은 1 2 4 3 이 된다. 이때, 오름차순이었던 수에서 내림차순이 발생한다. 즉 나는 다음순열을 구할 때의 핵심은 오름 차순은 정렬 할 구간, 내림차순은 앞으로 정렬 된 구간이라고 생각하고 풀었다. 7 2 4 6 5 3 1 이라는 순열이 있다고 해보면, 7 2 내림차순, 2 4 6 오름차순, 6 5 3 1 내림차순이 된다. 따라서 오름차순은 정리를 해야하기 .. 더보기 이전 1 ··· 25 26 27 28 29 30 31 ··· 40 다음