꾸준한 개발일기

문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 분석 시간 복잡도 컴퓨터수 (노드 수): 100대 엣지수: 모름 최악의 경우 완전그래프 형태: N(N-1) / 2 이미 방문한 노드는 재방문 필요 X 방문한 노드에서 연결된 노드 재귀적 방문 O(100) 연결리스트 배열: O ( V + E ) → O ( 100 + 100^2 ) 2차원 배열: O ( V^2 ) → O ( 100^2 ) 문제 유형 시간복잡도상 완전탐색 가능 완전탐색 (dfs) ..

문제리뷰 해당 문제는 문제 제목에서 알 수 있듯 "최단경로"를 구하는 문제이다. 또한, Input Size (노드개수, 엣지개수)에 따라 시간복잡도에 맞는 최단경로 알고리즘을 분류해낼 수 있는가?를 의도한 문제인 것 같다. 다익스트라와 플로이드-워셜과 같은 최단경로 알고리즘을 복기할 필요성을 느낀 문제이다. 풀이 시간복잡도 분석 2 "모든 노드"에 대한 최단거리를 구할 수 있고, 시간복잡도는 O(E logV)이다. 따라서, 시작노드 -> v1 -> v2 -> N 과 시작노드 -> v2 -> v1 -> N의 최단거리 중 최솟값을 구하면 시간복잡도도 초과하지 않고 목표로하는 값을 구할 수 있다. 단, 여기서 다익스트라를 dijkstra(시작노드), dijkstra(v1), dijkstra(v2) 총 3번 돌..

https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 리뷰 해당 문제는 완전탐색시 시간복잡도가 초과할 것으로 생각하여 고민하다 시간복잡도 안에 해결할 수 있는 풀이를 생각하지 못해 카카오 테크블로그와 타 블로그의 풀이를 참고한 문제이다. 노드의 개수가 17개이고, 중복된 경우가 많으며, 결국 모든 경우의 수를 고려해야 하므로 O(17!) 정도로 예상했기 때문이다. 하지만, 카카오 테크블로그 공식풀이가 dfs 풀이임을 확인하고 시간복잡도를 잘못 ..

"데이터 타입"의 정의 자바에서의 데이터 타입 인터페이스가 도입된 이유를 설명하기 앞서 "데이터 타입"의 정의부터 살펴보자. Data Type 1. 정의 정의: A data type is a category of data characterized by a collection of values (or domain) and a set of operations that act on those values. (출처: Data Structures & Algorithms in Java) 즉, 하나의 데이터 타입이 되려면 다음과 같은 것들이 정의되어 있어야 한다. 해당 타입에 속한 값들에 대한 정의 그 값들에 대해 적용할 수 있는 Operation에 대한 정의 2. 자바에서의 데이터타입 1. Primitive Typ..

[설계] 1. State Space Tree 설계 ① depth는 시간 (초)를 의미한다. ② 2번: 같은 depth에 있는 17은 "서로 다른 방법"을 통해 도달한 경우이다. 따라서, 일반적인 bfs처럼 큐 삽입시에 visiting check하면 안된다. (서로 다른 방법에 대한 고려가 안됨) ③ 1번: 문제의 목표는 "가장 빠른 시간"에 갈 수 있는 경우의 수이다. 즉, 이전 depth(더 빠른 시간)에 방문한 노드는 또 방문할 필요가 없다. => depth 단위로 끊어서 탐색하고, 1-depth가 끝나면 visiting check를 진행. ④ 종료조건: 방문노드 == 동생위치① 2. 시간복잡도 분석 위의 SST를 보면, 중복 방문의 경우가 존재하지만 visiting check를 통해 이전 depth..

https://www.acmicpc.net/problem/17398 17398번: 통신망 분할 첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q www.acmicpc.net 문제분석 시간제한: 1초, 메모리제한: 512MB 1. 시간복잡도 분석 - 통신탑(노드) 개수: 100,000 - 간선의 개수: 100,000 ▶O(V*E) (불가), O(V^2) (불가), O(E^2) (불가) ▶O(V), O(E) or log scale로 낮춰야.. 2. 유형 분석 그래프문제인 것 같긴한데 log scale로 떨어트려야 함. 1) LCA ->..

보호되어 있는 글입니다.

오늘은 알고리즘 기초에 대해 부족한 부분을 채우는 시간을 가졌다. 1. 완전탐색이란? 2. dfs 탐색 3. dfs 문제 (추 후, 풀이과정 업로드 예정) 1) 백준 골드 1759 암호만들기 2) 백준 골드 1062 가르침 4. bfs 탐색 5. bfs 문제 (추 후, 풀이과정 업로드 예정) 1) 백준 골드 3055 탈출

문제 10972 다음순열 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 설계 설계1: dfs 완전탐색 순열을 구하는 문제이니 dfs 완전탐색으로 접근하면 되지 않을까? 하지만, dfs 완전탐색은 모든 경우의 수에 대해 탐색하는 것이므로 Worst Case에 대해 고려해야 한다. Worst Case: N=10,000 즉, 10000! 경우의 수에 대해 탐색해야하므로 "시간초과" 설계2: 순열의 특성을 고려한 구현으로 접근 주어진 정보는 순열이다. 따라서, 주어진 순열을 적절히 조작하면 다음 순열을 만들 ..

문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 설계 설계방향성: 이 문제는 결국 이동가능한 경로에 대한 순열을 찾는 문제이다. (∵ 문제에서 주어진 인접행렬은 W[i][j] != W[j][i] 양방향 그래프이다. 즉, 경로 [1, 2, 3] != [1, 3, 2] 이기 때문에 조합이 아닌 순열을 구해야하는 것이다.) dfs로 접근 순열은 dfs탐색으로 구할 수 있다. 하지만, dfs탐색으로 순..