PYTHON71 [BOJ] 3980. 선발 명단(Python) / DFS, Backtracking 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 11개의 포지션에 11명의 선수를 채웠을 때, 능력치의 합의 최댓값을 구하는 문제. # 42분 소요. (한 번에 통과, PyPy3 제출 기준 시간 1위 달성했다!) 사용 알고리즘 : Backtracking, DFS 순열 구하기 무난하게 순열 구하는 dfs 재귀로 접근해 가지치기하여 가짓 수를 쳐냈다. 원래 dfs 순열로는 11개 자리에 11명을 각각 다른 자리에 배치하는 경우의 수가 39,916,800개가 나오는데, Backtracking으로 가지치기하면 경우의 수가 1824개로 확연히 준다. perm 함.. 2021. 4. 15. [BOJ] 1941. 소문난 칠공주(Python) / DFS, Backtracking 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 전형적인 Backtracking 문제이다. 내가 매우 취약한 알고리즘.. 이번 주는 백트래킹/DFS 문제를 파보자 사용 알고리즘 : Backtracking / DFS 재귀로 조합 구현 조합으로 접근해야한다는 것을 생각도 하지 못했다. 가짓 수가 너무 많을 것이라 생각했는데, 백트래킹으로 Y를 4번 이상 만났다면 return하여 가지치기로 어느정도 거를 수 있다. dfs 함수로 25개 칸에서 7개 칸을 선택하는 조합을 구현한다. 이 때, 7개 숫자를 리스트로 담는데,.. 2021. 4. 13. [BOJ] 11725. 트리의 부모 찾기(Python) / BFS, DFS 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하는 문제. # 26분 소요 사용 알고리즘 : Stack을 이용한 루트 노드 구하기 Stack을 이용한 기본적인 코드로 아래 주석으로 설명을 대신한다. Stack을 사용해 푼 파이썬 코드는 다음과 같다. (아래 코드에서 stack만 queue로 바꿔 head부터 pop하면 BFS로 푼 코드가 된다.) from sys import stdin input = stdin.readline def solve(): parentNo.. 2021. 4. 12. [BOJ] 1938. 통나무 옮기기(Python) / BFS 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 2021. 4. 11. [BOJ] 14425. 문자열 집합(Python) / Trie 자료구조 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 매주 알고리즘 코딩 & 컴공 전공 스터디를 진행하는데, BFS, DFS, 백트래킹, Brute Force, Greedy 등은 자주 푸니까 매주 한 개씩 새로운 알고리즘을 공부해보자 하여 지난 주 이분탐색에 이어 이번 주는 트라이 자료구조에 대해 한번 공부해보기로 했다. .. 2021. 4. 10. [BOJ] 11967. 불 켜기(Python) / BFS 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 각 방에서 불을 켤 수 있는 곳의 위치가 주어지면 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 불을 켤 수 있는 방의 최대 개수를 구하는 문제이다. 사용 알고리즘 : BFS 너비 우선 탐색 근래 풀어본 BFS 문제 중에 내 기준 가장 까다로운 문제였다.. 처음에 쉬운 문제라고 생각했는데 하다보니 자꾸 꼬이고 잘 안 되어서 다른 분의 블로그를 참고했다. 코드를 .. 2021. 4. 9. 이전 1 2 3 4 5 6 ··· 12 다음
