이 문제는 트리의 깊이를 이용해서 풀 수 있다 제일낮은 깊이부터 깊이0까지 깊이를 한 단계씩 올라오며 정점 N개를 봐주면 된다! 부모를 미리 찾아주고 부모가 양인지 늑대인지만 확인하면 현재층에서 다음층의 결과를 쫙 구할 수 있다! 다 풀고 다른사람의 풀이를 보니 위상정렬로도 풀 수 있다 위상정렬은 생각못했는데 한번 다시 풀어봐야겠따 위상정렬로 + 위에서 아래로 내려오면서 한번에 구할 수 있는데 제일 한심하게 제일 열심히 위아래위아래 했다 거의 EXID 굿;; 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48..
이 문제는 이분탐색 or 시물레이션으로 풀 수있는것같다 주구장창 시물레이션 풀다가 계속 틀렸다 최적화의 계산을 정~~~~말 못해서 그런거같다 이분탐색도 생각 못했다.. 최소의 최대체력인데..!!! 문제에 써있는데..!! 최대체력을 mid로 두고 이분탐색을 해서 그 체력이 가능한지 돌려보자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include using namespace std; #define ll long long ll n,k; vector vt; bool solve(ll mid){..
하반기 코테를 위해 백준문제를 오랜만에 풀어봤따..!! 골고루 틀리면서 정신을 차리고 있다 이 문제는 dfs로 가장 1~n까지 간다고 생각하면 된다 대신 check[현재][이전에 고른 수]를 체크해 가며 가야한다 ans배열을 만들고 내가 수를 고르고 다음수로 넘어갈 때 현재의 수를 넣어주면 탐색이 끝나고 그대로 출력하면 된다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include using namespace std; int n; int arr[1111][11]; bool check[11..
이 문제는 트라이를 이용하면 풀 수 있다 여태까지 항상 동적 트라이만 짜봤는데 오늘 정적 트라이을 배워서 사용해봤다 먼저 문자열배열 s와 trie배열 그리고 문자열의 끝남을 알리는 fin을 잡자 trie가 [10000*10][10] 크기인 이유는 총 10000*10개의 정점이 나올 수 있고 각 정점은 0~9까지 10개의 숫자를 가질 수 있기 때문이다! 총 2가지의함수 insert, find를 구현했다! insert에서는 문자열을 trie자료구조에 넣는다 이 때 문자열의 문자 하나씩을 보며 끝난다면 fin[현재정점]을 true로 만들어준다 그럼 우리는 현재정점은 끝나는 지점이라는 것을 알 수 있다 trie배열에는 trie[현재정점][현재문자] = cnt로 인덱스를 매긴다 그럼 문자열을 하나하나 찾을때 정점..
수 정렬하기2 문제는 사실 STL 정렬로 쉽게 풀 수 있다 이번에는 삼성 B형 준비할 겸 직접 힙소트로 구현해서 풀어보았다 혹시 틀렸으면 댓글좀..!!! 부탁합니다 총 3개의 함수 swap,insert,sort 함수를 구현했다 swap은 말그대로 a,b의 수를 바꿔주는 함수다 insert는 수를 heap에 넣는 함수로 넣고나서 내가 루트가 아니라면 항상 부모와 크기를 비교해본다. 그래서 만약 내가 더 크다면 체인지! swap을 못할때까지 죽쭉 올라가보자!! sort는 pop하는걸 n번 연속으로 한다고 생각하면 쉽다 추가적인 배열을 만들필요가 없어서 메모리에 좋다..! 먼저 최대힙이므로 루트에는 가장 큰 수가 있다 이 수를 가장 마지막 last수와 바꾸준다 그럼 가장 뒤에는 가장 큰 수가 위치한다 이제 루..
그리디 알고리즘으로 그냥 그대로 앞부터 덮어가면 된다 벡터로 구현하다가 구현 오류가 많이나서 틀렸다 변수를 더 잡더라도 정확하게 구현을 하자! 마지막으로 덮은 곳을 last에 두고 last와 다음 웅덩이의 시작지점을 비교했다 만약 last가 더 크다면 웅덩이의 시작지점을 last+1로 바꾼다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include #include using namespace std; int n,l,ans; vector vt; bool cmp (const pair &a, const pair&b){ if(a.first==b.first) return a.second>b.sec..
그리디문제인제 복잡하게 생각해서 많이 틀렸다 나의 틀린 접근법은 각 날 마다 최대값을 두고 나머지 날 들은 pq 에 넣었다 그리고 각날의 최대값과 나머지날들을 비교해서 큰값을 넣었다 많은 것들을 고려했었는데 그럴 필요가 없었다 데드라인 순으로 정렬하고 내가 보고있는 데드라인까지 중 큰 값들만 남기고 버리면 된다 pq를 이용하면 쉽게 풀 수 있다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include #include #include using namespace std; pair arr[200200]; int n; int main(){ //freopen("input.txt","r",stdin); scanf(" %d",&n); for(in..
그리디 문제이다. 우선순위 큐를 이용해 쉽게 풀 수 있다 최소값 2개를 계속 더해가면 된다 이 때 pq는 최대값을 저장하므로 -를 붙여서 저장해 최소값을 계속 찾아주자 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include using namespace std; #define ll long long int n,m; priority_queue pq; int main(){ //freopen("input.txt","r",stdin); scanf(" %d %d",&n,&m); for(int i=0;i
다익스트라를 이용하며 최단거리로 지나가는 경로를 저장해 매번 확인했다 https://sejinik.tistory.com/131와 비슷한 방법이다! 사실 이렇게 풀면 되긴하지만 시간이 조금 오래걸린다 다른 사람들 풀이를 보니 여러가지 최적화가 있는 것 같다 내가 푼 방법은 Passed라는 배열에 지나가는 경로를 저장하고 매번 다익스트라를 돌고 확인하는 하라는대로 하는 방법이다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64..
정말 직관적으로 문제에서 하라는대로 풀었다 먼저 최단거리를 찾아보다 그리고 이 때 내가 최단거리를 가는 모든 경우를 pre라는 벡터에 저장한다 그리고 최단거리를 구한 후 거꾸로 목적지에서부터 타고오며 check set에 넣는다 이건 간선을 제거하는 과정이라고 보면 편하다 그리고 다시 그래프를 그려서 다익스트라를 돌리면 최단거리를 제외한 2번째 최단거리가 나오게 된다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 6..