문제 내용 요약 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다. 따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다. solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 ..
문제 내용 요약 DFS, BFS를 공부하던중 '동빈나'님의 자료를 보며 DFS, BFS를 공부했다.해당 문제에대한 해석에는 DFS를 통한 풀이방법만 제시해서 BFS로도 풀줄 알아야될거 같아서 BFS로 만들어 풀어봤다. 문제 원리파악 일단 이 문제에서 숫자 0끼리 묶여있는 그래프라고 생각하고, 연결이 되어있지 않은 총 그래프의 갯수를 생각한다. 위 그림에서는 총 3개의 그래프를 만들 수 있다. 위의 입력 맵을 예시로 [x,y]값을 [0,0]부터 [3,4]까지 순차탐색하면서 최초 0을 방문하면 연결된 그래프를 모두 1로 바꾸고, Count 1을 더하는 방식으로 진행한다. 만약 순차탐색을 하면서 grpah[x,y]값이 1일 경우 Pass하는 방식으로 코드를 진행하면 원하는 문제의 답이 나올 것이라고 생각한다...
문제 내용 요약 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 compute..
재귀 함수 정의한 함수안에 정의한 함수를 다시 호출하는 방식 재귀함수를 사용하려면 반드시 함수내의 종료조건을 명시해줘야함 def test_recursive(i): # 종료되는 조건을 반드시 추가해야 종료됨 if i == 10: return print("재귀함수") test_recursive(i+1) 예를들어 백준문제 N-Queen문제같이 백트래킹 문제풀때 활용 9663 문제 python N-Queen [백준-골드4/백트래킹] 문제 내용 요약 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 문제 원리파악 yoon1seok.tistory.com 유클리드 호제법 예제 두 수의 최대공약..
문제 내용 요약 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 문제 원리파악 백트래킹 문제인 만큼 어떻게 백트래킹 되는지 방식을 알아야 된다. 재귀함수 활용한 DFS 탐색 방식 def Back_Track(count, col, i): if count == 0: # 재귀함수를 돌면서 0일때 종료됨 break count -= 1 # 트리로 따지면 가장 안쪽으로 탐색하는 방식 for j in range(1,5): col[i] = j Back_Track(count, col, i+1) col = [0,0,0,0,0] Back_Track(5, col, 0) 문제풀이에 사용되는 For문안의 ..
문제 내용 요약 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해..
