https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 네트워크는 아래의 리스트에 맞게 연결되어 있고 연결된 네트워크는 같은 네트워크 상에 존재한다. 컴퓨터 개수가 n, 연결에 대한 정보가 담긴 2차원 배열이 있다고 할 때 네트워크 개수를 구하라. 3 [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 2 3 [[1, 1, 0], [1, 1, 1], [0, 1, 1]] 1 for문을 통해 Check가 False일 때 해당 네트워크를..
https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 완전 탐색을 활용하여 문제를 해결함 최소 필요 피로도와, 소모 피로도가 존재하고 k가 최소 필요 피로도보다 높아야 던전에 들어갈 수 있으며 k는 k-소모피로도로 변한다. 위의 규칙을 따라 유저가 탐험할 수 있는 최대 던전 수를 구하는 문제이다. DFS 문제이기 때문에 던전 탐색을 Check로 만들었고 dungeons이 아래와 같이 탐색하게 함 80 [[80,20],[50,40],[30,..
https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 n개의 음이 아닌 정수가 있을 때, 정수들의 순서를 바꾸지 않고 타겟 넘버 만드는 경우의 수 구하기 -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 재귀 함수를 통해 [+,-] 두 개의 리스트를 만들어 각 branch에서 앞의 수에 누적으로 자신의 수를 더하고 빼서 문제를 품 num_target = [..
백트래킹(Backtracking) 비선형으로 구성된 자료구조의 모든 경우의 수를 전부 고려하여 해를 찾는 도중 막히면 되돌아가서 해를 찾는 기법 최적화 문제와 결정 문제를 푸는 방법 가지치기(Prunning)를 통해 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 이동하며 가지치기를 얼마나 잘하는지에 따라 효율성이 결정됨 DFS https://pasongsong.tistory.com/240 [알고리즘] 너비 우선 탐색 BFS Breadth First Search BFS 너비 우선 탐색 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식 DFS는 깊이 우선 탐색으로 정점의 자식들을 먼저 탐색하는 방식 BFS 방식 : A -> B -> C -> D -> G -> H -> I -> E -> F -> J 한 단..
https://school.programmers.co.kr/learn/courses/30/lessons/86052 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 각 칸마다 S, L, R이 적여있고 이 격자 빛을 쏘았을 때 몇 개의 사이클이 있고, 각 사이클의 길이가 얼마인지 알고 싶음 ["SL", "LR"]가 있을 때 [16]이 나온다. DFS에서 사용하는 check를 활용하여 문제를 해결하고자 함 모든 경로를 탐색해야 하기 때문에 각 입구를 list로 만들어서 check 하는 형식으로 똑같은 곳에 사이클이 생기는 것을 방지했다. S, L, R..
https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 DFS를 이용하여 섬을 만나면 주변 섬 전체를 탐색하도록 설계하였다. need_visit에는 탐색해야하는 값의 (행, 열)이 들어있고 pop을 통해 빼낸다. visit을 따로 설정해두어 이미 둘러본 섬은 다시 둘러보지 않도록 설계한다. pop으로 꺼낸 섬의 주변을 탐색하고 섬이 있다면 need_visit에 추가하여 붙어있는 섬을 다 탐색하도록 한다. def solution(maps):..
DFS 깊이 우선 탐색 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 Node들의 자식을 타고 내려가며 순회함 DFS 방식 : A -> B -> D -> E -> F ->C -> G -> H -> I -> J 구현 코드 # 그래프 생성하기 graph = dict() graph['A'] = ["B", "C"] graph['B'] = ["A", "D"] graph['C'] = ["A", "G", "H", "I"] graph['D'] = ["B", "E", "F"] graph["E"] = ["D"] graph["F"] = ["D"] graph["G"] = ["C"] graph["H"] = ["C"] graph["I"] = ["C", "J"] graph["J"] = ["I"] def bfs(gr..
