본문 바로가기

분류 전체보기84

다익스트라 vs 크루스칼 비교 (java) 다익스트라 크루스칼 구현 방법 우선순위 큐 + dist(점화식) 우선순위 큐 + Union-Find 중심 정점 중심 간선 중심 시작점 출발점이 정해져 있는 경우 간선의 가중치가 가장 작은 것부터 시작한다 큐에 넣는 시점 dist가 갱신 될 때에만 그 점에서 출발하는 간선을 우선순위 큐에 넣어준다. 모든 정점을 우선순위 큐에 넣고 시작한다 용도 점과 점 사이의 거리를 구할 경우 최소 신장 트리를 그릴 때 끝 점과 점 사이의 최단 거리를 찾고 나면, 더이상 탐색하지 않는다. 목적에 따라 끝까지 그릴 수도 있다. 최소 신장 트리가 만들어 질 때까지(모든 점들이 다 이어질 때 까지) 탐색한다. 두 덩이일 경우 한 덩이만 그려지고 다른 한덩이는 그려지지 않는다(이어져 있지 않기 때문에) 간선 중심이므로 끝까지 가.. 2020. 2. 1.
[백준] 17472.다리 만들기 2 (java) / 크루스칼, Union-Find, DFS, BFS, 시뮬레이션 @ 크루스칼, Union-Find, DFS, BFS, 시뮬레이션 / 1h 30m 9월 삼성 SW 역량테스트 2번 문제 종이에 쓰는시간 30분을 포함해서 1시간만에 풀었는데 몇가지 실수해서 디버깅하느라 +30분 걸렸다. 다익스트라, DFS 등 여러 개념을 이용해서 풀 수 있는 좋은 문제인 것 같다. 약간 어려운 편. 문제 링크 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 구현 방법 1. 먼저 각 섬들에 단지번호붙이기 방법.. 2020. 2. 1.
[SWEA] 2105.디저트 카페 / DFS @DFS / 35m 쉬운 문제였다. 그런데 마지막 사각형이 만들어질 때 예외처리를 해주지 않으면 직사각형이 아닌 다른 모양으로 만들어져서, 테케가 틀리게 나온다. 그 부분만 신경쓰면 끝나는 문제. 문제 링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 구현 방법 # 문제의 화살표 방향과 반대로 구현했을 때의 풀이방법이다. (별 의도는 없고 하다보니..) 1. 사각형에서 제일 위에 있는 점에서 시작했다. 이중 for문을 돌면서 (이때 세로는 0 2020. 1. 28.
[SWEA] 5650.핀볼 게임 / 시뮬레이션 @시뮬레이션 / 4h 이상 처음에는 오 인덱스 조절만 잘 하면 쉽겠다 하고 풀었는데 이게 웬걸.. 테케도 안맞아서 그때부터 멘붕되고 값을 넣는 족족 stackoverflow로 터져버려서 내 멘탈도 같이 터진 문제였다.. ㅎㅎ 나중에는 swea의 댓글을 참고하면서 코드를 고쳐나갔는데 테케 40->42->43->46->49 순으로 맞아서 진짜 인내심 테스트 하는 줄 알았다. 마지막에 pass 떴을 때에는 되는건 좋은데 왜 되는지 스스로 이해가 안돼서 더 괴로웠다 ㅠㅠ 알고보니 문제를 잘못 이해했던 거였다. 주어진 대로만 풀면 적당한 문제였는데.. 문제 링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6.. 2020. 1. 27.
[SWEA] 4008.숫자 만들기 / Next-Permutation @Next-Permutation / 24m 넥퍼로 풀면 재귀보다 훨씬 효율적으로 풀 수 있는 문제다. 쉬운 문제였음! 문제 링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 구현 방법 1. 연산자를 +는 0, -는 1, *는 2, /는 3으로 바꿔서 크기가 N - 1인 int 배열에 저장했다. 예를 들면, 문제에서 2 1 0 1 로 주어졌을 때 (1번 테케) 이를 크기가 4인 배열에 0 0 1 3 이렇게 저장하는 식이다. 이를 위해서 Arra.. 2020. 1. 26.

티스토리툴바