DFS21 [BOJ] 6603. 로또(Python) / DFS www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 간단한 DFS로 조합(Combination)을 구현한 문제다. # 소요시간 12분 lottos에 담긴 숫자들 중 순서를 고려하지 않고 6개를 뽑아 차례로 출력한다. 이미 배열은 오름차순으로 되어있기 때문에 그대로 이미 뽑혔는지 확인해주며 뽑히지 않았다면 뽑은 표시 후 다음 자릿수에서 탐색한다. depth == 6이 될 때 출력한다. 파이썬 코드는 다음과 같다. import sys input = sys.. 2021. 3. 17. [BOJ] 9466. 텀 프로젝트(Python) / DFS www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 꽤 까다로웠던 DFS 문제였다. 각 학생이 함께 프로젝트 하고 싶은 사람들 지목하고 지목을 한 사람들끼리 사이클을 이루는지 여부를 파악하여 팀을 이루지 못한 학생들의 수를 계산해야 한다. DFS를 이용하여 1번 학생부터 n번 학생까지 방문표시하며 지목한 다음 학생의 번호를 차례대로 확인한다. 이 때, 사이클 리스트에 넣는데, 다음 숫자가 이 리스트에 있다면 사이클 이루는 경우이므로, 전체 학생의 수에서 사이클을 이루.. 2021. 3. 9. [BOJ] 2661. 좋은 수열(Python) / Backtracking www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 깔끔한 Backtracking 문제였다. 1시간 22분 소요 Backtracking은 제약조건 만족문제에서 해를 찾는 방법이다. 개념 : 여러가지 경우의 수가 있는 문제에서 특정조건을 만족하는 찾는 데 있어, 조건을 탐색하다가 어느 순간 조건이 맞지 않는 것으로 판단되면 그 쪽의 경우의 수는 더이상 체크하지 않고 다른 경우의 수를 체크하는 것이다. 일종의 문제 푸는 전략으로, 알고리즘은 아니다. 고려할 수 있는 경우의 수를.. 2021. 3. 7. [SWEA] 4013. 특이한 자석(Python) / DFS swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 난이도가 낮은 편에 속하는 SW Expert Academy 삼성 SW 역량 테스트 모의 문제이다. 41분 소요로 워낙 많이 풀어본 문제라 오래 걸리지 않았다. DFS의 구조를 익힌 것이 도움이 됨 dfs 함수 안에서 num이 3보다 작을 때와 0보다 클 때를 모두 봐야 해서 둘다 if 조건문을 걸어줘야 한다! 오른쪽/왼쪽 방향 살피기(자성 같거나 달라서 회전할 수 있는지 여부 확인하며 재귀로 넘기기) 마지막에 자.. 2021. 3. 7. [BOJ] 1759. 암호 만들기(Python) / DFS www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net DFS 알고리즘과 combination 모듈을 활용한 것 두 가지 방법으로 풀어보았다. 물론 조합(Combination)을 구한다는 본질은 같다. 파이썬 풀이는 다음과 같다. 방법 1 - dfs로 comb 함수 구현. 시간은 148ms 소요 import sys input = sys.stdin.readline def comb(depth, k, temp): if depth == L: vowel = 0 for s in t.. 2021. 3. 4. [Programmers] 단어 변환(Python) / DFS 프로그래머스 고득점 KIT > 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > Level 3 단어 변환 문제이다. programmers.co.kr/learn/courses/30/lessons/43163?language=python3 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr DFS를 먼저 떠올렸고, 계속 생각만 하다가 결국 코드로 구현하지 못하고 다른 사람의 코드를 참고했다. 참고 링크 : khann.tistory.com/79 프로그래머스 단어 변환.. 2021. 2. 23. 이전 1 2 3 4 다음
