오뚝이개발자

문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 나의 풀이 DFS와 DP가 합쳐진 유형의 문제이다. 시작지점이 정해진 것이 아니므로 각 지점을 시작지점으로 했을 때 최장거리를 계산해 이들 중 다시 가장 큰 값을 답으로 출력하는 문제이다. 그냥 단순히 모든 지점을 시작점으로 해서 DFS로 탐색해도 되지만 이미 했던 연산을 중복해서 계산하므로 시간초과가 난다. 따라서 DP를 사용해 해당 지점을 시작점으로 했을 때 갈 수 있는 최장경로..

DFS를 활용해 connected component의 갯수를 구하는 것이 필요할 때가 있다. 이럴 땐 탐색을 하면서 각 unit별로 구분을 해서 갯수를 카운트 해주면 된다. 정확히는 이를 union find 알고리즘이라고 한다. 예제를 통해 이해해보자. 아래 문제는 프로그래머스에 수록된 문제이다. programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr def dfs(start, n, visited, computers): fo..

DFS(깊이우선탐색)는 BFS와 함께 그래프를 탐색하는 알고리즘 중 하나이다. DFS는 스택으로 구현할 수 있다. 하지만, 스택을 사용하지 않고도 재귀로 충분히 구현이 가능한데 컴퓨터에서 함수 호출의 과정이 스택으로 구현되는 것을 생각해보면 이해가 될 것이다. DFS, BFS 모두 인접행렬과 인접리스트 두 가지로 구현할 수 있다. 인접행렬로 구현할 경우 특정 item에 접근해 연결성 여부를 검사하는 것은 빠르지만 무조건 O(n^2)만큼의 메모리가 필요하다. 연결리스트를 사용한 인접리스트로 구현하는 경우 메모리 사용을 줄일 수 있지만 특정 item에 접근해 연결성 여부를 검사하는 과정이 좀 느릴 수 있다. 하지만 데이터가 많지 않은 경우 접근에 필요한 시간이 많이 소요되는 것은 아니므로 연결리스트를 사용해..

그래프란? finite set of vertex(V)와 edge(E)로 이루어진 것 - graph G : (V,E) Edge(간선)란? 집합 E는 VxV의 subset이다. 일종의 relation이라 볼 수 있다. directed graph(digraph) vs. undirected graph 그래프에서 방향성이 중요한지의 여부에 따라 구분 path란? 그래프에서 node의 sequence다. 단, 각 노드를 연결하는 edge가 있어야 함 Connected graph vs. Disconnected graph connected graph : 모든 노드 사이에 path가 존재(disconnected는 그 반대) disconnected graph는 여러 개의 connected component로 구성 그래프에..

문제 programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 풀이 처음엔 단순한 문제인줄 알고 DFS를 사용하지 않고 풀어보려 했다. 내가 생각한 방식은 이러했다. 출발점이 ICN인 것들 추출해서 도착점 알파벳 순으로 앞서는 것은 선택한다. 1에서 선택한 경로의 도착점이 출발점인 것을 골라 알파벳순으로 비교하고 선택하는 과정을 반복한다. 그런데 문제는 위와 같은 방법으로 풀이했을 때 반례가 존재한다는 것이다. [["ICN","JFK"],["ICN","..

문제설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i..

문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 생각의 흐름 전형적인 DFS 문제이다. 문제의 요점은 A-B, B-C, C-D, D-E인 친구관계가 존재하는지를 조사하는 것이다. adjacent list를 이용하여 연결관계에 대한 정보를 저장하고 시작점을 vertex 0부터 n-1까지 돌아가면서 dfs를 사용하여 depth가 4이상이 되는 subgraph가 존재하는지를 판별하면 된다. 코드 n, m = map(int, input().split()) adj_lst = [[] for i in range(n)] for i in range(m): a,..

문제 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용 www.acmicpc.net 생각의 흐름 결국 최종적으로는 화면에 n개의 이모티콘이 있어야 하는데 이 때, 클립보드에 있는 이모티콘의 갯수가 0~n-1개 일..