본문 바로가기

전체 글23

백준 16724번 | 피리 부는 사나이 (C++ 풀이) 문제 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 풀이 사용 알고리즘 : Union-Find or DFS 문제를 잘 해석해 보면, SAFE-ZONE의 최소 개수는 결국 그래프의 컴포넌트 개수와 같다는 점을 이용해서 풀 수 있습니다. 단, 사이클이 존재하는 단방향 그래프이기 때문에 추가적인 생각이 필요했던 문제였습니다. 컴포넌트의 개수를 구하는 풀이는 Union-Find 나 DFS 정도가 있을 것 같고, 이.. 2023. 1. 25.
우아한테크코스 5기 지원 후기 + 최종 합격(백엔드) 우아한테크코스 5기 최종 합격(백엔드) 안녕하세요. 이번 글은 우아한테크코스 5기 지원 후기에 대한 글입니다. 12월 28일 오후 2시 59분쯤에 메일로 최종 합격 안내를 받았습니다! 정말 기쁘네요. 지원 후기를 쓸지 말지 고민을 했지만, 다행히도 결과가 좋았으니 다음 기수에 지원하실 분들에게 도움이 될 수 있도록 저의 경험을 공유하고자 합니다. 서류 지원 저는 우아한테크코스에 지원해야겠다고 마음먹은 때가 서류 마감 3일 전쯤이었습니다. 당시의 저는 군인 신분이었고, 일과가 끝난 말년 포지션에 있었어서 슬슬 전역 후에 무엇을 할지에 대해 고민하던 시기였습니다. 평소와 다름없이 사지방에서 알고리즘 공부나 하면서 백준을 풀고 있던 찰나, 문득 제 머리속에서 생각 하나가 스쳐 지나갔는데, "개발 공부는 언제 .. 2022. 12. 31.
백준 16946번 | 벽 부수고 이동하기 4 (C++ 풀이) 문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 사용 알고리즘 : DFS 시간 복잡도 : O(N^2) 문제의 해석은 어렵지 않으나, 시간 복잡도를 잘 생각해보며 풀어야합니다. Naive한 풀이는 이렇습니다.모든 벽인 칸에 대해서 BFS를 돌려 이동할 수 있는 칸의 개수를 구해주면 됩니다. 하지만 시간 복잡도가 너무 크죠.단순히 BFS 한 번 돌리는 데 발생하는 시간은 O(N^2)이 될 겁니다. 여기서 문제는 매 .. 2022. 10. 25.
오일러 경로 테크닉(Euler Tour Technique) 오일러 경로 테크닉 (Euler Tour Technique) ETT라고도 불리는 이 테크닉은 DFS를 이용한 트리 관련 테크닉입니다. 구체적으로는, 어떤 트리가 있을 때, 해당 트리에 속한 노드 N과, 노드 N을 루트로 가지는 서브트리에 속한 모든 노드들을 하나의 연속된 구간으로 표현할 필요가 있을 때 사용됩니다. 음, 이를 좀 다르게 말해보면, 일반적인 트리를 세그먼트 트리로 변환시킬 때 필요한 테크닉입니다. 방법에 대해서는 이 글에서 설명할 예정이지만, 결론부터 말하자면, 트리의 각 노드들에 구간 [DFS 함수가 시작된 시점, DFS 함수가 종료된 시점]을 부여해주면 됩니다. 이런 모양의 트리가 있습니다. 이제 이 트리에 대해서 오일러 경로 테크닉을 사용해볼텐데, 그전에 먼저 트리의 순회 방법부터 정.. 2022. 10. 12.
ㅇㅅㅇ ㅡㅅㅡ myCPP #include #define X first #define Y second using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const ll INF = 1e18; const int inf = 2e9; const int SIZE = 1 0) return 1; else if (ret == 0) return 0; else return -1; } bool isIntersect(pll a, pll b, pll c, pll d) { ll ab = ccw(a, b, c) * ccw(a, b, d); ll cd = ccw(c, d, a) * ccw(c, d, b); if (ab == 0 && cd == 0) { // .. 2022. 10. 6.

티스토리툴바