본문 바로가기
728x90

Algorithm128

2352 반도체 설계 www.acmicpc.net/problem/2352 [ 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net ](https://www.acmicpc.net/problem/2352) (문제 풀이) 해당 문제의 요구사항 왼쪽의 포트들을 오른쪽의 포트로 겹치지 않게 가장 많이 연결할때의 포트 갯수를 구한다. 가장 쉽게 생각 해볼 수 있는 최선의 방법은, 시작 포트에서 부터 가장 적은 번호와 연결시키는 방법일 것이다. 가장 최악의 경우를 생각해보면 가장 첫번째 포트가 가장 마지막 포트와 연결 되는 경우.. 2020. 12. 7.
17144 미세먼지 안녕! www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net (문제 풀이) 이 문제는 별 다른 시간복잡도와 알고리즘의 사용을 요구하지 않는다. 시뮬레이션 구현의 문제이다. 하나씩 어떻게 동작하는지 예제 그림의 도움을 최대한 받아서 하나씩 따라가며 시작해본다. 1. 확산을 하고 2. 공기청정기의 위 아래 기준으로 배열의 값들을 회전시킨다. 그렇다면, 1. 확산을 어떻게 시킬것인가 모든 먼지가 있는 칸에 확산되는 값들과, 감소되는 기존 미세먼지 중심의 감소값을 따로 Cop.. 2020. 12. 7.
[Summer/winter Coding ~ (2018)] 배달 https://programmers.co.kr/learn/courses/30/lessons/12978?language=cpp 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr (풀이) 인접리스트를 만들어 DFS를 이용하여 푼다. (1) Input, 노드간 가중치가 최소인 거리만을 인접리스트로 만들어준다. _distance[][] 사용 (2) check[from][to]로 이전 노드에서 다음 노드까지 거리를 구해준다. 이 거리를 구하는 이유는 재방문시 더 짧은 최단거리가 있으면 업데이트 .. 2020. 8. 7.
[Summer/winter Coding ~ (2018)] 스킬트리 https://programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr (풀이) 1. Skill의 우선순위를 정한다. 2. Skill_trees 각 String원소들이 우선순위에 맞는지 확인한다. #include #include #include #include using namespace std; map _map; void check_priority(string skill); bool IsGetSkill(string spell); int solution(string skill, vector skill_trees) { int answer = 0; check_priority(skill); for (int i = 0; .. 2020. 8. 7.
14891 톱니바퀴 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net (풀이) 4개의 톱니바퀴가 회전하는 시뮬레이션 문제이다. 단순히 구현으로 풀었다. 가장 먼저 고려하는 부분은 1)회전이 가능한 톱니바퀴를 어떻게 찾을 것인가. 2)회전은 어떻게 진행되는가. 3)진행이 끝나고 점수를 획득하는 방법 회전이 가능한 톱니바퀴는 1번 톱니바퀴의 세번째 톱니 2번 톱니바퀴의 세번째, 일곱번째 톱니 3번 톱니바퀴의 세번째, 일곱번째 톱니 4번 톱니바퀴의 일곱번째 톱니 를 .. 2020. 8. 7.
15685 드래곤 커브 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커� www.acmicpc.net (풀이) 규칙을 찾는것이 가장 중요하다. 만약 0세대가 0부터라면 1세대는 0,1 2세대는 0,1,2,1 3세대는 0,1,2,1,2,3,2,1 이전 세대의 끝에서부터 처음 인덱스까지 반대숫자를 하나 더해주며 나열해주면 된다. (역순 +1 ) 3이 넘어가면 1이 되므로 모듈 연산자를 통해 보정을 해주었다. #include #include #include using nam.. 2020. 8. 7.
17140 이차원 배열과 연산 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net (풀이) (풀이) 문제의 조건 R연산 , C연산 R연산 행의 개수 >= 열의 개수 C연산 행의 개수 < 열의 개수 풀이 순서 1. 이 문제의 모든 입력값은 3x3 행렬로 시작한다. 2. 가장 먼저 R,C연산에 대해 행 또는 열 정렬을 한다. 3. 행 또는 열에서 (원소수, 횟수)가 몇번 나왔는지 검사한다. 4. 3번에서 원소수, 횟수에 대해 정보를 가지고 있는 vector에 대해 정렬.. 2020. 8. 7.
17142 연구소3 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net (풀이) 연구소2 문제와 유사하지만, 비활성화된 바이러스로 반례가 존재한다. 기존과 같은 풀이방식의 Depth로는 아래의 반례 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 0 2 0 1 1 1 1 1 를 통과하기 어렵다. 따라서 0의 갯수를 카운트하여 확산이 가능한 부분에 대해서 확산 갯수와 0의 갯수가 같아지는 시점에 전부 확산 되었다고 판단. #include #include #i.. 2020. 7. 30.
17141 연구소2 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이�� www.acmicpc.net (풀이) 바이러스를 퍼트릴 수 있는 특정 지점들에서 바이러스가 퍼지는 최단시간을 구하는문제. 바이러스를 놓을 수 있는 공간 E개라고한다면 M개를 살포할 수있으므로 (1> arr[i][j]; if(arr[i][j]==1) check[i][j] = arr[i][j]; if (arr[i][j] == 2) virus_pos.push_back(make_pair(i, j)); } } } 2020. 7. 30.
17471 게리맨더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net (풀이) 문제의 조건 1. 각 구역은 두 선거구중 하나에 포함되어야 한다. 2. 각 구역은 모두 연결되어 있어야 한다. 3. 두 구역으로 나누었을때 두 구역의 인구차의 최소값을 구하라. 문제의 첫 번째 조건을 만들기 위해 백트래킹을 이용한 조합을 사용하였다. divide_zone(int cnt, int idx, int limit) check_choice[]의 T구역은 true, F구역은 false로 구분, 두 선거구중.. 2020. 7. 27.
728x90