본문 바로가기

Algorithm/DFS&BFS&백트래킹&재귀52

[프로그래머스 lv 3] 섬 연결하기 사용 언어 - Python3 문제 - 섬 연결하기 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 크루스칼 알고리즘 가중치를 기준으로 정렬 후 유니온 + 파인드 가중치를 기준으로 정렬 = costs.sort(key=lambda x:x[2]) 내 노드에서 연결 된 모든 선 확인 = 부모 찾기 _find(x) 같은 집합으로 묶어주기 = 사이클 안생기게 처리 _union(a,b) def _find(x): while par[x] != x: # 부.. 2023. 12. 20.
[프로그래머스 lv 3] 퍼즐 조각 채우기 사용 언어 - Python3 문제 - 퍼즐 조각 채우기 https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 큐, BFS 채워야할 빈칸과 도형을 분할해서 생각하기 1. def find_board(board,f) empty_blocks = find_block(game_board,0) # game_board의 빈공간(0) 위치 찾기 puzzles = find_block(table,1) # table의 블럭(1) 위치 찾기 방문하지 않았고 해당 위치.. 2023. 12. 18.
[프로그래머스] PCCP 모의고사 2회 4번 보물 지도 사용 언어 - Python3 문제 - 보물 지도 https://school.programmers.co.kr/learn/courses/15009/lessons/121690 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 큐, BFS 이동하면서 신발 사용안했다면 신발사용한 nx,ny로 이동 1. from collections import deque 2. dx,dy 방향 상하좌우 이동 3. graph(n*m) 설정, hole 구멍위치는 1이고 나머지는 0 4. visited(n*m*2) 설정, 신발사용여부 O/X 포함한 방문여부 설정 5. 시작 queue .. 2023. 12. 18.
[프로그래머스 lv 5] 방의 개수 사용 언어 - Python3 문제 - 방의 개수 https://school.programmers.co.kr/learn/courses/30/lessons/49190 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 대각선 판별을 위해 이동거리를 1이 아닌 2라고 생각하기 방문여부, 경로가 겹치지 않았는지 확인 0. from collections import defaultdict : dic클래스의 서브 클래스, 유사딕셔너리 : 외부함수라 import 필요 visit = defaultdict(list) : 방문여부를 빈리스트로 유사딕셔너리로 설정 1. x,y.. 2023. 12. 11.
[프로그래머스 lv 3] PCCP 기출 4번 수레 움직이기 사용 언어 - Python3 문제 - PCCP 기출 4번 수레 움직이기 https://school.programmers.co.kr/learn/courses/30/lessons/250134?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 BFS 탐색 다양한 경우의 수 생각하기 1. 빨강 시작점/끝점, 파랑 시작점/끝점 위치 찾기 2. 방문여부 visited 리스트 생성, 시작점은 방문 O (True)로 설정 3. q 빨강 시작점x,y / 파랑 시작점x,y / 빨강방문여부 / 파랑방문여부 / cnt 4. 경우의 수 4.1. .. 2023. 12. 11.
[프로그래머스 lv 3] 순위 사용 언어 - Python3 문제 - 순위 https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 해당 사람에게 이기고 진 사람 수 확인하기 플로이드-와샬 알고리즘 A->B, B->C ===> A->C 1. 이기고 진 관계 설정하기 dist_array = [[0]*n for _ in range(n)] dist_array[이긴사람][진사람] = 1 2.i가 k를 이겼고, k가 j를 이겼다면, 자동으로 i는 j를 이겼다. 3번의 반복문을 통해 dis.. 2023. 12. 8.
[프로그래머스 lv 3] 가장 먼 노드 사용 언어 - Python3 문제 - 가장 먼 노드 https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 구현 연결된 노드를 모두 확인해주면서 max(거리)인 경우를 카운트하기 1. 연결된 노드 정보를 저장해준다. 예) graph[1번노드] = 3번 노드 , grpah[3번 노드] = 1번 노드 2. 각 노드를 기준으로 최단거리를 저장할 distance 리스트를 생성한다. 거리는 0 일수도 있으니 디폴트값을 -1로 설정한다. distance =.. 2023. 12. 8.
[프로그래머스 lv 2] PCCP 기출 2번 석유 시추 사용 언어 - Python3 문제 - PCCP 기출 2번 석유 시추 https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 DFS 알고리즘 x,y 좌표를 nx,ny로 이동하면서, 가장 깊게까지 들어갈 수 있는 min_y, max_y를 찾기 from collections import deque def solution(land): answer = 0 n = len(land) # 세로 m = len(land[0]) # 가로 # 이동 dx = [1,-.. 2023. 12. 6.
[백준] 1197번 최소 스패닝 트리 (프림, 크루스칼) 사용 언어 - Python3, PyPy3 문제 - 1197번 최소 스패닝 트리 Minimum Spanning Tree 최소한으로 뻗어나가는 트리 - 프림 = 다익스트라 이용해서 MST 구하는 문제 - 크루스칼 = 유니온파인드 이용해서 MST 구하는 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 정답 최소 스패닝 트리 알고리즘 트리의 기본 조건 : 사이클 발생 X 방법1. 프림 다익스트라를 이.. 2023. 11. 8.
[백준] 1717번 집합의 표현 (유니온 파인드 문제) 사용 언어 - Python3, PyPy3 문제 - 1717번 집합의 표현 유니온 파인드 union & find 두 노드, 두 숫자, 두 무언가가 같은 집합 안에 있나요? https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 정답 유니온 파인드 x==0 인 경우, 두 집합 합치기 _union(a,b) - 부모 리스트 생성 par = [i for i in range(n+1)] 부모는 자기자신으로 시작 - 관계 생성 .. 2023. 11. 6.

티스토리툴바