본문 바로가기
반응형

dfs66

BOJ 14891 : 톱니바퀴 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/14891  시뮬레이션 문제는 시키는대로 구현하면 된다.이 문제는 연속으로 회전이 발생하므로, DFS로 연속 회전 시켜보자. 먼저 rotate를 구현해보자.톱니의 번호와 방향을 입력받으면 회전하는 함수는 아래와 같이 구현할 수 있다.톱니바퀴 4개와 12시 방향 = 1 부터  8까지(순서대로 시계방향)의 톱니를 넣을 수 있는 2차원 배열을 선언하자.int wheel[5][10]; /* wheel[번호 1~4][각 톱니 1~8] */void rotate(int number, int dir){ int te.. 2021. 2. 21.
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 15651 : N과 M (3) - 중복 순열 permutations with repetition A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15651  중복으로 숫자를 선택 가능하고, 순서도 의미가 있는 중복 순열 문제이다.즉, visit배열로 숫자를 현재 선택했는지 관리할 필요가 없다. 따라서 다음 Level에서도 모든 숫자를 선택할 수 있도록 i = 1 ~ N으로 하면 된다.#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.
BOJ 15649 : N과 M (1) - 순열 permutation A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15649 순열을 구하는 문제이다.서로 다른 N개중에 M을 선택하는 경우의 수를 의미하고 순서가 상관이 있다.그리고 중복이 없어야 한다. N = M이면 팩토리얼이 된다.(서로 다른 N개를 모두 나열하는 경우의 수) 예제 입력 2를 예로 4개 중 2개를 선택해서 줄을 세운다면, 아래의 출력이 나온다.1 21 31 42 12 32 43 13 23 44 14 24 3순서에 의미가 있으므로 1 2 와 2 1이 다르다. 경우의 수 문제는 대부분 재귀 호출로 해결한다. 먼저 첫번째를 선택하면 다음 재귀에서는 선택하지 못하도록 해야한다.따라서 숫자들이 현재 선택된 상태인지 확인하는 .. 2021. 2. 20.
BOJ 14889 : 스타트와 링크 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/14889  N개의 팀 중, N / 2를 선택해야 하는 조합 문제이다.조합 문제에서는 list에 경우의 수를 저장했지만, 여기에서는 visit 배열을 이용해 선택한 팀을 1로 체크하자.그러면 visit = 0인 팀은 저절로 다른 팀이 된다. 마지막으로 선택된 팀(start), 선택되지 않은 팀(link)에 대해 입력받은 표를 보고 점수를 계산해주면 된다.start 팀은 team 배열의 앞에, link 팀은 team[halfN] 부터 저장하자.#include #define MAX (20 + 5)int .. 2021. 2. 19.
BOJ 14888 : 연산자 끼워넣기 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/14888 숫자가 N개 연산자가 N-1개가 있다.연산자는 4종류고, 중복으로 사용이 가능한 경우다.보통 DFS에서 visit(check, used)으로 현재의 값(여기에서는 연산자)을 사용 중인지 확인하고,DFS를 다음 단계로 보낸다.void DFS(int L){ if (/* return 조건 */) return; for (int i = 0; i  visit을 최대 possible까지 허용한다면?아래와 같이 코드를 수정하면 된다.void DFS(int L){ if (/* return 조건 */) re.. 2021. 2. 19.
BOJ 1707 : 이분 그래프 삼성 B형 전체 링크 www.acmicpc.net/problem/1707 그래프를 만들고 DFS나 BFS 탐색을 하면 된다. tc가 K개 있으므로, 초기화를 잘 해줘야 한다. 문제 풀이 방법은 node를 탐색하면서 색칠을 하면 된다. 색칠을 하다가, 이미 색칠이 된 곳을 검사해서 색깔이 다르면 "NO"가 된다. 3 - 2(빨강) = 1(검정) / 3 - 1(검정) = 2(빨강)이 되므로 if (!DFS(p->node, 3 - color)) return 0; 와 같은 방식으로 색칠하면 된다. 1 -1 을 하는 방법도 가능하다. DFS 풀이는 아래와 같다. #include int K, V, E; typedef struct st { int node; struct st *next; }NODE; NODE HEAD.. 2021. 2. 15.
BOJ 14502 : 연구소 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/14502  MAP을 입력받을 때, (0, 0)이 아닌 (1, 1)을 기준으로 잡는다.(0, 0) ~ (N+1, N+1)을 모두 1로 만들고 (1, 1)부터 입력을 받으면, 경계 조건을 신경쓰지 않고, 벽인지 아닌지만 체크하면 된다.void input(){ scanf("%d %d", &N, &M); for (int r = 0; r  이제 MAP을 입력받았으니, 벽을 3개 만들자.벽을 만들 때, 3중 for문을 이용할 수도 있지만, DFS 연습으로, 3단계를 걸쳐 벽을 만들어 보자.void DFS(in.. 2021. 2. 15.
반응형

티스토리툴바