switch

보호되어 있는 글입니다.

여러 가지 정렬 알고리즘의 차이점을 이해하고, 해당 상황에서 어떤 알고리즘이 어울릴지 살펴보자 예를 들어 Cat이라는 객체로 이루어진 아주 크기가 큰 배열이 있다고 하자 이 배열에 담긴 객체들을 나이순으로 정렬하라고 했을 때 어떤 알고리즘을 사용해야 할까? 여기서 알 수 있는 2가지는 1. 배열의 크기가 크므로 효율성이 매우 중요하다. 2. 나이순으로 정렬하는 것이므로 그 값의 범위가 좁다는 것을 알 수 있다. 다양한 정렬 알고리즘들을 살펴봤을 때 버킷 정렬 혹은 기수 정렬이 가장 적합하리라는 것을 눈치챌 수 있다. 각 버킷의 크기를 1년으로 설정하면 O(n)에 정렬할 수 있다. 자주 사용되는 정렬 알고리즘을 알아두면 문제풀이 능력을 크게 향상할 수 있다. 1. 버블 정렬 평균 및 최악 실행시간 : O(..

정렬을 이용한 문제풀이 무차별 알고리즘을 이용해서 O(n^2) 시간에 문제를 쉽게 풀어낼 수 있는 경우는 많지만 O(n^2)은 입력 크기가 클 때 사용하기에는 너무 느리다 O(n^2)이 걸리는 문제를 O(n)이나 O(n log n)시간으로 풀 수 있는 알고리즘의 설계에 대해 알아보자 예를 들어 배열의 모든 원소가 유일한지 검사한다고 해보자 아래의 무차별 알고리즘은 두 원소의 모든 조합을 O(n^2)에 살펴보는 것이다 bool ok = true; for (int i = 0; i < n; i++) { for (int j= i+1; j < n; j++) { if (array[i] == array[j]) ok = false; } } 배열을 정렬한다면 배열에 같은 원소가 있을 때 그 원소들이 정렬된 배열에서 나란..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 1번 노드에 연결된 그래프의 노드가 몇 개인지 찾는 문제이다. 단순하게 각 노드마다 연결된 노드의 리스트를 만들어서 1번부터 연결된 노드를 순회하며 바이러스가 걸리지 않은 컴퓨터(노드)가 있다면 재귀를 돌아줬다. import sys input = sys.stdin.readline n = int(input()) m = int(input()) #map 컴퓨터 수만큼 M = {} for i in range(..