https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 Level 3 정도의 문제지만, 백준으로 치면 다른 트릭이나 복잡한 구현이 없는 기본적인 bfs/dfs 문제라서 골드 4-5정도 될 것 같다. 아무튼, 이 문제의 풀이에 대해 알아보자 문제에서 찾고자 하는 것은 '연결된 영역의 개수' 라고 할 수 있다. n은 반드시 1 이상, 즉 주어진 그래프에는 노드 1이 반드시 존재함을 알 수 있다. 1을 기점으로, 재귀 형식의 dfs를 이용해 아..
https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr BFS/DFS 연습용 문제이다 예시가 4,1,2,1이라고 하면, 4 -> 5 or 3 에서 5 -> 6 or 4 와 3 -> 4 or 2 ,,, 와 같은 식으로 갈 수 있다. from collections import deque def solution(numbers, target): answer = 0 q = deque() q.append([numbers[0],0]) q.append([-1*num..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프인지 아닌지를 판단하는 문제이다 정점 하나하나씩 bfs 탐색을 진행해주는데, 주의해야 할 점은 그룹을 지어야 한다는 것이다! (왜 bfs를 한번에 돌리지 않고, 정점 하나씩 해주냐면 입력이 어떻게 들어올 지 모르기 때문이다. 비연결 그래프가 존재하는 경우, 시작점과 연결되지 않은 곳은 탐색할 수 없기 때문에 모든 정점에 대해 탐색해주는 것이다) 트리를 하나 떠올려 보자. level 0 ..
https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 일단 이 문제는 입력도 은근 까다롭기 때문에 ㅋㅋ 입력부터 잘 받아보자. 무방향이지만 아래 코드처럼 입력받을 필요는 없다! 어차피 입력값에서 다 주어지기 때문이다. tree[a].append((b,c)) tree[b].append((a,c)) 그리고 이 문제는 '트리의 지름' 이란 키워드에 대한 이해가 필요하다. 단순히 임의의 한 노드에서 가장 멀리 있는 노드를 구하는 것이 아니라..
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 간단한 dfs문제이다. bfs로도 풀 수 있지만 dfs 연습중이라 그냥 dfs로 풀었다 무방향이므로 양쪽으로 모두 다 입력받아주고, 방문하지 않은 노드에 대해서만 dfs 탐색을 진행해준다. dfs 탐색이 끝난다면, 하나의 '연결요소'에 대한 탐색이 끝난 것과 동일한 것이므로 정답 개수를 +1 해주면 된다! import sys sys.s..
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 백트래킹을 이용한 브루트 포싱이다. 단어의 앞뒤가 항상 anti, tica로 이루어져 있으므로 최소 5개의 글자 (a,c,i,n,t) 는 알고 있어야 한다. 그리고 이제 남은 알파벳 21개 중에서 추가로 학습을 진행한다. 이 때 알고 있는 글자의 수가 k개가 될 때 까지만 진행한다. 만약 depth가 k에 도달한다면, 입력으로 주어진 단어를 탐색하면서 모르는 글자가 나올 경우 탐색을 종료하..
