[수행평가] 알고리즘 개념 정리하기

그리디 알고리즘이란?

 

최적해를 찾기 위해 각 단계에서 가장 좋아 보이는 선택을 하는 알고리즘입니다. 그리디 알고리즘은 각 단계에서 지금 당장 최적인 선택을 하는 경향을 가지고 있으며, 그 선택이 전체적으로 최적해를 만드는지는 보장되지 않을 수 있습니다. 따라서 그리디 알고리즘은 항상 최적해를 보장하는 것은 아니지만, 여러 경우에서 유용하게 쓰일 수 있습니다.

 

그리디 알고리즘 예시 코드 - 거스름돈 문제

 

동전의 종류가 주어졌을 때, 거스름돈을 가장 적은 동전 개수로 주는 문제입니다.

 

def get_change(n, coins):
    change = []  # 거스름돈 동전 리스트
    coins.sort(reverse=True)  # 동전을 큰 순서대로 정렬
    
    for coin in coins:
        while n >= coin:  # 현재 동전보다 거스름돈이 크거나 같은 경우
            change.append(coin)  # 동전 추가
            n -= coin  # 거스름돈에서 현재 동전의 가치만큼 차감
            
    return change

# 예시 사용법
n = 1260  # 거스름돈 금액
coins = [500, 100, 50, 10]  # 동전의 종류

change = get_change(n, coins)
print(change)  # 출력: [500, 500, 100, 100, 100, 50, 10]
print(len(change))  # 출력: 7

 

get_change 함수를 정의하여 그리디 알고리즘을 적용한 거스름돈 문제를 해결합니다. 함수는 거스름돈 금액 n과 동전의 종류를 나타내는 리스트 coins를 입력으로 받습니다. 동전 리스트 coins는 큰 순서대로 정렬되어 있어야 합니다.

 

함수에서는 주어진 거스름돈 금액을 가장 큰 동전으로부터 차례로 비교하여 가능한 많은 동전을 사용합니다. while 반복문을 사용하여 현재 동전의 가치보다 거스름돈이 크거나 같은 경우, 해당 동전을 거스름돈 리스트에 추가하고, 거스름돈에서 현재 동전의 가치를 차감합니다. 이 과정을 거스름돈이 0이 될 때까지 반복합니다. 

 

 

 

구현 알고리즘이란?

 

알고리즘을 실제로 구현하는 과정을 의미합니다. 주어진 문제나 알고리즘을 프로그래밍 언어로 구체적으로 작성하여 실행 가능한 형태로 만드는 것을 말합니다. 구현 알고리즘은 알고리즘의 동작 과정을 구체화하고, 데이터 구조, 제어문, 반복문 등을 이용하여 알고리즘을 코드로 변환하는 과정을 말합니다.

 

구현 알고리즘 예시 코드 - 실습1 문제

 

