본문 바로가기
반응형

조합8

[코드트리] 팩맨 (삼성 SW 역량테스트 2021 하반기 오후 1번) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 https://www.codetree.ai/training-field/frequent-problems/problems/pacman 팩맨 문제 풀이는 BOJ 23290 : 마법사 상어와 복제와 비슷하지만, 방향의 정의가 다르다./* 0, ↑, ↖, ←, ↙, ↓, ↘, →, ↗ */int dr8[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };int dc8[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 }; 주어진 방향이 반시계 방향이라서, 반시계 방향과 관련된 구현도 수정하였다. int m; for (m = 0; m   전체 코드는 다음과 같다.#include int T;int M, T.. 2024. 6. 9.
BOJ 23290 : 마법사 상어와 복제 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) https://www.acmicpc.net/problem/23290 먼저, 문제 아래에 설명된 상어의 이동 방법에 대해 구현해보자.상어의 이동 방법은 상하좌우 = 1, 2, 3, 4 중 3개를 선택하는 중복 조합이다따라서 43 = 64가지 방법을 미리 구현해둔다.N과 M (4) - 중복 조합 코드에서 outputList를 고치면 된다.상하좌우에 대한 경우의 수는 moveList에 저장해둔다.typedef struct st2{ int move[3];}MOVE;MOVE moveList[70];int mcnt;int list[10];void o.. 2021. 11. 6.
BOJ 17471 : 게리맨더링 (A형 상시) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17471 A형에서 그래프는 2차원 배열로 만들면 대부분 충분하다. 제시된 N이 매우 작기 때문이다.(N이 매우 큰 그래프는 링크드 리스트를 이용해 그래프를 만들어야 한다.) 만약 1번 구역과 2번 구역이 인접하다면, MAP[1][2] = MAP[2][1] = 1, 그렇지 않다면 0이 된다.people 배열에는 구역의 인구 수를 저장한다.#define MAX (10 + 5)int N;int MAP[MAX][MAX];int people[MAX];void input(){ scanf("%d", &N).. 2021. 4. 28.
BOJ 17135 : 캐슬 디펜스 (A형 상시) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17135  먼저 궁수가 탐색해야할 우선순위를 구해보자.아래의 그림은 D = 1, 2, 3인 경우 궁수가 탐색해야하는 순서다.적이 가장 가까울 경우 가장 왼쪽에 있는 적을 공격한다고 하였으므로, 거리가 가장 가까운 앞을 보고, 그 다음 거리부터는 왼쪽/가운데/오른쪽 순서대로 탐색한다. D = 4인 경우, 규칙이 점점 보인다. 위의 탐색 순서를 궁수를 기준으로 r, c로 나타내면 아래와 같다. 좌표 r은 -1부터 시작해서 감소하다가 다시 증가한다.좌표 c는 처음엔 0이며, 그 다음 주기에는 -1.. 2021. 4. 11.
BOJ 15657 : N과 M (8) - 중복 조합 combinations with repetition SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15657  N과 M (5)와 마찬가지로 input에 대해서 N과 M (4)의 코드를 조금만 수정하면 된다.#include int N, M;int list[10];int input[10];void outputList(){ for (int i = 0; i input[k]) { int tmp = input[i]; input[i] = input[k]; input[k] = tmp; } } } DFS(0, 1); return 0;} 2021. 2. 22.
BOJ 15655 : N과 M (6) - 조합 combination SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15655  N과 M (5)와 마찬가지로 input에 대해서 N과 M (2)의 코드를 조금만 수정하면 된다.#include int N, M;int list[10];int input[10];void outputList(){ for (int i = 0; i input[k]) { int tmp = input[i]; input[i] = input[k]; input[k] = tmp; } } } DFS(0, 1); return 0;} 2021. 2. 22.
BOJ 15652 : N과 M (4) - 중복 조합 combinations with repetition SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15652 중복 순열에서 순서가 의미가 없다면, 중복 조합이 된다. 중복으로 선택은 가능하되, 다음으로 선택해야할 숫자가 작아서는 안되므로, DFS에 현재 선택한 값을 그대로 넘겨주면, 다음 Level에서는 작은 값을 선택할 수 없게 된다.#include int N, M;int list[10];void outputList(){ for (int i = 0; i 2021. 2. 21.
BOJ 15650 : N과 M (2) - 조합 combination SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15650  N과 M(1) - 순열이 줄 세우기 문제라면, 이번 문제는 조합문제이다. 1 2 3 4 = 1 2 4 3 = ... = 4 3 2 1 이 모두 중복으로 취급된다.즉, 순서가 상관이 없다. 그리고 사전 순으로 증가하도록 출력해야하므로,DFS Level에서 start를 기억해두고, start에서 N까지만 list를 작성하도록 만들면 된다. list에서 선택한 번호를 저장하고, 선택한 번호 + 1을 다음 DFS에 넘겨주면 된다.이렇게 되면, 선택한 번호는 다음 DFS Level에서 선택할 수 없으므로, visit 배열이 필요가 없다.#include int N, M;i.. 2021. 2. 20.
반응형

티스토리툴바