본문 바로가기

DFS6

[Algorithm] 백준 11724 연결 요소의 개수 | 파이썬 DFS ※ 11724 연결 요소의 개수https://www.acmicpc.net/problem/11724문제 해결 TIP간선 정보를 이용하여 몇개의 그룹이 만들어지는지 출력하는 문제이다. 기본 DFS 알고리즘을 이용하여 풀 수 있고, 주의해야 할 점은 RecursionError가 발생하는 것이다. 1000번 이상의 recursion이 발생하면 recursion error 가 뜨기 때문에 recursionlimit을 변경해주었다. 전체 코드import syssys.setrecursionlimit(10**7)input = sys.stdin.readlineN, M = map(int, input().split())graph = [[] for _ in range(N+1)]for i in range(M): u, v .. 2024. 6. 30.
[Algorithm] 백준 2667 단지번호붙이기 | 파이썬 DFS ※ 2667 단지번호붙이기https://www.acmicpc.net/problem/2667문제 해결 TIP이코테의 음료수 얼려 먹기 문제의 응용 버전이라고 생각하면 된다. DFS를 이용하여 연결된 모든 노드들을 방문하고 count를 해준다. 집이 있는 곳이라면, 문제에 나와 있는 것처럼 단지번호를 붙여준다. (집의 유무인 1과 헷갈리지 않기 위해 단지번호는 2부터 붙여주었다.) 집을 모두 방문한 후 그래프의 최종 상태는 마지막 주석을 확인하기 바란다. 전체 코드N = int(input())graph = []for i in range(N): graph.append(list(map(int,input())))#graph = [[0, 1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0, 1].. 2024. 6. 26.
[Algorithm] 백준 14888 연산자 끼워 넣기 (삼성전자 SW 역량테스트 기출문제) | 파이썬 ※ 14888 연산자 끼워 넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 첫번째 문제 풀이 (시간 초과) 문제를 보고 먼저 생각해낸 해결방법은 1. 모든 조합 가능한 연산자 조합을 func_possible 리스트에 담는다. ex) func_possible=[['+', '*'], ['*', '+']] 2. 연산자 조합을 하나씩 꺼내서 숫자 배열과 계산한 후 answer_possib.. 2024. 4. 13.
[Algorithm] DFS(Depth-First Search,깊이 우선 탐색) DFS란? 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다. DFS의 특징 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다. 가중치가 주어지거나 특정 경로를 찾아야 할 때 DFS 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 스택을 이용한 DFS 동작과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 .. 2024. 1. 5.
[Algorithm] DFS 프로그래머스 92343번 양과 늑대 | C++ ※ 2022 KAKAO BLIND RECRUIMENT : 양과 늑대 코딩테스트 연습 - 양과 늑대 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2022.09.01 - [c++/DFS&BFS] - [Algorithm] DFS(Depth-First Search,깊이 우선 탐색) 프로그래머스 92342 [Algorithm] DFS(Depth-First Search,깊이 우선 탐색) 프로그래머스 92342 DFS란? 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 .. 2022. 9. 23.
[Algorithm] DFS 프로그래머스 92342 양궁대회 | C++ ※ 92342 양궁대회 코딩테스트 연습 - 양궁대회 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr #include #include using namespace std; int maxDiff = 0; //최대 점수차 //최대 점수차와 현재 점수차가 동일한 경우 bool compare(vector ryan, vector &answer) { //작은점수부터 화살수를 비교 🠒 현재값이 작은점수에 화살수가 더 많다면 true for(int i = 10; i >= 0; i--) { if(ryan[i] > an.. 2022. 9. 1.

티스토리툴바