알파벳 대문자와 숫자(0 ~ 9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다.

예를 들어 K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력한다

 

s = input()
number = 0 # 숫자
result = [] # 문자

for i in s:
    if i.isalpha(): # 알파벳인 경우 리스트에 삽입
        result.append(i)
    elif i.isdigit(): # 숫자인 경우 따로 더하기
        number += int(i)

result.sort()
if number != 0: # 숫자가 하나라도 존재한다면 리스트 가장 뒤에 삽입
    result.append(str(number))
print(''.join(result)) # 리스트 -> 문자열 변환 출력

 

입력 : K1KA5CB7

출력 : ABCKK13

 

 

 

DFS, BFS 알고리즘이란?

 

그래프 탐색 알고리즘입니다. 그래프는 정점과 간선으로 이루어진 자료 구조로, 여러개의 노드가 서로 연결되어 있는 구조를 말합니다. DFS와 BFS는 그래프의 모든 노드를 탐색하기 위해 사용되는 알고리즘으로, 각각 깊이 우선 탐색과 너비 우선 탐색을 의미합니다.

 

DFS

 

- 깊이 우선 탐색은 그래프에서 한 노드에서 시작하여 해당 노드와 인접한 노드들을 먼저 탐색하는 알고리즘 입니다. 특정 노드의 자식 노드를 탐색하기 전에 해당 노드의 모든 형제 노드를 함색합니다.

 

BFS

 

- 너비 우선 탐색은 그래프에서 한 노드에서 시작하여 해당 노드와 인접한 모든 노드들을 먼저 탐색하는 알고리즘입니다. 같은 레벨의 노드들을 먼저 탐색한 후 다음 레벨의 노드들을 탐색합니다.

 

DFS, BFS 알고리즘 예시 코드

 

음료수 얼려먹기(DFS)

주어진 2차원 그리드에서 얼음이 형성되는 영역의 개수를 찾는 문제입니다.

 

n, m = map(int,input().split())

board = []
for i in range(n):
    tmp = list(map(str,input()))
    board.append(list(map(int, tmp)))
visited = board

f = []
cnt =0

dx = [0,1,0,-1] #북쪽부터 시계방향
dy = [-1,0,1,0]

def dfs(iy,ix):
    global visited,f
    
    visited[iy][ix] = 1
    f.append((iy,ix))

    count=0
    for i in range(len(dx)):
        tx = ix+dx[i]
        ty = iy+dy[i]
        count+=1
        if ty>=0 and ty<n and tx>=0 and tx<m:
            if visited[ty][tx] == 0:
                dfs(ty,tx)

    if count==4:
        if f:
            f.pop()
            if not f:
                return
            dfs(f[-1][0],f.pop()[1])
        else:
            return         

for i in visited:
    for j in i:
        if j==0:
            dfs(visited.index(i),i.index(j))
            cnt+=1

print(cnt)

 

주어진 그리드의 모든 위치를 순회하며 방문하지 않은 빈 공간을 찾습니다. 그리고 방문하지 않은 빈 공간을 찾았을 때, 해당 위치를 시작으로 DFS를 수행하여 연결된 모든 빈 공감을 탐색합니다. DFS를 수행하면서 방문한 위치를 체크하여 중복 방문을 방지합니다. 그리고 DFS가 종료될 때마다 얼음이 형성되는 영역의 개수를 증가시킵니다. 마지막으로 모든 위치를 순회하고 나서 얼음이 형성되는 영역의 개수를 반환합니다.

 

연구소(BFS)

바이러스의 확산을 막기 위해 벽을 설치하여 안전 영역의 최대크기를 구하는 문제입니다.

 

import sys
from itertools import combinations
from collections import deque
from copy import deepcopy

# 지도의 크기
n, m = map(int, sys.stdin.readline().split())

# 지도 정보 저장
lab = []
for _ in range(n): 
    lab.append(list(map(int, sys.stdin.readline().split())))

# 빈 공간의 좌표를 모두 저장
empty = []
for i in range(n):
    for j in range(m):
        if (lab[i][j] == 0):
            empty.append((i,j))

# 가능한 울타리 조합을 모두 계산
total_empty_combi = list(combinations(empty, 3))

# 상하좌우 이동용 좌표
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS를 사용해 바이러스 확산시킨 뒤, 남은 안전 영역을 계산
def bfs():

    # 울타리가 설치된 지도를 깊은 복사
    lab_copy = deepcopy(lab)

    for x in range(n):
        for y in range(m):

            # 바이러스 확산용 큐
            q = deque()     

            # 현재 위치에 바이러스가 있다면
            if (lab_copy[x][y] == 2):

                # 현재 위치를 큐에 추가
                q.append((x, y))
                while(q):    

                    # 현재 위치를 큐에서 추출
                    now = q.popleft()

                    # 상하좌우의 빈 공간에 바이러스를 학산
                    for i in range(4):
                        new_x = now[0] + dx[i]
                        new_y = now[1] + dy[i]

                        # 이웃 영역이 지도 내에 존재하고, 빈 공간인지 확인
                        if (0 <= new_x and new_x < n and 0 <= new_y and new_y < m and lab_copy[new_x][new_y] == 0):
                            # 주변 위치에 바이러스를 확산
                            lab_copy[new_x][new_y] = 2

                            # 이웃 공간을 큐에 추가
                            q.append((new_x, new_y))

    return safe_area(lab_copy)

# 남은 안전 영역을 계산
def safe_area(lab_copy):

    count = 0
    for i in range(n):
        for j in range(m):
            if (lab_copy[i][j] == 0):
                count += 1

    return count

def solution():

    # 울타리 설치 전 원본
    global lab

    # 울타리 조합 별 안전 영역의 개수 저장
    result = -1

    # 울타리를 세운 뒤, BFS를 사용해 바이러스를 확산시키고, 남은 안전 영역을 계산
    for empty_combi in total_empty_combi:

        # 울타리 설치
        for x, y in empty_combi:
            lab[x][y] = 1

        # BFS를 사용해 바이러스 확산시킨 뒤, 남은 안전 영역을 계산하고, 최대값과 비교
        result = max(result, bfs())

        # 울타리 제거
        for x, y in empty_combi:
            lab[x][y] = 0

    return result

print(solution())

 

BFS 알고리즘을 사용하여 연구소 문제를 해결하는 것은 바이러스의 확산을 모든 방향으로 동시에 탐색하면서 안전 영역의 크기를 구하는 것입니다. BFS는 너비 우선 탐색으로, 한 노드에서 인접한 노드들을 먼저 탐색하는 알고리즘 입니다. 이를 이용하여 바이러스의 확산을 효율적으로 처리할 수 있습니다.

 

 

 

 

선택정렬 알고리즘이란?

 

주어진 배열에서 가장 작은 값을 선택하여 맨 앞으로 이동시키는 정렬 알고리즘입니다. 배열을 순회하면서 최솟값을 찾아 맨 앞 요소와 교는 정렬 알고리즘입니다. 배열을 순회하면서 최솟값을 찾아 맨 앞 요소와 교환하는 과정을 반복하여 정렬을 수행합니다.

 

선택정렬 알고리즘 예시 코드

 

#include <stdio.h>
int main() {
	int n, arr[100]={0};
	
	scanf("%d", &n);
	for(int i=0; i<n; i++) {
		scanf("%d", &arr[i]);
	}
	
	for (int i = 0; i < n - 1; i++)
    {
        int indexMin = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[indexMin])
            {
                indexMin = j;
            }
        }
        int temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
    }
	
	for(int i=0; i<n; i++) {
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

 

 

삽입정렬 알고리즘이란?

 

주어진 배열을 정렬된 부분과 비정렬된 부분으로 나누고, 비정렬된 부분의 요소를 정렬된 부분에 적절한 위치에 삽입하는 정렬 알고리즘입니다. 배열의 요소를 순회하면서 정렬된 부분에서 요소의 적절한 위치를 찾아 삽입합니다.

 

 

삽입정렬 알고리즘 예시 코드

 

#include <stdio.h>
int main() {
	int n, arr[100]={0};
	
	scanf("%d", &n);
	for(int i=1; i<=n; i++) {
		scanf("%d", &arr[i]);
	}
	
	int j;
	for (int i=1; i<=n; i++)
  {
    int remember = arr[(j=i)];
    while (--j >= 0 && remember < arr[j]){
        arr[j+1] = arr[j];
    }
    arr[j+1] = remember;
  }
	
	for(int i=1; i<=n; i++) {
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

 

 

퀵정렬 알고리즘이란?

 

분할 정복 방법을 사용하여 배열을 정렬하는 알고리즘입니다. 배열에서 하나의 요소를 선택하여 pivot으로 설정하고, pivot 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할합니다. 

 

퀵정렬 알고리즘 예시 코드

 

# include <stdio.h>
# define LEN 7
 
void quickSort(int arr[], int L, int R) {
      int left = L, right = R;
      int pivot = arr[(L + R) / 2];    // pivot 설정 (가운데) 
      int temp;
      do
      {
        while (arr[left] < pivot)    // left가 pivot보다 큰 값을 만나거나 pivot을 만날 때까지 
            left++;
        while (arr[right] > pivot)    // right가 pivot보다 작은 값을 만나거나 pivot을 만날 때까지 
            right--;
        if (left<= right)    // left가 right보다 왼쪽에 있다면 교환 
        {
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            /*left 오른쪽으로 한칸, right 왼쪽으로 한칸 이동*/
            left++;
            right--;
        }
      } while (left<= right);    // left가 right 보다 오른쪽에 있을 때까지 반복 
 
    /* recursion */
    if (L < right)
        quickSort(arr, L, right);    // 왼쪽 배열 재귀적으로 반복 
 
    if (left < R)
        quickSort(arr, left, R);    // 오른쪽 배열 재귀적으로 반복 
}
 
int main(){
  int arr[100]={0};
	int n;
	
	scanf("%d", &n);
	for(int i=0; i<n; i++) {
		scanf("%d", &arr[i]);
	}
    
  quickSort(arr, 0, n-1);
  
  for(int i=0; i<n; i++){
    printf("%d ", arr[i]);
  }
  
  return 0; 
}

 

 

 

계수정렬 알고리즘이란?

 

비교 기반 정렬 알고리즘이 아닌 정수의 개수를 세는 방식으로 동작하는 정렬 알고리즘입니다. 정수의 범위가 제한되어 있고, 정수의 개수를 세는 작업을 통해 정렬을 수행합니다. 각 정수의 개수를 세어 정수의 값에 해당하는 인덱스 개수를 저장하고, 이를 바탕으로 정렬된 결과를 생성합니다. 

 

계수정렬 알고리즘 예시 코드

 

#include <stdio.h>
int main() {
	int n, num, visit[51]={0}, max=0;
	
	scanf("%d", &n);
	for(int i=0; i<n; i++) {
		scanf("%d", &num);
		if(max<num) max=num;
		visit[num]++;
	}
	
	for(int i=0; i<=max; i++) {
		if(visit[i]!=0) {
			for(int j=0; j<visit[i]; j++) {
				printf("%d ", i);
			}
		}
	}
	
	return 0;
}

 

 

 

탐색 알고리즘이란?

 

순차탐색

- 리스트나 배열과 같은 선형 구조에서 원하는 항목을 찾기 위해 처음부터 순서대로 탐색하는 알고리즘입니다. 데이터가 정렬되어 있지 않은 경우에 주로 사용됩니다. 순차 탐색은 간단하고 직관적인 방법으로 구현할 수 있으며, 데이터의 순서와 상관 없이 모든 요소를 확인하기 때문에 모든 경우를 탐색할 수 있습니다.

 

이진탐색

- 정렬된 리스트나 배열에서 특정한 값을 찾는 알고리즘입니다. 리스트를 반으로 나누어 탐색 범위를 좁혀가는 방식으로 동작합니다. 이진 탐색은 분할 정복 전략을 사용하여 작동하며, 매번 탐색 범위를 절반으로 줄여가기 때문에 매우 효율적입니다. 이진탐색은 반복문을 사용한 반복적인 구현 방식과 재귀적인 구현 방식으로 구현할 수 있습니다. 

 

순차탐색, 이진탐색 알고리즘 예시 코드

 

순차탐색

 

def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 탐색 대상을 찾았을 때 해당 인덱스를 반환
    return -1  # 탐색 대상을 찾지 못한 경우 -1을 반환

# 예시 배열과 탐색 대상
arr = [4, 2, 9, 7, 1, 5]
target = 7

# 순차 탐색 수행
result = sequential_search(arr, target)

# 결과 출력
if result != -1:
    print(f"탐색 대상 {target}은(는) 인덱스 {result}에 위치합니다.")
else:
    print("탐색 대상을 찾지 못했습니다.")

 

이진탐색

 

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main() {
    int arr[100]={0};
    int n, target;
    
		scanf("%d %d", &n, &target);
		for(int i=0; i<n; i++) {
			scanf("%d", &arr[i]);
		}
	
    int result = binarySearch(arr, 0, n - 1, target);
    if (result == -1) {
        printf("원소가 존재하지 않습니다.");
    } else {
        printf("%d", result+1);
    }
    return 0;
}

 

원소의 개수와 찾고 싶은 원수를 입력한 한 후 원소가 존재하면 몇번째에 있는지 출력하고, 없다면 '원소가 존재하지 않습니다'를 출력합니다.

 

 

 

DP 알고리즘이란?

 

문제를 작은 부분 문제로 나누어 해결하는 최적화 기법입니다. 문제를 작은 부분 문제로 나누어 푸는 동적 계획법은 중복된 계산을 피하고 계산 속도를 향상시킬 수 있는 장점이 있습니다. DP 알고리즘은 다음과 같은 점화식을 사용하여 작은 부분 문제의 해를 구하고, 이를 이용하여 큰 문제의 해를 구하는 방식으로 동작합니다. 또한 DP 알고리즘은 다이나믹 테이블이라는 배열이나 테이블을 사용하여 중복 계산을 피하고 해를 저장하며 상향식 또는 하향식 방식으로 구현할 수 있습니다.

 

DP 알고리즘은 다양한 문제에 적용될 수 있으며, 주로 최단 경로 문제, 최강 공통 부분 수열 문제, 배낭 문제 등에 사용됩니다.

 

DP 알고리즘 예시 코드

 

피보나치 수열을 계산하는 문제

 

def fibonacci(n):
    # DP를 위한 배열 초기화
    dp = [0] * (n+1)
    
    # 초기값 설정
    dp[0] = 0
    dp[1] = 1
    
    # 피보나치 수열 계산
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

# 피보나치 수열의 10번째 항 계산
result = fibonacci(10)
print(result)  # 출력: 55