티스토리

궤도

검색하기

블로그 홈

궤도

myunji.tistory.com/m

내가 보려고 쓰는 블로그

구독자: 18

방명록 방문하기

주요 글 목록

[백준] 20056번 : 마법사 상어와 파이어볼 문제 풀이 메모리면에서 그닥 효율적인 코드는 아닌 것 같지만 적어본다. 할 일은 2개밖에 없다 1. 파이어볼 이동 2. 파이어볼 분리 파이어볼의 상태를 저장할 구조체가 필요하겠고, 한 좌표에 둘 이상의 파이어볼이 있는지도 잘 체크해야 하고... 또 사라진 파이어볼을 어떻게 처리할지도 생각해야 한다. 아 그리고 격자의 크기가 최대 50인데 속력의 크기는 최대 1,000이다. 이걸 하나하나 움직이는건 당연히 비효율적이니 모듈러 연산을 사용해야 한다. 소스코드 #include #include using namespace std; struct info { bool is_remain; int r, c, m, s, d; }; int N; vector board; vector fire; pair dir[8] = {{.. 공감수 0 댓글수 0 2021. 8. 31.
[백준] 1938번 : 통나무 옮기기 문제 풀이 최소 동작 횟수라고 했으니까 BFS로 풀면 될 것이고, 가로로 놓는 경우와 세로로 놓는 경우의 visited를 따로 처리해야하니까 3차원 배열로 visited를 처리해야겠다. 그리고 3개를 다 들고 돌아다니는건 좀 비효율적이니까...가운데에 있는 통나무 하나만 들고다니려고 한다. 왜 굳이 가운데를 쓰냐면 그게 회전할 때 편하기 때문이다. 통나무의 상태, 그리고 하려는 동작에 따라 체크해야하는 범위가 다르다. 가로 통나무를 UDLR 하면 1x3의 범위를 확인해야 하고, 세로 통나무를 UDLF 하면 3x1의 범위를 확인해야 하고, T하면 3x3의 범위를 확인해야 한다. 이걸 하나하나 따로 처리하는건 비효율적이니까 함수로 만들어서 관리하려고 한다. 소스코드 #include #include #incl.. 공감수 0 댓글수 0 2021. 8. 18.
[백준] 19236번 : 청소년 상어 문제 풀이 할 일을 정리해보자... 1. 상어가 위치한 곳에 있는 물고기를 먹음 1.1 상어의 위치, 방향 정보 갱신 1.2 물고기 삭제 처리 1.3 상어의 새로운 위치를 공간에 기록 2. 1~16번 물고기 이동(아직 살아있는 물고기만) 3. 상어가 이동할 수 있는 모든 공간 탐색(백트래킹 재귀 함수) 3.1 상어가 더 이상 이동할 수 없으면 최댓값 갱신 공간의 현재 상태를 기록할 4x4 2차원 배열과 상어+물고기의 위치, 방향 정보를 기록할 1차원 배열이 필요하다. 상어는 여러 칸을 이동할 수 있지만 방향을 바꿀 수 없고, 물고기는 한 칸만 이동할 수 있지만 방향을 바꿀 수 있다는 차이점을 염두해야 한다. 소스코드 #include #include using namespace std; struct inf.. 공감수 0 댓글수 0 2021. 7. 12.
[백준] 17281번 : ⚾ 문제 풀이 각 선수가 몇 번 타자가 될 지는 next_permutation으로 구하면 된다. 다만, 1번 선수가 4번 타자인건 고정이니 2~9번 선수들에 대해서만 순열을 돌리고 4번 타자가 된 선수와 1번 선수를 바꾸면 되겠다. 점수나 다음 타자는 이닝이 바뀌어도 누적되는 결과니까 전역변수로 처리하면 된다. 그리고 1, 2, 3루 각 플레이트에 선수가 있는지 없는지를 저장해야 하는데...나는 비트 마스킹을 썼다. 1110 : 1, 2, 3루에 주자 존재 0100 : 2루에 주자 존재 1010 : 1, 3루에 주자 존재 가장 오른쪽 비트는 이번에 나선 타자를 위해 남겨뒀다. 아무튼 이런식으로 하면 주자 이동도 3루타 일때 (1011) 공감수 0 댓글수 0 2021. 7. 4.
[백준] 1194번 : 달이 차오른다, 가자. 문제 풀이 그냥 평범한 bfs로 풀 수 있을 것 같은데 생각을 하나 해야한다. 예제 입력 1을 보면 알 수 있듯이 이미 방문한 정점이지만 f 열쇠를 획득한 이후엔 다시 방문할 수 있다. 열쇠 보유 '상태'가 달라졌기 때문이다. https://myunji.tistory.com/289 [백준] 2206번 : 벽 부수고 이동하기 문제 풀이 너어무 어려웠다. 골드 4길래 풀만할 줄 알았는데 아니었다. 반례가 너무 많았어서 기억도 안나고 여기서 더 최적화 할 수 있을 것 같은데 더 이상 못하겠다. 솔직히 설명도 잘할 자신 myunji.tistory.com 이 문제랑 비슷한 개념인데, 참고로 저 문제 이제 완벽하게 이해해서 관련 문제도 2차원 배열 내에서 다 해결했다. 뿌듯 아무튼 저 문제에서의 상태는 '벽을 부순.. 공감수 0 댓글수 0 2021. 7. 3.
[백준] 17779번 : 게리맨더링 2 문제 풀이 뭐 이런 문제가 다 있지? 재미도 뿌듯함도 없는 순수 노가다 구현 문제다. 일단 정해야하는 변수가 x, y, d1, d2이니 4중 루프를 돌려야 하는데 당연히 나는 중간에서 코드를 쪼갰다. x, y를 기준으로 잡고 d1, d2를 구할 수도 있고, d1, d2를 기준으로 잡고 x, y를 구할 수도 있는데 난 후자로 했다. 그게 더 계산이 쉬울 것 같아서였다. d1과 d2의 범위는 정해진 조건을 들고 잘 계산해보면 (d1+d2) 공감수 0 댓글수 0 2021. 7. 1.
[백준] 17406번 : 배열 돌리기 4 문제 풀이 예전엔 구현 문제가 정말 싫었는데 요즘은 좀 괜찮은 것 같다. 풀고나서 성취감이 커서 그런가 싶다. 회전의 순서는 next_permutation으로 정했다. 각 연산에 대해 s개의 정사각형이 움직이게 되는데...이걸 그림으로 표현하면 이렇게 된다. 제일 큰 문제가 회전일 텐데...나는 큐를 썼다. 자세한건 코드를 보면서 설명하겠다. 소스코드 #include #include #include #include using namespace std; struct info { int idx, r, c, s; }; vector matrix; pair dir[4] = {{0, 1}, //우 {1, 0}, //하 {0, -1}, //좌 {-1, 0}}; //상 void rotate(int sr, int sc,.. 공감수 0 댓글수 0 2021. 6. 29.
[백준] 17471번 : 게리맨더링 문제 풀이 할게 많아보이는데 그렇게 많진 않다. 1. 두 선거구로 나눈다. 2. 두 선거구의 인구 차이를 구한다. 3. 두 선거구를 올바르게 나눴다면 인구 차이의 최솟값을 갱신한다. 2번과 3번의 순서가 바뀌어야 하지 않나?라고 생각할 수도 있다. 근데 인구 차이를 먼저 구하고 그 값이 현재의 최솟값보다 크거나 같다면 3번을 실행하지 않을 것이다. 그럼 불필요한 연산을 하지 않으니 시간이 좀 줄어들 것이다. 두 선거구를 나누는 조합 연산은 비트마스킹으로 했다. 소스코드 #include #include using namespace std; vector split, visited; vector population; vector graph; int calcDiff() { //두 선거구의 인구 차이 int bl.. 공감수 0 댓글수 0 2021. 6. 27.
[백준] 17135번 : 캐슬 디펜스 문제 풀이 각 턴마다 해야하는 일을 순서대로 써보자. 1. 궁수가 적을 타겟팅 2. 동시에 공격 3. 적 이동 둘 이상의 궁수가 하나의 적을 공격할 수 있다고 하니 타겟팅만 해두고 한번에 공격해야 한다. 궁수의 공격 범위는 반지름이 d인 반원의 형태라고 볼 수 있는데, 그래서 좌, 상, 우의 순서로 탐색하다 제일 먼저 찾은 적을 공격하면 된다. https://myunji.tistory.com/378 [백준] 16236번 : 아기 상어 문제 풀이 계속해서 상어를 이동시키며 이동할 때마다 bfs를 실행해야 한다. 다행히 입력 범위가 그렇게 크지 않아 bfs를 여러번 해도 시간 초과는 발생하지 않는다. 상어가 물고기를 먹는 우선순 myunji.tistory.com 가능한 모든 후보를 찾고 정렬했던 이 문제보단.. 공감수 0 댓글수 0 2021. 6. 20.
[백준] 14890번 : 경사로 문제 풀이 어쩌다보니 요즘 삼성 문제에 대한 풀이만 올리는 것 같은데... 구현 문제가 아니고서야 코드가 다 비슷비슷해서 굳이 올리지 않는 것이다. 일단 같은 행으로 이루어진 길은 다루기가 쉬운데 같은 열로 이루어진 길은 좀 까다롭다. 그래서 아주 간단한 방법을 썼다. 1 2 3 4 이런 지도가 있다고 하자. 이 지도를 값들을 1 2 3 4 1 3 2 4 이렇게 저장할 것이다. 그냥 길을 저장할 배열을 지도의 2배로 만들고 같은 열의 길도 같은 행의 길 처럼 저장하는 것이다. 그럼 각각의 길들을 독립적으로 다룰 수 있다. 3 2 1 1 2 3 이란 길이 있다고 하자. 맨 왼쪽(i=0)에서부터 맨 오른쪽의 직전 위치(i=4)까지 살펴볼 것인데 i=0 일 때를 보자. 3->2로 내리막 경사로를 설차해야 한다.. 공감수 0 댓글수 0 2021. 6. 8.
[백준] 15683번 : 감시 문제 풀이 이 문제의 풀이를 쓰는 이유는... 문제를 풀고 다른 사람들의 풀이가 궁금해서 블로그를 봤더니 거의 다 하드코딩(?)을 했더라 내가 짠게 엄청 좋아보이진 않지만 그래도 최대한 효율적으로 쓰려고 노력해서 올려본다. 말로 설명하기가 좀 그래서 코드를 보면서 설명하려는데 그 전에 이걸 봐두면 좋다. 내 코드에선 각 cctv의 범위가 이렇게 세트로 묶여 있다. 무슨 말인지는 코드를 보면 이해될 것이다. 소스코드 #include #include #include using namespace std; typedef pair pp; int N, M, result = 65; vector board; vector cctv; //cctv 위치 pp direction[4] = {{-1, 0}, //상 {0, 1},.. 공감수 0 댓글수 0 2021. 6. 6.
[백준] 14891번 : 톱니바퀴 문제 풀이 원래는 그냥 단순 구현이라 이 문제에 대한 풀이를 쓸 생각이 없었는데... 맞고 나서 다른 사람들은 어떻게 했을까 싶어 블로그들을 보니 뭐 덱을 쓰기도 하고 이상한 복잡한 무언갈 하기도 하고 뭔가 나랑 비슷한건 없어보였다. 구현이 워낙 그냥 조건대로 돌아가기만 하면 그만인 문제라 그런걸지도 모르겠다. 아무튼 그래서 나의 풀이를 적어보겠다. 톱니바퀴는 동시에 돌아가니까 회전하게 될 톱니바퀴를 먼저 다 체크하고 한번에 회전해야 한다. 그리고 회전하게 될 톱니바퀴는 연속일 것이다. 회전시킬 톱니바퀴를 기준으로 왼쪽과 오른쪽을 따로 살펴보며 처음으로 돌아가게 될 톱니바퀴와 마지막으로 돌아가게 될 톱니바퀴를 확인한다. 만약 2번 톱니바퀴를 시계방향으로 돌렸는데 1번 톱니바퀴부터 돌아가기 시작한다면 시계.. 공감수 0 댓글수 0 2021. 6. 5.
[백준] 13460번 : 구슬 탈출 2 문제 풀이 비트마스크로도 풀 수 있다는데 난 백트래킹으로 풀었다. 근데 bfs로도 풀 수 있나보다. 먼저 상하좌우에 대해 각 구슬의 새로운 위치를 찾는다. 직전에 갔던 방향으로 또 이동할 필요는 없으니 그 방향은 제외한다. 두 구슬의 위치변화가 없거나 파란구슬이 빠진 경우는 제외한다. 만약 두 구슬의 새로운 위치가 같다면 같은 칸에 구슬이 2개 있을 수는 없으니 원래의 선후관계를 따져 구슬을 이동한다. 이동 횟수가 10을 넘어가거나 현재의 최솟값을 넘어가면 더이상 탐색하지 않는다. 소스코드 #include #include #include #include using namespace std; typedef pair pp; int result = 11; vector board; pp dir[4] = {{-1.. 공감수 0 댓글수 0 2021. 5. 24.
[백준] 4574번 : 스도미노쿠 문제 풀이 일단 주어진 도미노의 총 개수는 36개이므로 이 도미노들의 정보와 사용여부를 map으로 관리하기로 했다. 그리고 빈 공간을 발견할 때마다 가로 또는 세로로 배치할 수 있는 도미노를 찾아보는데 1 1 1 상하좌우로 배치할 필요없이 그냥 2개의 방향만 고려하면 된다. 위 또는 왼쪽으로 배치하는건 이전 경우에서 고려됐을 것이기 때문이다. 아무튼 그래도 하나의 위치에 대해 최대 4개의 경우를 고려해야 한다. (가로세로)*(도미노 방향 2) 하나의 도미노에 적힌 숫자는 다르기 때문에 해당 위치에 이 도미노가 들어갈 수 있을지 확인할 때 도미노를 쪼개서 각각 고려해도 문제가 없다. https://myunji.tistory.com/202 [백준] 2580번 : 스도쿠 문제 풀이 입력을 어떻게 처리하여 어떤.. 공감수 0 댓글수 0 2021. 5. 24.
[백준] 10217번 : KCM Travel 문제 풀이 지금까지 풀었던 골드1 문제는 힌트를 조금씩 봐야했는데, 이건 정말 나혼자만의 힘으로 풀었다. 뿌듯히다. 처음에는 '플로이드-워셜'일까 싶었는데 이것도 모든 경로와 비용을 고려하진 못해서 동적 계획법을 써야겠거니 했다. 일단 최소 2차원 배열일 것 같았고, 행과 열을 무엇으로 할지 고민했는데 냅색 문제를 떠올렸다. 그래서 행을 각 정점으로 하고, 열을 비용으로 하는 2차원 dp 배열을 생각했다. 예제 입력 1의 두번째 테스트 케이스에 대해서 dp 배열의 초기값을 만들어보면 이렇게 될 것이다. dp[i(파란색)][j(초록색)]의 의미는 j만큼의 비용이 있을 때 1번 정점에서 i번 정점까지 가는 최단 거리이다. 당연히 출발점인 1에서 1까지 가는 최단거리는 비용에 상관없이 0이다. 한편 예제 입력.. 공감수 1 댓글수 0 2021. 5. 19.
[백준] 2473번 : 세 용액 문제 풀이 https://myunji.tistory.com/362 [백준] 2470번 : 두 용액 문제 풀이 이 문제는 시간제한이 있기 때문에 모든 쌍을 찾는 O(n^2)의 시간 복잡도로는 풀 수 없다. 그래서 O(n)의 시간복잡도인 투 포인터 알고리즘을 사용해야 한다. 투 포인터 알고리즘을 사용 myunji.tistory.com 이 문제를 응용한 것이다. 두 용액이면 투포인터를 쓰면 될 것인데 3개라 어떻게 할지 고민됐다. 근데 그냥 용액 하나를 고정하고 투포인터를 돌리면 되는 것이었다. 이렇게 초록색을 고정하고 빨간색과 파란색 포인터를 움직이자 N개의 용액이 있을때 초록색 포인터는 0~N-3번 용액까지 움직일 수 있다. 소스코드 #include #include #include #include #inc.. 공감수 0 댓글수 0 2021. 5. 13.
[백준] 1005번 : ACM Craft 문제 풀이 위상정렬 문제다. m.blog.naver.com/ndb796/221236874984 25. 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 ... blog.naver.com 이 분께서 시간 복잡도까지 포함해서 잘 정리해 주셨다. 각 빌딩의 건설 시간을 저장할 벡터와 이 빌딩을 건설하기까지의 시간까지를 저장할 벡터를 각각 만들었다. 두번째 벡터를 갱신하는 과정에서 실수가 있었는데 처음엔 더이상 부모 정점이 없어 큐에 삽입이 가능한 시점에만 갱신을 했다. 그리고 '입력 예제 1'의 두번째 테스트케이스에서 19라는 결과가 나와서 그림을 그려보니 어디가 문제였는지 이해됐다. 건설에 걸리는 총 시간은 .. 공감수 0 댓글수 0 2021. 5. 13.
[백준] 11657번 : 타임머신 문제 풀이 보통의 최단거리는 다익스트라 알고리즘을 사용하지만 간선의 가중치가 음수인 경우 다익스트라를 무한루프에 빠질 수 있다. 어떤 경우에 그렇게 되는지는 내가 설명하긴 귀찮고 구글에 자료가 많으니 검색해보면 될 것이다. 아무튼 그럴때 쓰는 방법이 벨만-포드 알고리즘인데 정점을 기준으로 최단거리를 갱신해 나가는 다익스트라와 달리 이건 간선을 기준으로 최단거리를 갱신한다. 정점 A, B, C가 있다고 하자. 정점의 개수 V는 3이다. 아무리 멀리 돌아가도 최단경로라면 (V-1)개의 간선을 지날 것이다. A-B-C인 경우 A-C로 가는 경로에 간선이 2개 있는 것처럼 말이다. 만약 V개의 간선을 지나서 갈 수 있는 최단경로라면? 이건 음의 사이클이 발생한 것이다. 그러므로 일단 V-1번동안 간선을 살펴보며.. 공감수 0 댓글수 0 2021. 5. 11.
[백준] 1238번 : 파티 문제 풀이 처음에는 이 문제가 당연히 플로이드-워셜 문제인 줄 알았다... 실제로 그걸로 풀었더니 맞기도 했고... 근데 다익스트라 문제라는 것이다...! 난 이해가 되지 않았다. 다익스트라는 하나의 시작점에서 모든 정점과의 거리를 구하는 SSP 알고리즘인데 이 문제는 모든 사람에 대해 도착지점 하나에 대한 거리를 구해야 하기 때문이다... 굳이 모든 정점에 대해 하나하나 다익스트라를 돌리느니 플로이드-워셜이 낫지 않나 했는데 다익스트라 2번으로 해결할 수 있는 방법이 있었다. jow1025.tistory.com/114 [백준 1238] 파티 문제출처: https://www.acmicpc.net/problem/1238 풀이 출발->거쳐서->도착 의 패턴이 보여서 플로이드와샬 알고리즘이 끌리는데, 정점의 .. 공감수 0 댓글수 0 2021. 5. 11.
[백준] 1043번 : 거짓말 문제 풀이 처음에는 각 사람들의 연결관계를 그래프로 만들어서 dfs했는데 생각해보니 정답을 맞고 보니 유니온 파인드로도 풀 수 있단걸 깨달아서 유니온 파인드로도 풀었다. 두 풀이 모두 중요한 부분은 모든 파티 정보를 고려해서 연결되어 있는 사람들을 전부 찾아야 한다는 것이다. 소스코드 - dfs #include #include using namespace std; vector isLie; //이 사람에게 거짓말을 할 수 있나? vector party_info; //파티 정보 vector graph; //연결 정보 void dfs(int cur) { //거짓말을 할 수 없는 사람을 체크 isLie[cur] = false; for (int i = 0; i < graph[cur].size(); i++) { i.. 공감수 0 댓글수 0 2021. 5. 11.
[백준] 16236번 : 아기 상어 문제 풀이 계속해서 상어를 이동시키며 이동할 때마다 bfs를 실행해야 한다. 다행히 입력 범위가 그렇게 크지 않아 bfs를 여러번 해도 시간 초과는 발생하지 않는다. 상어가 물고기를 먹는 우선순위 때문에 좀 헤맸다. 처음엔 단순히 '상-좌-우-하'의 순서로 탐색하면 되겠거니 했는데 '예제 입력 4'에서 틀린 답이 나왔다. 그래서 최단 경로에 위치한 모든 물고기들을 찾은 뒤, 그 물고기들 중에서 가장 우선순위가 높은 물고기를 찾는 방법으로 코드를 다시 작성했다. 소스코드 #include #include #include #include #include using namespace std; vector board; int shark_size = 2; //상어의 크기 int fish_cnt, result; //.. 공감수 0 댓글수 0 2021. 5. 10.
[백준] 9019번 : DSLR 문제 풀이 문제 자체는 그냥 간단한 BFS였는데 그 과정이 너무 더럽다고 해야하나 짜증나게 한다고 해야하나 암튼 그랬다. D, S까지는 그렇다고 치고 L, R을 구현하는게 문제인데, 제일 먼저 생각난건 string이라 그걸로 했더니 tle가 났다. 그러다가 잘 생각해보니 이거 그냥 수학으로 되는 연산이었다...이것만 빨리 알아챘어도.. 소스코드 #include #include #include #include #include using namespace std; string bfs(int source, int target) { vector visited; visited.assign(10000, false); queue q; visited[source] = true; q.push(make_pair(sourc.. 공감수 0 댓글수 0 2021. 5. 10.
[백준] 7662번 : 이중 우선순위 큐 문제 풀이 min-heap과 max-heap을 하나씩 만들어두고 각 정수별 인덱스도 함께 저장해서 삭제 여부를 체크하면 풀릴 것이다... 하지만 뭔가 이걸보니 지금까지 미뤄뒀던 set을 써야할 때가 왔구나 싶었다... www.cplusplus.com/reference/set/set/?kw=set set - C++ Reference difference_typea signed integral type, identical to: iterator_traits ::difference_type usually the same as ptrdiff_t www.cplusplus.com set은 입력되는 모든 값을 정렬된 상태(default : 오름차순)로 저장해주는 자료구조인데 그냥 set은 중복 저장이 불가능하고 mul.. 공감수 0 댓글수 0 2021. 5. 10.
[백준] 1074번 : Z 문제 풀이 분할정복 문제다. 일단 그냥 판을 크게 4등분 한다면 1 2 3 4 이 순서로 방문해야 한다. 그러면 판을 계속 4등분 하면서 우리가 구하고자 하는 좌표가 존재하는 사분면만 탐색하면 될 것 같은데 함수에 들어갈 인자가 뭐가 있을까... 사람마다 다르겠지만 대충 이번에 탐색할 사분면을 A라고 하면 기본적으로 들어가는 N, r, c에 더해서 A의 가장 왼쪽 위 좌표와 해당 좌표를 방문하는 순서를 저장했다. 4등분 될 때마다 N은 1씩 줄어든다. N이 0이 될 때까지 탐색하면 될 것이다. 소스코드 #include #include #include #include using namespace std; int recurZ(int N, int r, int c, int num, pair p) { if (N .. 공감수 0 댓글수 0 2021. 5. 10.
[백준] 17472번 : 다리 만들기 2 문제 풀이 할 것이 굉장히 많다... 일단 최대 입력을 보니 브루트포스로 각 섬을 연결하는 모든 다리를 찾아도 될 것 같았다. 그렇다면 각 섬을 연결하는 다리를 어떻게 찾을 것이냐가 문제인데... 각각의 섬을 구분해야 하니 섬마다 다른 숫자로 라벨링하기로 했다. myunji.tistory.com/355 [백준] 2146번 : 다리 만들기 문제 풀이 일단 다른 섬끼리 다리를 이어야 하기 때문에 각각의 섬을 구분해야 한다. 이런식으로 말이다. myunji.tistory.com/280 [백준] 2667번 : 단지번호붙이기 문제 풀이 문제 이름에 왜 띄어쓰기가 myunji.tistory.com 이 문제에서 섬을 구분했던 것과 같은 방법을 쓴다. 0 0 0 0 0 0 2 2 3 3 0 0 0 0 2 2 3 3 0.. 공감수 0 댓글수 0 2021. 5. 9.
[백준] 2887번 : 행성 터널 문제 풀이 입력이 100,000개까지 들어올 수 있어서 행성 하나하나마다 모두 거리를 구하면 메모리 초과가 발생한다. 그렇다면 MST에 들어올 가능성이 있는 거리만 저장해야 하는데 그걸 도대체 어떻게 알까? 이 부분 때문에 힘들었다. 두 행성을 연결하는 비용을 살펴보자. 보통의 좌표간 거리 구하기 공식이 아니라 x, y, z 좌표의 차이의 절댓값 중 가장 작은 값을 터널 비용으로 한다고 적혀있다. 그럼 문제를 단순화 해서 x좌표만 존재한다고 하자. 그럼 당연히 예제 입력 1에 대한 MST는 (-1) - (10) - (11) - (14) - (19)로 20일 것이다. 그니까 만약에 최종적으로 x좌표의 차이의 절댓값을 MST의 간선으로 사용하게 된다면...그것은 (-1) - (10), (10) - (11),.. 공감수 0 댓글수 0 2021. 5. 9.
[백준] 1774번 : 우주신과의 교감 문제 풀이 myunji.tistory.com/370 이 문제에서 각 정점이 좌표로 표현되는 정도만 달라졌다고 생각할 수도 있지만...하나 더 생각할 것이 있다. 바로 이미 연결된 정점들이 주어진다는 것이다. 처음엔 초기 연결 정점들이 다 연결가능하겠거니 하고 코드를 작성했다가 아닐 수도 있단 것을 깨달았다. 그니까 간단하게 예를 들자면 4 2 1 1 3 1 2 3 4 3 1 4 4 1 이렇게 입력이 들어와서 이미 1-4를 연결했는데 4-1을 연결하려고 할 수도 있다는 뜻이다. 이 부분만 신경쓰면 크게 어려울건 없다. 소스코드 #include #include #include #include #include using namespace std; typedef pair pp; int v_cnt; //사용한 간.. 공감수 0 댓글수 0 2021. 5. 9.
[백준] 1197번 : 최소 스패닝 트리 문제 풀이 최소 신장 트리, 최소 스패닝 트리, MST 등등으로 불리는 문제다. 가중치가 있는 간선이 주어진 그래프가 있을 때 가중치의 합이 가장 작은 트리를 만드는 것인데 트리니까 당연히 사이클이 없을 것이고 정점의 수가 V일 때, 최종 간선의 수는 V-1이 될 것이다. 이러한 MST를 만드는 대표적인 알고리즘은 크루스칼과 프림이 있는데 크루스칼(kruskal)은 유니온 파인드를 이용해 푸는 알고리즘이고 프림은 다익스트라랑 비슷해보여서 많이들 헷갈리지만 아무튼 둘은 다른 알고리즘이다. ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 크러스컬 알고리즘 - 위키백과, 우리 모두의 백과.. 공감수 0 댓글수 0 2021. 5. 9.
[백준] 20040번 : 사이클 게임 문제 풀이 myunji.tistory.com/350 [백준] 4803번 : 트리 문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근 myunji.tistory.com 이 문제에서 사이클을 찾는 코드를 작성하긴 했었다. 근데 이번 문제는 사이클이 생기는 지점을 정확히 찾아야 하기도 하고...해서 유니온 파인드로 풀 것이다. 달리말하면 4803번도 유니온 파인드로 풀 수 있단 뜻이다. 아무튼 유니온 파인드에서 사이클이 형성된다는 것을 알 수 있는 기점은 유니온 하려는 x와 y의 부모가 같을 때이다. 소스코드 #include #include using namespace std.. 공감수 0 댓글수 0 2021. 5. 9.
[백준] 4195번 : 친구 네트워크 문제 풀이 myunji.tistory.com/367 [백준] 1717번 : 집합의 표현 문제 풀이 유니온 파인드로 푸는 문제다. 약...2년전 자료구조 시간에 배웠는데 그때 당시에는 아는 것도 없고 + 영어 강의고 + 기타 등등의 이유로 개념만 정말 간신히 익힌 것 같다. 지금 내가 myunji.tistory.com 이 문제랑 거의 유사한데 다만 입력값이 string이라는게 조금 까다로울 뿐이다. string으로 들어온 입력값을 int처럼 사용할 수 있게 map을 사용할 것이다. Fred - 1 Barney - 2 Betty - 3 Wilma - 4 이런식으로 저장하면 parent[4]는 Wilma의 부모 노드인 뭐 그런거다. 소스코드 #include #include #include #include us.. 공감수 0 댓글수 0 2021. 5. 9.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.