알기쉬운알고리즘] (1) 알고리즘 첫걸음

2023-12-25 8 분 소요

알고리즘 이란?

문제를 해결하기 위한 단계적인 절차 또는 방법
알고리즘(영어: algorithm)은 수학과 컴퓨터과학에서 사용되는, 문제 해결 방법을 정의한 ‘일련의 단계적 절차’이자 어떠한 문제를 해결하기 위한 ‘동작들의 모임’(출처 : 위키백과)

알고리즘의 첫걸음

최대 숫자 찾기
- 순차탐색 (n개라면 n-1번까지 실행해야함)
임의의 숫자 찾기
- 이진탐색
  정렬 후 중간에 있는 값과 우선 비교 -> 훨씬 빠르게 목표에 다가감
동전 거스름돈
(그리디 알고리즘)
- 가장 적은 수의 동전을 원한다
- 남은 거스름돈 액수를 넘지 않는 한도에서 가장 큰 액면의 동전을 계속 선택
- 이게 최선의 방법일까? 를 생각해야 하고,
  분야마다 선택하는 알고리즘이 또 달라서 잘 선택해서 써야함.
한붓그리기
- 1) 시작점 찾기 - 시작점을 어떻게 찾는게 효율적일까?
- 2) 어떤 조건을 넣어서 완성이 될까?
- 3) *사이클 찾아야 함. - 현재 점으로 돌아오는 사이클이 있으면 진행.
  외길이면 (인접한 점 하나밖에 없음) 사이클 체트 없이 감.
미로 찾기
- 한쪽 벽을 집고 감(오른손 법칙)
가짜 동전 찾기
가짜 동전의 무게는 정상적인 동전모다 약간 가볍움.
- 동전이 N 개라면,
  1) 순차탐색 - 임의의 동전 1개 올리고 하나씩 다른 저울에 올려서 가짜 동전 찾기(최대 N-1번 사용)
  2) 2개씩 짝을 지어 n/2 각각 저울에 달어서 (최대 N/2 저울사용)
  3) 이진탐색과 유사: *분할정복 - 동전 더미를 반으로 나눠서 가짜 동전 찾기 (마지막까지 저울을 달아야 하고, log2N번 저울을 사용)
독이 든 술단지
창고의 많은 술단지 중 하나의 단지에만 독을 넣었고, 먹으면 일주일 후에 죽는다 최소 희생으로 독단지 찾는 방법
- 4개의 단지가 있다면 신하 두명으로 확인
  -> 먹지 않은 단지, A가 먹은 단지, B가먹은 단지, AB 둘다 먹은단지 ( 둘다 죽으면 둘이 같이먹은 단지가 독이 듦)
  => 이진수 활용 (00, 01, 10, 11)

핵심

1) 순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

순차탐색은 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인한다는 점이 특징

python 코드

    # 순차 탐색 소스코드 구현
    def sequential_search(n, target, array):
        # 각 원소를 하나씩 확인
        for i in range(n):
            # 현재의 원소가 찾고자 하는 원소와 동일한 경우
            if array[i] == target:
                return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 1을 더한다.)
    print('생성할 원소 개수를 입력한 뒤, 한 칸 띄고 찾을 문자열을 입력하시오.')
    input_data = input().split()
    n = int(input_data[0]) # 원소의 개수
    target = input_data[1] # 찾고자 하는 문자열

    print('앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.')
    array = input.split()

    # 순차 탐색 수행 결과 출력
    print(sequential_search(n, target, array))

2) 이진 탐색

탐색 범위를 반으로 좁혀가며 데이터를 탐색 (배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘으로 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징)

시작점, 끝점, 중간점 필요

python 코드

# 1. 재귀 함수로 구현한 이진 탐색 소스코드
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2  # 중간점
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid -1)
    else:
        return binary_search(array, target, mid+1, end)

# n과 target을 입력 받기 (n: 원소의 개수, target: 찾고자 하는 문자열)
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n-1)
if result == None:
    print('원소가 존재하지 않습니다.')
else:
    print(result+1)


# 2. 반복문으로 구현한 이진 탐색 소스코드
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start+end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return None
            
# n과 target을 입력 받기 (n: 원소의 개수, target: 찾고자 하는 문자열)
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n-1)
if result == None:
    print('원소가 존재하지 않습니다.')
else:
    print(result+1)  

3) 그리디 (Greedy) 알고리즘

Greedy(탐욕, 욕심쟁이)라는 이름처럼 지금 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘

특징 1) greedy choice property: 현재 선택이 이 후의 선택에 영향을 주지 않음
특징 2) optimal substructure: 매 순간의 최적의 해가 문제 전체에 대한 최적의 해여야 함

python 코드

