본문 바로가기

알고리즘

 (160)
5650. [모의 SW 역량테스트] 핀볼 게임 주어진 게임판의 모든 빈 공간에서 핀볼을 동서남북 방향으로 모두 출발시켜 보는 완전탐색 시뮬레이션 문제입니다. 저는 Ball 클래스를 만들어서 빈공간의 모든 위치 x, y와 동서남북 방향을 뜻하는 d에 0,1,2,3 을 넣어서 ArrayList에 담고 모든 빈 공간에서 핀볼게임을 동서남북방향으로 시작했습니다. 그리고 웜홀을 처리하는 것이 문제였는데 웜홀 또한 Hole이라는 클래스를 만들어서 ArrayList에 모든 웜홀의 위치 x, y를 저장했습니다. 그래서 핀볼이 움직이면서 웜홀을 만나게 되면 모든 웜홀이 담긴 ArrayList를 전체 탐색하면서 자기 자신의 다른 짝 웜홀을 찾아서 그 위치로 이동시키는 방법으로 처리했습니다. 이 부분은 생각해보면 웜홀은 한 쌍으로 이루어져 있기 때문에 더 효율적으로 처..
[프로그래머스] 프린터 https://programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr priorities 에 들어 있는 숫자들을 위치와 함께 기억해야 하기때문에 Pair라는 클래스를 선언했습니다. idx에는 숫자들의 위치를 기억하고 value에는 숫자들을 저장하여 queue에 먼저 담았습니다. 그리고 priorities 에 있는 숫자들을 정렬하여 가장 큰 숫자가 우선순위가 가장 높기 때문에 queue에서 하나씩 빼가면서 비교했습니다. 우선순위가 가장 높은 숫자가 아니라면 queue에 다시 추가..
[백준] 17822. 원판 돌리기 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j www.acmicpc.net 2019 하반기 삼성 공채 SW 역량테스트 시뮬레이션 문제 입니다. 제가 봤던 시간대가 아닌 다른 시간대에 문제였는데 정답률을 보..
[백준] 17837. 새로운 게임2 https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 www.acmicpc.net 2019 하반기 삼성 공채 SW 역량테스트 시뮬레이션 문제 입니다. 제가 봤던 시험 시간에 나온 두 문제중 하나 였는데 게리멘더..
서로소 집합(Disjoint-set) 서로소 집합 : 서로소 또는 상호 배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 집합에 속한 하나의 특정 멤버(representative) 를 통해 각 집합들을 구분한다. 상호배타 집합을 표현하는 방법 : 연결리스트, 트리 상호배타 집합 연산 : Make-Set(x), Find-Set(x), Union(x, y) CODE 1. Make-Set(x) void makeSet(int x) { parents[x] = x; } 2. Find-Set(x) int findSet(int x) { if(x == parents[x]) return x; else { parents[x] = findSet(parents[x]); return findSet(parents[x]); } } 3. Union(x, y) vo..
프림 알고리즘 (Prim Algorithm) 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 정점을 하나씩 선택할 때마다 간선을 추가하면서 트리 확장 두 종류의 상호배타집합 정보를 유지 - 트리 정점들(tree-vertices) : MST를 만들기 위해 선택된 정점들 - 비트리 정점들(non-tree vertices) : 선택 되지 않은 정점들 동작과정 임의 정점을 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때까지 1, 2 과정을 반복 import java.util.Arrays; import java.util.Scanner; /* 7 11 0 1 2 0 2 2 0 5 8 1 2 1 1 3 19 2 5 5 3 4 7 3 5 11 3 6 15 4 ..
[SWEA] 1251. [S/W 문제해결 응용] 4일차 - 하나로 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD&categoryId=AV15StKqAQkCFAYD&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com Kruskal import java.util.Arrays; import java.util.Scanner; public class Solution { static class Edges implements Comparable { int v1; int v2; long cost; public Edges(int v1, int ..
크루스칼 알고리즘 (Kruskal Algorithm) 1. 신장트리 : 그래프의 모든 정점과 간선의 부분집합으로 구성되는 트리 2. 최소신장트리(MST) : 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리 - 무방향 가중치 그래프 - 그래프의 가중치의 합이 최소여야 한다. - N개의 정점을 가지는 그래프에 대해 반드시 (N-1) 개의 간선을 사용해야 한다. - 사이클을 포함해서는 안된다. 3. Kruskal Algorithm - 탐욕적인 방법을 이용하여 가중그래프(가중치를 간선에 할당한 그래프)의 모든 정점을 최소비용으로 연결하는 최적해를 구하는 것 - 간선을 하나씩 선택해서 MST를 찾는 알고리즘 - 동작과정 ① 그래프의 간선들을 가중치의 오름차순으로 정렬한다. ② 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. a. 가..

티스토리툴바