상상쓰

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net DFS 알고리즘을 이용하여 모든 경우를 구하여 최댓값과 최솟값을 반환하면 된다. 연산자의 개수는 len(A) - 1 이기 때문에 rf() 의 인자 i 가 len(A) 일 때 하나의 계산이 끝나므로 그때의 값을 비교하면 된다. o[] 로 해당 연산을 할 수 있는지 알 수 있다. rf() 가 시작할 때 해당 연산자를 썼다는 의미로 -1을 해주고 ..

https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net A에 포함된 문자열을 한 개 이상 붙일 수 있으므로 dp[index] 가 1이면 이미 재귀함수로 A의 문자열로 S를 만들 수 있는지 확인하고 있으므로 무시해도 된다. DFS 알고리즘으로 S = 'softwarecontest' A = ['software', 'contest'] 라면 1) index = 0 (dp[0] = 1) : softwarecontest(= S[0:]) 와 ..

https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr DFS 알고리즘으로 풀었고 리프 노드를 시작으로 하여 해당 노드의 전선 연결을 끊었을 때 남아 있는 송전탑의 개수(하위 노드의 개수 + 1)를 부모 노드의 result[] 에 더했다. (리프 노드는 result[] = 1) 만들어진 result[] 와 n - result[] 의 차이의 절대값과 result[0] 중 최솟값을 result[0] 으로 잡고 최종적으로 result[0..

https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net DFS 알고리즘, 재귀함수를 이용하여 괄호를 추가할 수 있는 모든 경우를 나타내었다. 3+8*7-9*2 를 예로 들었을 때, rf 함수에 str(l) + o + l_ + o_ + r_ 를 출력해보면 0+(3+8)*7-9*2 0+(3+8)*(7-9)*2 0+(3+8)*7-(9*2) 0+3+(8*7)-9*2 0+3+(8*7)-(9*2) 0+3+8*(7-9)*2 0+3+8*7-(9*2) (..

https://programmers.co.kr/learn/courses/30/lessons/72416 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr DFS 와 동적 계획법을 이용하여 풀 수 있을 거라고는 생각했는데 dp 배열을 구현하기가 어려워서 다른 블로그를 참고하여 풀어나갔다. dp[i][0] : i 가 참석하지 않았을 때의 최솟값, dp[i][1] : i 가 참석했을 때 최솟값으로 정의하고, 기본값으로 dp[i][1] = sales[i-1], dp[i][0] = 0 으로 시작한다. 리프 노드부..

https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr DFS 알고리즘을 통하여 0 ~ n-1 을 분할한다. 컴퓨터의 번호가 check 안 되어 있을 때(check[i] == 0), 재귀함수를 통해 이어져 있는 컴퓨터들의 번호를 다 check 해주고(check[i] = 1) answer 에 1을 더해준다. def solution(n, computers): answer = 0 check = [0] * n for ..

https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr DFS 알고리즘을 구현하여 가장 하위에 있는 판매원부터 추천인한테 이득을 분배하고 계산된 값을 가지고 더 상위의 추천인한테 이득을 분배하면 된다. 예를 들어 center - S - A (a원), B (b원) 로 나타냈을 때 S 는 (a // 10 + b // 10) 이다. 여기서 center 는 ((a // 10) // 10 + (b // 10) // 10..

https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr dfs 알고리즘을 이용하여 전위 순회와 후위 순회를 구하려고 하였다. dfs 알고리즘을 사용할 수 있도록 부모와 자식 관계를 나타내는 tree 라는 함수를 사용해 dic 을 구성하였다. 1. nodeinfo 에 각 번호를 넣고 y 에 대하여 내림차순, 다음으로 x 에 대하여 오름차순으로 정렬하였다. 2. tree 라는 함수는 7 이 root 라면 7 의 y 값보다..