# 동전 문제에 대한 소스코드 예시
def min_coin_count(value, coin_list):
    total_coin_count = 0
    details = list()
    coin_list.sort(reverse=True)
    for coin in coin_list:
        coin_num = value // coin
        total_coin_count += coin_num
        value -= coin_num * coin
        details.append([coin, coin_num])
    return total_coin_count, details

4) 한붓그리기 사이클

오일러 서킷, 한 정점에서 시작해서 모든 간선을 지나 시작 정점으로 돌아오는 것

현재 점으로부터 진행하고자 하는 점을 지나서 현재 점으로 돌아오는 ‘사이클(cycle)’을 찾는 것이 특징 조건
- 모든 간선들이 하나의 컴포넌트에 속해야한다.
- 각 정점마다 간선의 수가 짝수개여야한다.
  
  출처 : https://source-sc.tistory.com/55

python 코드

# 출처 : https://www.geeksforgeeks.org/eulerian-path-and-circuit/
# Python program to check if a given graph is Eulerian or not
#Complexity : O(V+E)

from collections import defaultdict

# This class represents a undirected graph using adjacency list representation


class Graph:

    def __init__(self, vertices):
        self.V = vertices  # No. of vertices
        self.graph = defaultdict(list)  # default dictionary to store graph

    # function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    # A function used by isConnected
    def DFSUtil(self, v, visited):
        # Mark the current node as visited
        visited[v] = True

        # Recur for all the vertices adjacent to this vertex
        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)

    '''Method to check if all non-zero degree vertices are
    connected. It mainly does DFS traversal starting from 
    node with non-zero degree'''

    def isConnected(self):

        # Mark all the vertices as not visited
        visited = [False]*(self.V)

        #  Find a vertex with non-zero degree
        for i in range(self.V):
            if len(self.graph[i]) != 0:
                break

        # If there are no edges in the graph, return true
        if i == self.V-1:
            return True

        # Start DFS traversal from a vertex with non-zero degree
        self.DFSUtil(i, visited)

        # Check if all non-zero degree vertices are visited
        for i in range(self.V):
            if visited[i] == False and len(self.graph[i]) > 0:
                return False

        return True

    '''The function returns one of the following values
    0 --> If graph is not Eulerian
    1 --> If graph has an Euler path (Semi-Eulerian)
    2 --> If graph has an Euler Circuit (Eulerian)  '''

    def isEulerian(self):
        # Check if all non-zero degree vertices are connected
        if self.isConnected() == False:
            return 0
        else:
            # Count vertices with odd degree
            odd = 0
            for i in range(self.V):
                if len(self.graph[i]) % 2 != 0:
                    odd += 1

            '''If odd count is 2, then semi-eulerian.
            If odd count is 0, then eulerian
            If count is more than 2, then graph is not Eulerian
            Note that odd count can never be 1 for undirected graph'''
            if odd == 0:
                return 2
            elif odd == 2:
                return 1
            elif odd > 2:
                return 0

    # Function to run test cases

    def test(self):
        res = self.isEulerian()
        if res == 0:
            print("graph is not Eulerian")
        elif res == 1:
            print("graph has a Euler path")
        else:
            print("graph has a Euler cycle")


# Let us create and test graphs shown in above figures
g1 = Graph(5)
g1.addEdge(1, 0)
g1.addEdge(0, 2)
g1.addEdge(2, 1)
g1.addEdge(0, 3)
g1.addEdge(3, 4)
g1.test()

g2 = Graph(5)
g2.addEdge(1, 0)
g2.addEdge(0, 2)
g2.addEdge(2, 1)
g2.addEdge(0, 3)
g2.addEdge(3, 4)
g2.addEdge(4, 0)
g2.test()

g3 = Graph(5)
g3.addEdge(1, 0)
g3.addEdge(0, 2)
g3.addEdge(2, 1)
g3.addEdge(0, 3)
g3.addEdge(3, 4)
g3.addEdge(1, 3)
g3.test()

# Let us create a graph with 3 vertices
# connected in the form of cycle
g4 = Graph(3)
g4.addEdge(0, 1)
g4.addEdge(1, 2)
g4.addEdge(2, 0)
g4.test()

# Let us create a graph with all vertices
# with zero degree
g5 = Graph(3)
g5.test()

# This code is contributed by Neelam Yadav

5) 분할 정복 (Divide-and-Conquer) 알고리즘

분할 정복 알고리즘의 설계 전략

① 분할(Divide) : 해결할 문제를 여러 개의 작은 부분 문제들로 분할
② 정복( Conquer ) : 나눈 작은 문제를 각각 해결
③ 통합(combine) : 필요 시 해결된 해답을 모음

python 코드

# 일반 반복 알고리즘
def iterative_Power(C,n):
    result = 1
    for _ in range(n):
        result= result*C
    return result

# 분할 정복 기반의 알고리즘
def Recursive_Power(C,n):
    if n ==1:
        return C
    if n % 2==0:
        y = Recursive_Power(C,n/2)
        return y*y
    else:
        y= Recursive_Power(C,(n-1)/2)
        return y*y*C

