알고리즘 들어가기

2022. 2. 24. 08:56·Algorithm/이론
반응형

알고리즘이란 문제를 해결하기 위한 단계적인 절차를 의미한다.

주어진 문제에 여러 종류의 알고리즘이 있을 수 있으나, 보다 효율적인 알고리즘을 고안하는 것이 매우 중요하다.

 

1. 최대 숫자 찾기

mission: 다음 카드들 중에 가장 큰 숫자를 찾는다.

- 순차 탐색 (Sequential Search)

카드를 한 장씩 차례대로 읽어 가며 찾는 방법이다.

 

2. 임의의 숫자 찾기

mission: 다음 카드들 중에 임의의 숫자(ex. 85)를 찾는다.

- 순차 탐색 (Sequential Search)

- 이진 탐색 (Binary Search)

오름차순으로 정렬된 데이터를 반으로 나누고, 나누어진 반을 다시 반으로 나누고, 이 과정을 반복하여 원하는 데이터를 찾는 탐색 알고리즘이다.

 

3. 동전 거스름돈

mission: 거스름돈을 동전으로 줄 때, 가장 적은 수의 동전을 준다.

- 그리디 알고리즘 (Greedy Algorithm)

greedy는 '탐욕스러운'이라는 뜻이다.

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

 

4. 한붓그리기

mission: 종이에서 연필을 떼지 않고 한붓그리기를 한다.

한붓그리기는 그래프의 어느 한 점에서 출발하여 모든 선분을 한 번만 지나서 출발점으로 돌아오되, 궤적을 그리는 동안 연필이 종이에서 떨어져서는 안 된다. 단, 점은 여러 차례 방문하여도 괜찮다.

solution: 현재 점으로부터 진행하고자 하는 점을 지나서 현재 점으로 돌아오는 사이클을 찾는다.

 

5. 미로 찾기

solution: 오른손 법칙

현 위치에서 한 방향을 선택하고, 벽에 오른손을 댄다. 출구가 나올 때까지 계속 오른손을 벽에서 떼지 않고 걸어가면 출구를 찾을 수 있다.

알고리즘으로 출구를 찾아 나아가는 궤적을 점선으로 나타냈다.

 

6. 가짜 동전 찾기

mission: 아주 많은 동전 더미 속에 1개의 가짜 동전이 섞여있다. 가짜 동전은 눈으로 식별할 수 없지만, 정상적인 동전보다 약간 가볍다. 양판 저울만 사용하여 가짜 동전을 찾되, 가능한 한 저울에 동전을 다는 횟수를 줄여야 한다.

 

solution1: 임의의 동전 1개를 저울 왼편에 올리고, 나머지 동전을 하나씩 오른편에 올려서 가려낸다. -> 1번~(n-1)번

solution2: 동전을 2개씩 짝을 지어, n/2 짝을 각각 저울에 달아서 가짜 동전을 찾는다. -> 1번~n/2번

solution3: 동전 더미를 반으로 나누어 저울 양편에 달고, 가벼운 쪽의 더미를 계속 반으로 나누어 저울에 단다. 분할된 더미의 동전 수가 1개씩이면, 마지막으로 저울을 달아 가벼운 쪽의 동전이 가짜임을 찾아낸다. -> log₂n번

solution3이 이진 탐색을 이용한 방법으로, 세 가지 중 가장 효율적이다.

 

7. 독이 든 술단지

mission: 희생되는 신하의 수를 최대한 줄이면서 독이 든 술단지를 찾는다.

solution: 각 단지에 2진수를 0부터 부여하고, 각 신하가 술맛을 보면 1, 안 보면 0으로 하여 단지와 신하를 짝짓는다.

단지 수가 n일 때, 희생자 수는 0~log2₂n명이다.

 

[참고] 알기 쉬운 알고리즘

반응형

'Algorithm > 이론' 카테고리의 다른 글

[알고리즘] 재귀(Recursion)  (0) 2024.11.11
[알고리즘] 분할 정복 알고리즘(Divide-and-Conquer)  (0) 2022.02.24
[알고리즘] 자료구조 총정리 : 배열, 연결 리스트, 스택, 큐, 트리, 그래프  (0) 2022.02.24
알고리즘을 배우기 위한 준비  (0) 2022.02.24
'Algorithm/이론' 카테고리의 다른 글
  • [알고리즘] 재귀(Recursion)
  • [알고리즘] 분할 정복 알고리즘(Divide-and-Conquer)
  • [알고리즘] 자료구조 총정리 : 배열, 연결 리스트, 스택, 큐, 트리, 그래프
  • 알고리즘을 배우기 위한 준비
올콩
올콩
콩 심은 데 콩 난다
  • 올콩
    콩스토리
    올콩
  • 전체
    오늘
    어제
    • 분류 전체보기 (191) N
      • SSAFY (10)
      • Algorithm (111) N
        • 이론 (6)
        • 백준 (BOJ) (104) N
        • 프로그래머스 (1)
      • Trouble Shooting (9)
      • Frontend (6)
      • React (17)
      • Next.js (3)
      • Vue (4)
      • Node.js (2)
      • HTML (9)
      • DevOps (3)
        • Git (3)
      • Language (9)
        • JavaScript (0)
        • Java (9)
      • Embedded (1)
      • CS (5)
        • Network (1)
        • Blockchain (4)
      • 자격증 (2)
  • 블로그 메뉴

    • GitHub
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    백준
    순열
    SSAFY
    싸피
    bfs
    브루트포스
    React
    백트래킹
    Java
    알고리즘
    재귀
    힙
    DP
    Heap
    Algorithm
    Error
    중복순열
    중복조합
    블록체인
    수학
    구현
    오블완
    dfs
    Next.js
    강의
    html5
    파이썬
    티스토리챌린지
    SSAFYcial
    우선순위큐
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
올콩
알고리즘 들어가기
상단으로

티스토리툴바