PROGRAMMING/알고리즘
-
(백준 11505번 구간 곱 구하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 2PROGRAMMING/알고리즘 2024. 5. 13. 21:45
세그먼트 트리! 이제 쬐금 익숙해진 것 같다. 2042번과 매우 비슷하지만, 아직 세그먼트 트리가 익숙치 않아 푸는데 매우 매우 오래 걸렸다..^^ 2042번 풀이는 아래에...!https://jjo-mathstory.tistory.com/entry/%EB%B0%B1%EC%A4%80-2042%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-C-%EB%9D%BC%EC%9D%B4%EB%8B%98-%EB%B8%94%EB%A1%9C%EA%B7%B8-%EB%8C%80%ED%9A%8C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%94%B0%EB%9D%BC%EC%9E%A1%EA%B8%B0-12-SegmentTree-1 ..
-
(백준 2042번 구간 합 구하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 1PROGRAMMING/알고리즘 2024. 5. 12. 21:13
나의 스승 라이님 블로그를 보고 오늘은 세그먼트 트리를 배워보았다. https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220791986409&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 세그먼트 트리(Segment Tree) (수정: 2019-02-12)아마 트리 파트에서 마지막이 될 글입니다. 상당히 재미있는 자료구조입니다. 그 이름하여 세그먼트 트리(s...blog.naver.com 풀이는 라이님 깃허브에서 가져옴!!https://github.com/kks227/BOJ/blob/master/2000/2042.cpp BOJ/2000/2042.cpp ..
-
(백준 1976번 여행 가자 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) Union Find 2PROGRAMMING/알고리즘 2024. 5. 9. 20:07
(노느라) 바쁘다는 핑계로 공부를 소홀히 하는 것 같아 마음이 불편하다.이제는 진짜 매일 1백준 해야겠다!!! 백준 1976번https://www.acmicpc.net/problem/1976 이 문제는 Union Find 라고 해서 봤는데 처음에는 뭔 소리인가 했다. dfs로 풀어야 하나 생각하고 있었는데!Union Find로 아이디어를 틀었다. 이디야에서 샤인히비스커스를 마시면서 깨달은 사실 : 사실 어떤 도시를 몇 번 가는지는 중요하지 않다! 연결된 도시는 무조건 방문이 가능하다. 이 말인 즉, 여행을 가고지 하는 도시들이 하나의 connected graph의 node들이기만 하면 된다는 의미!그리고 하나의 connected graph에 속하는지 아닌지는 root node가 동일한지 아닌지만 확인하..
-
(백준 1717번 집합의 표현 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) Union FindPROGRAMMING/알고리즘 2024. 5. 2. 08:39
Union Find 알고리즘으로 빠르게 넘어가서 하나 풀어봤다.늘 그렇듯 라이님 블로그를 보면서 이해했다. https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220791837179&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 백준 1717번https://www.acmicpc.net/problem/1717#define _CRT_SECURE_NO_WARNINGS#include #include using namespace std;constexpr int MAX_N = 1000000 + 1;int p[MAX_N];int find(int n) { // ★오타 ..
-
(백준 1351번 무한수열 C++) 라이님 블로그 대회 알고리즘 따라잡기 11) BSTPROGRAMMING/알고리즘 2024. 5. 2. 07:50
어제 풀다가 삽질한 문제 1351번!역시 머리가 맑은 아침에는 잘 풀린다^__^ 백준 1351번 무한수열https://www.acmicpc.net/problem/1351 문제를 풀다가 처음에는 메모리 초과 -> 틀렸습니다 이슈로 고생 좀 했는데, 1. 메모리 초과가 된 이유 : vector를 사용했기 때문 → map을 사용해야 한다!!2. 틀렸습니다가 계속 뜬 이유 : long long...^^ vector가 아닌 map을 사용해서 문제를 풀어야 하는 이유는 아래 답글을 참고하세요↓https://www.acmicpc.net/board/view/137948#include #include using namespace std;map m;long long N, P, Q;long long dp(long long ..
-
(백준 1269번 대칭 차집합 C++) 라이님 블로그 대회 알고리즘 따라잡기 11) BSTPROGRAMMING/알고리즘 2024. 5. 1. 21:42
Tree로 멘탈이 바사삭해서 잠시 휴식을 찾아 이 문제도 왔다..@_@ BST(Binary Search Tree)에 대한 설명은 아래 라이님 블로그를 따라가면 됩니다..🌟https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220789373847&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 이진 검색 트리(Binary Search Tree)저번 글에서 이진 트리를 조금 비중있게 다루었는데, 이진 트리는 자료구조에서 굉장히 중요합니다. 이진 ...blog.naver.com그 전에 알아두면 좋을 C++로 합집합, 차집합 구현하는 방법을 소개하고자 한다.ht..
-
(백준 1967번 트리 지름 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Tree 3 with gptPROGRAMMING/알고리즘 2024. 5. 1. 15:00
풀이가 감이 오질 않아 gpt에게 물어보고 나름 내 스타일대로 풀어보았다. 백준 1967번https://www.acmicpc.net/problem/1967 트리에서 가장 긴 거리를 구하는 문제인데, gpt는 2번의 dfs방법을 사용해서 풀었다.보고나니 당연하게 느껴졌지만, 처음에는 생각하지 못했다..ㅠ 우선 가장 긴 거리는 당연히! leaf에서 출발해서 leaf에서 끝날 것이다..!그렇다면 우선 root에서 시작에서 가장 멀리 있는 leaf를 찾은 다음( = farthestNode)farthestNode에서 다시 dfs를 통해 가장 멀리 있는 leaf를 찾으면 된다. 여기서 신박했던 점은 farthestNode와 maxDistance를 찾는 방법이다.dfs 매 실행마다 farthestNode와 max..
-
(백준 4803번 트리 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Tree 2 with gptPROGRAMMING/알고리즘 2024. 5. 1. 14:37
오늘은 gpt 선생님에게 한 수 배웠다. 백준 4803번https://www.acmicpc.net/problem/4803 일단 gpt가 풀어준 풀이는 아래와 같다. § dfs(int node, int parent)를 정의해줘서 부모가 아닌데 방문된 노드를 만나면 순환이 있다고 판단§ 처음 시작은 dfs(node, -1)로 시작#include #include #include using namespace std;int n, m;vector> graph;vector visited;// DFS 함수, 순환이 있는지 체크bool dfs(int node, int parent) { visited[node] = true; for (int next : graph[node]) { if (!visi..