본문 바로가기
  • 시 쓰는 개발자

전체 글338

1182 부분수열의 합 💡문제 분석 요약n개의 정수와, 목표합 s를 받아서 부분 수열의 합이 s가 되는 경우의 수를 구한다.💡알고리즘 설계DFS를 쓰지 않아도 풀 수 있어보인다. N의 개수도 20으로 그리 크지 않아서 for문으로 모든 경우를 다 구해도 되지 않을까 생각이 들었다.combination을 이용하여 1개, 2개, 3개 ..... n개를 뽑는 경우를 모두 구한 후, sum이 s와 같은지 비교하여 개수를 구한다.💡코드import sysfrom itertools import combinations as cbinput = sys.stdin.readlinen, s = map(int, input().split())lst = list(map(int, input().split()))# 부분 수열의 합이 s가 되는 개수를 구.. 2024. 7. 25.
6987 월드컵 💡문제 분석 요약월드컵 조의 경기 결과를 보고, 해당 결과가 나올 수 있는 결과인지 아닌지 판단한다.경기 결과는 4개 조에 대해서 주어진다.한 조에 6팀이 속한다.💡알고리즘 설계백트래킹으로 모든 경우의 수를 다 구할까 생각했었다.이는 3^15 경우의 수인데 이론상 가능하다고 생각했다.💡코드import sysfrom itertools import combinationsinput = sys.stdin.readlineanswer = []# 가능한 모든 게임 조합 - 총 15개 게임 (0,1), (0,2), ... , (4,5)game = list(combinations(range(6), 2))def backTracking(round): global ans if round == 15: # 모든 .. 2024. 7. 24.
15651 N과 M (3) 💡문제 분석 요약N, M 값을 받고 1 ~ N까지의 숫자중에서 M개의 숫자를 중복 허용하여 출력한다.오름차순으로 출력한다.💡알고리즘 설계이전에 풀었던 N과 M(9) 문제처럼, DFS를 이용한다.m개의 원소가 모이면 print해주는 탈출조건을 작성해준다.💡코드n, m = map(int, input().split())s = []def backTracking(): # DFS를 이용함 if len(s) == m: # m개가 모였다면 출력 print(*s) return for i in range(1, n+1): # m개의 숫자가 모이는 과정인데, prev를 통해 중복 출력을 방지함. s.append(i) # 1~n까지 값을 넣는 것이기 때문에 굳이 list .. 2024. 7. 23.
15663 N과 M (9) 💡문제 분석 요약N개의 숫자 중에서 M개를 뽑아 순열로 출력한다.이때 중복된 숫자는 출력하지 않는다. ex) 4 4 2중에서 1개 출력하면, 2 4만 출력됨.💡알고리즘 설계DFS 사용 : 백트래킹은 DFS, BFS 둘 다 가능하지만 재귀를 사용한다는 점과 되돌아온다는 맥락에서 DFS가 더 편하고 적합했다.💡코드n, m = map(int, input().split())lst = sorted(list(map(int, input().split())))visited = [0] * ntemp = []def backTracking(): # DFS를 이용함 if len(temp) == m: # 출력조건. m개의 숫자가 쌓일 때까지 백트래킹을 진행함. 다 모이면 출력 print(*temp) .. 2024. 7. 22.
필독!!) 백트래킹 요약 백트래킹(backtracking)이란?해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법이다. 모든 경우의 수를 대상으로 진행하지만, 실제로는 제한된 조건으로 경우의 수를 한정짓기 때문에, 이론적인 경우의 수보다는 더 적은 실행을 보인다. 탐색하다가 가능성이 없다면(조건에 맞지 않는다면) 바로 돌아가기 때문에 실제로 시간이 N^M만큼 걸리지는 않는다.구현모든 경우의 수 중에서 맞는 경우를 찾는 방법이므로, 구현은 DFS/BFS 둘 다 가능하다. 그러나 되돌아간다는 점에서 DFS와 유사해 구현도 편하다고 한다.DFS와 차이점그럼 백트래킹과 DFS의 차이점은 무엇일까 ??한줄 요약 : 백트래킹은 모든 경우를 탐색하지 않는데, DFS는 모든 경우를 탐색한다. 1. 백트래킹제한 조건을 보.. 2024. 7. 22.
문제풀이 TIP (Test Case) 문제풀이 전, 확인해야하는 것1. input이 어떻게 들어오는지 확인2. 문제의 요구사항이 뭔지 확인3. 어떤 알고리즘을 사용할지 확인4. 제한시간 체크하기5. 슈도코드로 코드 어떻게 작성할지 흐름 써보기 테스트케이스 확인 팁기본적으로 주어지는 테스트 케이스에 속으면 안됨. 다음과 같은 경우를 고려할 것. 1. 비어있거나, 하나만 있는 case2. 첫번째 혹은 맨 마지막 case3. 크기가 굉장히 큰 case4. 양수만 있는, 음수만 있는 case5. overflow가 나는 case6. 중복 값이 들어가는 case 2024. 7. 22.
1743 음식물 피하기 💡문제 분석 요약이전에 풀었던 단지 번호붙이기 문제와 거의 유사했다.한마디로 음식물이 뭉쳐져있으면 커지고, 제일 크게 커진 음식물 크기를 구하는 문제였다.이는 DFS, BFS로 탐색하여 해당 구역에 1이 몇개 있는지 구하는 맥락이다.💡알고리즘 설계BFS, DFS 모두 가능하다.💡코드import syssys.setrecursionlimit(10 ** 6)n, m, k = map(int, input().split())graph = [[0] * m for _ in range(n)]visited = [[0] * m for _ in range(n)]foods = [] # 음쓰들foodWaste = 0 # 음쓰dx = [0, 0, 1, -1]dy = [1, -1, 0, 0]for _ in range(k):.. 2024. 7. 21.
2178 미로 탐색 💡문제 분석 요약N, M이 주어졌을 때 N행 M열에 대해 미로를 탈출한다.미로를 탈출하는 최소 거리를 구한다.💡알고리즘 설계최소의 칸수를 구하는 것이므로 BFS를 시도하면 될 것 같다.⚠️주의) 이동 거리가 모두 1로 동일하다면 그냥 BFS 쓰면 되는데, 그게 아니라면 다익스트라를 사용해야한다 !!!!!💡코드import sysfrom collections import dequeinput = sys.stdin.readlinen, m, = map(int, input().split())maze = [[0] * m for _ in range(n)]for i in range(n): # 미로 초기화 tmp = input().rstrip() for j in range(m): maze[i].. 2024. 7. 20.
1697 숨바꼭질 💡문제 분석 요약n, k가 주어졌을 때 n이 k에게 가는 최단 시간을 측정한다.n은 n-1 , n+1 , 2*n 이렇게 3개의 방법으로만 움직일 수 있다.💡알고리즘 설계최단경로이긴 하지만, DP처럼도 풀 수 있어보였다. n을 2*(n-1) , 2*(n+1), 2*n 이렇게 3개중에 하나로 쭉 이어나가다보면 되지 않을까 했지만 실패했다.결국, 최단경로를 찾는 매커니즘은 BFS이기 때문에 BFS로 접근해야했다.💡코드from collections import dequen, k = map(int, input().split())maxSize = 100000visited = [0] * (maxSize + 1) # 각 위치를 방문했는지 여부 & 해당 위치까지 도달하는 데 걸린 시간# 0이 아니니까 방문했다! .. 2024. 7. 19.
반응형

티스토리툴바