링크: https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 works의 sum이 n보다 작으면 0 return works 배열을 heapq로 만들어 가장 큰 수가 앞으로 오게 만든다. n번 반복하여 works에서 가장 큰 수에 -1을 해준다. 각 자릿수의 야근지수를 구해 더하고 return 구현(실패) import heapq def solution(n, works): # 야근을 하기전에 일이 끝남 if sum(works) < n: retu..
링크:https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 아이디어 미리 카메라의 위치를 한 번 돌아 찾아둔다. 그 좌표를 통해 백트래킹을 진행하여 1~5번 카메라의 조건만큼 for문을 돈다. 각 카메라의 조건이 지정된 순간 감시를 했다고 쳤을 때 사각지대의 갯수를 찾는다. 감시를 하는 경우는 상하좌우 #을 뿌리는 함수를 만들고 각 경우의 마다 필요한 함수를 쓴다. 예) 2번 카메라의 1번의 경우 좌측에 #을 뿌리는 함수와 우측에 #을 뿌..
링크: https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 아이디어 백트래킹을 통해 벽을 세우는 경우를 만듦 그 경우에서 2인 위치를 기준으로 bfs를 진행하여 감염이 된 상태를 만듦 이후 안전지대의 개수를 세고 result 값과 비교하여 더 큰 값을 result에 저장. 구현(pypy정답) import sys input = sys.stdin.readline # 백트래킹 def back(wall): if wall == 3: tmp_li = [mat[:] for..
링크: https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어 백트래킹사용 for문을 돌며 숫자를 선택 방문여부를 확인하며 돌고 다시 이전 깊이로 돌아갈 때 방문여부를 되돌려줘야함 M개의 숫자를 고른 경우의 경로는 print해준다. 시간복잡조 중복을 허용하지 않은 경우니 N!이다 -> 가능! 구현 import sys # 백트래킹 구현 def back(): # 경로를 찾았을 때 출력 if len(check) == m: for i in chec..
백트래킹? 트리방식으로 동작된다고 이해하면 쉽다. 재귀함수를 통해 for문을 돌려 깊이를 마음대로 설정할 수 있음. DFS랑 백트래킹 뭐가 달라? 재귀함수를 통한 dfs랑 백트래킹이 유사하지 않나?라는 생각이 들었다. 둘 다 탐색이지만 원하는 값을 찾기 위한 방법에서 차이가 발생한다. 백트래킹은 불필요한 탐색을 하지 않는다. 경로를 찾아가는 도중에 해가 되지 않을 것 같은 경로에 왔다면 더 가지 않고 되돌아온다. 아래 사진을 보면 느낌이 팍 올 것이다. 되돌아올 때 밑에 노드는 애초 방문하지 않은 것처럼. dfs의 방문처리는 보통 배열을 사용하여 인덱스를 활용한 방문처리를 한다. 하지만 백트래킹은 다시 부모노드로 올라갈 때 이전의 노드들을 방문했다고 생각하지도 않고 진행한다. 그래서 보통 append()..
링크: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 아이디어 큐를 이용한 BFS 재귀를 이용한 DFS 방문처리 배열 하나로 두 번 사 구현(틀림) import sys from collections import deque #dfs def dfs(v): dfs_li.append(v) for i in range(n): if m_li[i][0] == v and not check[m_li[i][1]]: check..
링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 뭔가 말이 헷갈리긴 하는데 쉽게 보면 그래프 탐색인 듯 방문처리 배열 만들고 각 요소마다 bfs를 진행 bfs가 진행될 때마다 count변수 +1 구현 def solution(n, computers): global chk answer = 0 chk = [False]*n for i in range(n): if not chk[i]: chk[i] = True answer += 1 dfs..
링크: https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 dfs bfs 뭘 사용해도 될 듯? dfs를 이용해서 풀어보자 (재귀) ICN부터 dfs탐색 시작 알파벳 순 판별은 대소비교를 통해 진행 지나간 경로는 del 구현(실패) def solution(tickets): # 경로를 저장할 배열 global road road = ["ICN"] # ICN부터 시작 dfs("ICN", tickets) return road # dfs 함수 def..
평소에는 DFS, BFS 둘 중 뭘 써도 풀리는 문제들만 풀었어서 차이점(효율적인 측면)을 명확하게 잘 몰랐다. 그렇게 오늘도 알고리즘 문제를 풀다 갑자기 이 DFS BFS 적용 기준 정리에 필요성을 느껴 바로 실행에 옮기려 한다. BFS, DFS가 뭐야? 내가 알고있는 bfs, dfs는 그래프를 탐색하는 방법으로 알 고 있다. 각 dfs bfs에 대해 간단히 적어보겠다. BFS(너비 우선 탐색) 큐를 사용함 정점에서 가까운 노드들부터 탐색 찾는 노드가 인접할 때 유리 노드가 많을 수록 메모리를 많이 소비 DFS(깊이 우선 탐색) 스택 혹은 재위함수를 사용함 정점에서 가장 깊은 노드까지 들어가며 탐색 그래프의 깊이(depth)가 깊을 수록 빠름 메모리가 적음 언제 뭐 써야해? 공통 단순히 모든 정점을 방..
