꾸준한 개발일기

문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 분석 시간 복잡도 N x N 지도 (N = 25) 영역 탐색 (그래프 탐색) 중복방문 X O( N ^ 2) 문제 유형 그래프 탐색 시간 복잡도 상, 완전탐색 (dfs, bfs) 가능 설계 dfs와 bfs는 기본적으로 "탐색" 알고리즘이다. 따라서, 연결된 곳 (순회할 수 있는 곳)이 어디있는지 파악 연결된 곳으로 방문할 수 있는지 파악 하는 것이 중요하다. 해당 문제의 경우, 연결된 곳은..

문제 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) ..

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