꾸준한 개발일기

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 분석 시간 복잡도 N x N 칸 (N: 100) 중복 없이 방문: O(N^2) 문제 유형 완전 탐색 인접 4방향 그래프 탐색 (dfs, bfs) 설계 dfs, bfs 그래프 탐색의 난이도가 올라갈 수록 "갈 수 있는가?" 조건을 정확히 파악하여 설계하는 것이 중요하다. (dfs, bfs 설계에 대한 포스팅은 이전 글을 참조) 해당 문제의 경우 색약인 사람과 아닌 사람의 "갈 수 ..

문제 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 문제분석 시간복잡도 노드개수 V (1000개) 엣지개수 E ( V^2 ) 무방향 그래프, 연결요소 파악 1) 그래프 표현: 2차원 배열 노드 한개와 연결된 노드를 순회하는 비용: O( V ) → 완전탐색 비용: O( V ^ 2 ) (∵노드 개수 V개) 2) 그래프 표현: 연결리스트 배열 노드 한개와 연결된 노드를 순회하는 비용: ..

문제 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 풀이임을 확인하고 시간복잡도를 잘못 ..

문제 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탐색으로 순..

문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 설계의 방향성은 상.하.좌.우 재귀적 탐색을 바탕으로 한 그래프탐색이였다. Worst Case의 경우 배열이 100 X 100 크기지만, 모든영역을 탐색하는 것이 아닌 적절한 Pruning 과정이 있을 것이라 생각하여 가능할 것이라 판단하였다. 첫번째 시도(틀림): 안전한영역이 아닌 침수된 영역을 탐색하였다. 그러다보니, "안전한 영역"의 최대개수가 아닌 "침수된 영역"의 최대개수가 나왔다. ..