Algorithm76 [알고리즘] 2048 (Easy) (백준 12100번) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 삼성 기출 문제인데 정말 삼성스러운 문제라고 할 수 있다. 시뮬레이션 + 브루트 포스 문제다. 이전의 다른 삼성 기출 문제들과 마찬가지로 맵에서 여러 물체를 동시에 움직이는 것을 구현해야한다. Solution 1. 전역 변수 var N = 0 lateinit var map : Array var max = 0 val UP = 0 val DOWN = 1 val LEFT = 2 val RIGHT = 3 상하좌우를 나타내는 상수들과 그 외의 .. 2020. 10. 5. [알고리즘] ACM Craft (백준 1005번) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 그래프 상으로 본인보다 앞서 있는 건물들이 모두 지어져야 해당 건물을 지을 수 있다는 설정을 보면 알 수 있듯이 위상 정렬을 쓰는 문제다. 다만 건물 건설 시간이 각각 다르다보니 기교를 가해야한다. 결론적으론 '위상정렬 + DP' 문제다. Solution 1. topologicalSort 함수 static int topologicalSort(int N, int W, int[] complete_time, ArrayList graph, int inEdge[].. 2020. 10. 5. [알고리즘] 소수 구하기 (에라토스테네스의 체) 소수 소수 : 약수가 해당 숫자 본인과 1만 존재하는 수를 의미한다. (영어로는 Prime Number) EX) 2, 3, 5, 7 ..... (짝수 중에선 2가 유일한 소수이다.) 에라토스테네스의 체 모든 자연수는 단 하나의 소수들의 곱으로 표현된다는 특징을 이용하여 일정 범위의 수들이 소수인지 여부를 판단하는 방법이다. 즉, 소수의 곱이 되는 수는 소수가 아닌 것을 이용하여 소수가 아닌 수들을 걸러나가는 방법이다. 2가지 방법이 있는 데 순서의 차이일 뿐 어느 것을 써도 무방하다. 1. 소수 구한 후 결과 반전 boolean형 배열을 선언할 때는 초기값이 false로 채워져있기 때문에 우선 소수가 아닌 수들에 true를 해놓고 나중에 반전을 시키는 방법이다. int number = 10000; boo.. 2020. 10. 5. [알고리즘] 외판원 순회 2 (백준 10971번) 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원 순회, 일명 TSP라고 불리는 문제다. 외판원은 모든 도시를 최소 비용으로, 단 한 번 방문한 도시는 다시 방문할 수 없다는 조건 하에 순회하게 된다. (마지막 도시에서 출발 도시로 돌아오는 경우 제외) 도시를 방문하는 순서 케이스들을 찾아야 하기에 순열을 구하는 문제다. 이 경우는 N의 크기가 10 이하이기 때문에 백트랙킹으로 모든 경우를 찾을 수 있다. Solution 백트랙킹으로 순열을 구할 때와 조합을 구.. 2020. 10. 4. 이전 1 ··· 3 4 5 6 7 8 9 ··· 19 다음