# 병합 정렬 알고리즘, 분할 정복 예시
def merge_sort(m):
    if len(m)<=1: #사이즈가 0이거나 1인 경우, 바로 리턴
        return m
    
    # 1. DIVIDE 부분
    mid = len(m)//2
    left = m[:mid]
    right = m[mid:]
    
    # 리스트의 크기가 1이 될 때까지 merge_sort 재귀 호출
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 2. CONQUER 부분 : 분할된 리스트들 병합
    return merge(left,right)

6) 2진수를 활용

독이 든 술단지(주어진 다수의 술 단지에서 독이 든 단지 찾기), 어떻게하면 희생되는 신하의 수를 줄일 수 있을 것인가? -> 적은 수의 술단지에 대하여 우선 생각해 보는 것이 핵심

Parameters : 술 단지의 개수 N, 술 단지 리스트 L.
Instance : N = 4, L = {c1, c2, c3, c4}
Solution : L에서 독이 든 술 단지와 필요한 최소 인원수
술단지에 ‘2진수’를 부여 -> n개의 단지가 있으면, lob2n명의 신하만이 필요(최소 희생자는 0명, 최대는 log2n명)

python 코드

# 양의 정수 n이 주어졌을 때, 이를 이진수로 변환
# 1. 2진수 변환함수 사용 O
# 1) format
binaryNum = format(n, 'b')  # format 함수 이용, 'b' 는 2진수
return binaryNum

# 2) bin
binaryNum = bin(n)
return binaryNum[2:] # bin 이라는 함수 이용한다면 'ob + 2진수 변환 수' 로 나오기 때문에 앞에 ob를 제거한 후 return

# 2. 2진수 변환함수 사용 X, 재귀 호출
def getBinaryNum(n, lists):
    a, b = divmod(n, 2)   # divmod를 사용하면 몫과 나머지를 반환
    lists.append(b)
    if a == 0 :
        return lists
    else :
        return getBinaryNum(a, lists)

answerList = []
answer = getBinaryNum(n,answerList)
answer.sort(reverse=True)

return "".join([str(_) for _ in answer])
# 10진수를 2진수로 변환하는 방법은 n을 2로 나눈 나머지를 계속 기록하고, 몫을 계속 2로 나눠주는 것을 반복

# 3. 수식 이용
def getBinaryNum(n, lists):
    a = n // 2
    b = n % 2
    lists.append(b)
    if a == 0 :
        return lists
    else :
        return getBinaryNum(a, lists)

answerList = []
answer = getBinaryNum(n,answerList)
answer.sort(reverse=True)

return "".join([str(_) for _ in answer]) 

도서출처 : 양성봉, 『알기 쉬운 알고리즘(개정판)』. (주)생능출판사, 2021
요약출처

https://velog.io/@cha-suyeon/Algorithm-%EC%88%9C%EC%B0%A8-%ED%83%90%EC%83%89Sequential-Search%EC%99%80-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89Binary-Search

https://it-college-diary.tistory.com/entry/21-Greedy-Algorithm%ED%83%90%EC%9A%95%EB%B2%95-%EC%9A%95%EC%8B%AC%EC%9F%81%EC%9D%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90

https://source-sc.tistory.com/55

https://m.blog.naver.com/sunbi5252/221977857377

https://scsctrack.sogang.ac.kr/Download?pathStr=NTAjIzEwMSMjMTE0IyMxMTcjIzExNiMjOTkjIzEwMSMjMTA4IyM5NSMjMTA3IyM5OSMjOTcjIzExNCMjMTE2IyM5OSMjMTE1IyM5OSMjMTE1IyM0NyMjMTE1IyM5OCMjOTgjIzQ3IyMxMjQjIzEwNCMjMTE2IyM5NyMjODAjIzEwMSMjMTA4IyMxMDUjIzEwMiMjMzUjIzMzIyMzNSMjNDkjIzEyNCMjMTIwIyMxMDEjIzEwMCMjMTEwIyMxMDUjIzM1IyMzMyMjMzUjIzQ5IyMxMjQjIzEwMCMjMTA1IyMxMDcjIzExMg==&fileName=01_intro%5B0%5D.pdf&gubun=oldbbs)

Twitter Facebook LinkedIn

[Algorithm/기초/알기쉬운알고리즘] (1) 알고리즘 첫걸음

알고리즘 이란?

알고리즘의 첫걸음

핵심

1) 순차 탐색

2) 이진 탐색

3) 그리디 (Greedy) 알고리즘

4) 한붓그리기 사이클

5) 분할 정복 (Divide-and-Conquer) 알고리즘

6) 2진수를 활용

공유하기

참고

programmers_문제6_나머지가 1이 되는 수 찾기

스크랩_Edge detection

programmers_문제5_신고 결과 받기

Django 시작하기