반응형 개발삽질52 [BOJ]2667_단지번호붙이기(bfs) https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 낼모레가 정처기 시험이라 알고리즘 안풀려 했는데, 알고리즘 안푼다고 정처기 공부 더 하는 것 같지도 않다고 느꼈다. 외우는 공부는 이제 나이가 들어서 그런지 집중력 10분을 넘기지 못한다. 그러나 알고리즘 문제는 한시간은 거뜬히 집중할 수 있다는 것을 알기에 걍 이렇게 멍 때리고 유튜브보면서 공부 안할 바에 얼른 알고리즘 문제 하나 더 풀자고 생각했다. 문제는 내가 좋아하는(?) bfs.(물론 bt.. 2022. 3. 3. [BOJ]13549_숨바꼭질3(다익스트라) 오늘은 간만에 찾아온 휴일이었다. 삼일절! 그러나 난 불쌍한 취준생이자 이번주 토욜에 정보처리기사를 봐야 하기에 꾸역꾸역 카페에 가서 공부를 하였다. 정처기만 보고 있자니, 알고리즘을 까먹을까봐 한문제만 풀자하고 저녁먹고 풀었다. 다익스트라 마스터가 되려 그러는지 다익스트라를 골라서 풀었다ㅋㅋ https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 여태 연습했던 최다경로 문제와 달리, 이 문제는 그래프 문제가 아니다... 2022. 3. 2. [SWEA]1251_하나로 (크루스칼) 문제를 읽으면 전체 섬들을 다 합치는거다. 그럼 최소신장트리를 이용한 문제란 감이 온다. 근데 좀 짜증나는게 입력값으로 x좌표 따로, y좌표 따로 온다. 아니 이건 인접리스트를 만들어야 되나 인접행렬을 만들어야되나고민이 됐다. 다시 정리해보면, [알고리즘]최소신장트리(크루스칼,프림) 이름부터 무슨 중국말도 아니고 신장트리래. 영어는 더 어려움 수학공식같은 이름.. 그러나 막상해보면 별거아님 또. 이름 지은 사람들 다들 한대씩 맞아야함.ㅋㅋ 위 알고리즘을 쓰는 때는, 그 lovenewthing.tistory.com -인접리스트로 만들어서 푸는거 = 크루스칼 크루스칼 장점 : 좀 더 구현하기 수월함 단점 : 간선들을 정렬해줘야 해서 시간이 쪼오금 더 걸림 -인접행렬로 만들어서 푸는거 = 프림. 암튼, 이렇게.. 2022. 2. 25. [알고리즘] 다익스트라 개념정리~~~!, BOJ1753 적용 이전에 했던 크루스칼, 크림이 최소신장트리(모든 정점을 있는 간선들 중에 가장 비용이 적은 애들)를 찾는 알고리즘이었다면, 다익스트라는 하나의 정점에서 다른 정점으로 가는 길목들 중에 가장 비용이 적은 간선들을 고르는 것이다. 목적은 달라도 구현방식은 유사하다. (비슷한데 조금씩 달라서 더 헷갈리기도 한다..ㅎㅎ) 정점 정보로(=행렬로) 입력값이 들어온다면? 무식하게 행렬로 하는게 더 간단할 때가 있는 법이다. 순서대로 체크포인트: 입력이 정점들로 주어지니 일단 다 받는다. 다익스트라는 출발 정점->도착 정점 문제임을 잊지말자. int[] distance부터 논리가 시작된다! distance[2]은 출발정점 ->2번정점으로 오는 최소비용이다. 주의할 게, 어디어디를 몇번 거쳐서 어케 왔든간에 출발정점에서.. 2022. 2. 24. [BOJ]16236_아기상어(BFS응용) 진짜 과장 거의 안하고, 하루종일 이거만 푼 거 같다. 잘 하는 분들은 한시간만에 풀던데, 난 거의 열배넘는 시간을 들여서 겨우 했다. https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 처음에 문제를 읽을 때 도저히 감도 잡히지 않았다. 해설을 보고나서야 BFS구나를 깨달은 나는 ㅄ인가. 암튼,해설대로만 하지 않고 그래도 아무것도 안보고 다시 시도해서 겨우겨우 하는 데 성공했다. 단, 중간중간 버그잡는게 두시간가까이 걸렸다. 절대 대충 이.. 2022. 2. 24. [알고리즘]최소신장트리(크루스칼,프림) 이름부터 무슨 중국말도 아니고 신장트리래. 영어는 더 어려움 수학공식같은 이름.. 그러나 막상해보면 별거아님 또. 이름 지은 사람들 다들 한대씩 맞아야함.ㅋㅋ 위 알고리즘을 쓰는 때는, 그래프에서 최소비용을 구할 때 쓰인다. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가되는 것을 구할 때 쓰인다. 신장트리란, 위구르신장지역 아님. 아니 암튼, 신장트리란 n개의 정점으로 이뤄진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이뤄진 트리를 말함. 걍 간단하게 말하면 모든 정점에 딱 하나씩만 간선이 있는거임. 이때 최소신장트리란, 무향 가중치 그래프에서 신장트리를 구성하는 가중치의 합이 최소인 신장트리를 말함. 그니까 두 정점 사이에 간선이 여러개 있을 수 있는데 그중 가장 쬐그만 간선들로 이뤄진 신.. 2022. 2. 23. 이전 1 2 3 4 5 6 7 ··· 9 다음 반응형
