성공을 즐기자

https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr DFS인건 알겠는데 대체 이렇게 푸는 생각을 어떻게 하는거지..? for i in range(len(edges)) : parent = edges[i][0] child = edges[i][1] if vis[parent] and vis[child] == 0 : 위 코드를 통해서 내가 갈 수 있는곳은 다가보는거다. 그러다가 sheep > wolf 라면 답에 양의 숫자를 넣고 늑대가 더 많아진다면 ret..

if ans > val + ( total - tsum ) : return 전체 합에서 tsum(바둑이를 태웠건 안태웠건 지나간 바둑이의 무게) 을 빼면 앞으로 더할 수 있는 바둑이의 무게가 나온다. 여기서 val을 더한 값이 ans보다 작다면 더 할 필요가 없다. 끝까지 가도 어차피 ans보다 작기 때문이다. dfs에 tsum을 인수로 추가하여 시간 초과를 막는다는 것이 흥미롭다. def dfs(idx,val,tsum) : global ans if val > c : return if ans > val + (total-tsum) : return if idx == n : ans = max(ans,val) return else : dfs(idx+1,val+arr[idx],tsum+arr[idx]) dfs(id..

유니온 파인드인줄 알았는데 아니었다. DFS 였다. 그저 A,B,C,D,E 가 각각 한명씩만 친구 관계로 연결되어있는 것을 확인하면 된다. 즉, DFS의 깊이가 4인지 확인하는 문제다. A - B(depth == 1) - C(depth == 2) - D(depth == 3) - E(depth == 4) if finish : return 을 통해 시간을 줄여준다. 이미 finish가 True라면 깊이가 4인 dfs를 돌았다는 것이고 추가로 확인하지않아도 되기 때문이다. 코드 : def dfs(now, depth) : global finish if finish : return # 왔음을 표시 vis[now] = 1 if depth == 4 : finish = 1 return # 친구 목록을 돌면서 for i..

🐾 20220917 행복하고 재밌는 DFS 문제다. ^^ 1,2,3,4 CCTV 마다 볼수있는 방향이 다르다. 이를 미리 cctv_dir으로 설정해 놓는다. 1. 주어진 그래프를 돌면서 cctv가 있는 곳의 위치와 번호를 저장한다. 2. DFS에 그래프와 횟수를 인수로 넘긴다. 2-1. 종료 조건은 모든 cctv를 탐색한 경우이다. 2-2. 현재의 그래프와 동일하지만 객체는 다른 지도를 만든다. (원본 배열의 보존을 위해) [copy.deepcopy이용] 2-3. cctv의 타입에 따라 갈 수 있는 방향을 돌면서 감시가능 영역을 설정한다. 2-4. DFS를 이용해 재귀적으로 탐색할 수 있도록 만든다. 2-5. 원본 배열에서 deepcopy를 통해 감시 전으로 돌아갈 수 있도록 만든다. CCTV를 발견할 ..

🐾 20220918 사다리를 어떻게 생각해야할지 생각이 많았는데 지금으로서는 이렇게 생각하는게 제일 쉽다. (아래 사진 참고) 선을 그을수 있는 candidate를 만든다. candidate를 돌면서 그을수 있다면 그으면서 가장 최소의 check가 True인 값을 구한다. 코드 : def check() : # i 번 세로선의 결과가 i가 나오는지 확인 for i in range(1,n+1) : # 세로선을 돌면서 k = i for j in range(1,h+1) : # 선을 놓을 수 있는 곳을 확인 if line[j][k] == 1 : k+=1 elif line[j][k-1] == 1 : k-=1 if i != k : return False return True # added : 그어진 선 개수, num..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 조합을 이용해서 치킨집들의 조합을 구한다. 이 치킨집들과 집들의 각각 치킨거리를 구해 가장 작은 값을 구하면 된다. 코드 : n,m = map(int,input().split()) mp = [list(map(int,input().split())) for i in range (n)] hs = [] ch = [] cb = [0]*m # 조합 # 선택할 치킨집의 인덱스를 담은 배열..

백트래킹은 경우의 수 중에서 유망하지 않은 것을 거르는 방법으로 이것을 구현한는 방법은 다양하며 BFS, DFS등으로 구현할 수 있다. https://what-am-i.tistory.com/286?category=966524 [삼성SW역량][Python/BOJ] 백준 14889 스타트와 링크(DFS, 백트레킹) https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.ne.. what-am-i.tistory.com 여기 이 스타트와 링크문제의 풀이는 백트래킹 구현을 위해 DFS를 ..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net # depth은 뽑은 사람의 인원수, idx는 뽑은 사람 다음부터 뽑기위해서 저장 💻 코드 : def dfs(depth, idx) : # depth는 사람의 수 global min_diff if depth == n//2 : power1, power2 = 0,0 for i in range(n) : for j in range(n) : if vis[i] and vis[j] : # i와 j가 동시에 우리팀! power1+= ..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net dfs(idx,val) : val 이 기존 값 , idx는 이제 더할 값의 인덱스 다음 dfs는 val에 idx인덱스의 값을 (더하거나 ,빼거나 곱하거나 나눠주고) idx를 1 증가시킨다.) 그래서 처음에 dfs(1, numbers[0]) 를 호출해주는 것이다. numbers[0]을 가장 초기값으로 idx가 1인 값을 선택된 기호로 계산하여 ..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net wall()함수와 bfs() 함수가 있다. 1. wall 함수는 세운 벽의 개수를 인수로 받아 3이 되면 bfs함수를 실행시킨다. 아니라면 연구소를 돌면서 빈칸을 만나면 벽을 세우고 wall함수를 인수 1을 증가시켜 부른다. 2. bfs 함수는 바이러스를 퍼뜨린후 안전영역의 개수를 센다. ans 와 비교하여 가장 큰 안전영역의 개수를 저장한다. 코드 : Score와 virus를 합쳐서 bfs함수로 이름지었다...