문제해결 1 - 개요, 절차

1. 문제해결의 개요

• 문제 : 현재 상태의 변화로 인해 원하는 방향의 목표가 생기는 것
• 단순 vs 복잡  /  해결 O vs X  /  반복성 vs 일회성
• 문제해결 
  • 현재상태와 목표 상태의 차이를 해결한 결과물
  • 현재 상태에서 목표상태에 도달하기 위한 필요요소 (ex, 시간 노력 사고 등등)
  • 문제해결이라는 결과물을 만들어내기 때문에 요소의 투입 정도에 따라 결과물의 질이 달라질 수 있음.

 

• 문제해결 과정 :
  • 문제(현재 상태) -> 문제해결(목표상태) 도달 위한 일련의 인지적 처리 및 사고활동의 과정을 순차적으로 나열한 것
  • 컴퓨팅 기반 문제 유형

컴퓨팅 기반 문제 유형
결정문제	탐색문제	연산 가능 문제	최적화 문제
대답이 "예 / 아니오"로 이루어지는 문제, 조건&요소 기반 이론 전개	답이 될 수 있는 요소를 체계적으로 찾아봄	연산을 통해 계산	최댓값 / 최소값으로 효율성을 높임

일반적 문제해결 과정	컴퓨팅 기반 문제해결과정
주어진 상황과 조건을 바탕으로 문제해결을 위한 효과적인 방안을 탐색해내는 일 문제를 풀어가는 당사자의 경험 및 지식, 성향 등에 따라 같은 문제 상황이라 할지라도 다르게 해결과정을 제안할 수 있음.	컴퓨팅 과학의 원리를 적용하여 문제를 해결했을 때 그 결과가 효율적이어야 함.
문제 이해  →  해결방안고안   →  해결책 선택  →  실행 및 평가	문제 이해  →  해결과정설계  →  프로그래밍 구현  →  결과물 확인

 

 

2. 문제해결의 절차

• 절차적 문제해결의 과정
  • 절차적? 
    • 어떤 순서에 의해 하나씩 단계별로 실행하는 일
    • 반드시 해당되는 단계에 따라 앞 뒤 순서가 정해져 있음.
    • 절차 혹은 순서란 문제해결을 위한 인지적 처리 과정을 정해진 순서에 따라 하나씩 단계를 나열하는 것
    • == 절차적 사고 
• 알고리즘 
  •  어떤 주어진 문제를 해결하기 위한 절차적 순서나 방법
  • 현재 상태와 목표 상태의 차이를 해결하기 위한 과정을 나열하는 것
  • 문제해결과정을 절차적, 순차적으로 나열하는 것
  • 어떤 문제를 해결하기 위한 사고과정 혹은 명령어들의 유한집합
  • 주어진 문제해결을 위한 논리적 절차나 방법 
    • 문제해결을 위한 방법

시행착오로 풀기

나누어풀기(분할정복)

거꾸로 풀기

경우의 수 대입해 풀기

• 알고리즘 설계방법

상향식	처음의 커다란 덩어리 문제를 점차 작은 문제로 해결책을 세분화 하는 법
하향식	작은 문제를 먼저 해결하고 해결한 작은 문제를 모아 점차 큰 문제를 해결하는 방법

 

• 알고리즘의 특성
  • 모호하지 않은 정확성
  • 실행 가능한 단계들의 집합으로 구성
  • 단계들은 정해진 순서에 의하여 실행됨 (단, 반드시 종료되어야함)
  • 효율적으로 그 가치가 높아짐
• 알고리즘의 표현방법

자연어	한글 / 영어, 알고리즘 기술의 용이성, 자연어의 모호성에 의해 명확성 유지 어려움
순서도	좋은 알고리즘 표현법이나 규모가 커지면 표현하기 어려움
의사코드	프로그래밍 언어에 가까움. 특정 언어의 구조에 제약 없음. 실행 위해서는 프로그래밍 언어로 코딩

 

• 알고리즘의 성능
  • 문제를 해결하는 방법이 하나인 경우도 있지만 여러가지인 경우가 대부분임
  • 알고리즘은 문제해결을 위한 단순한 해결과정의 절차적인 나열이 아님.
  • 다양한 요소를 고려하여 최선의 선택을 해야함
  • 최선의 선택을 할 수 있게 알고리즘을 나열하여 효율성을 높임(=최적화) <- 알고리즘 성능 고려
• 측정 기준

정확성

작업량 / 수행량

메모리 사용량

단순성 / 명확성

최적성

 

• 알고리즘에 따른 문제해결의 차이 : 어떤 알고리즘을 선택하느냐에 따라 정확도와 시간에 차이가 생김

효율성 분석방법	시간 복잡도	소요 시간 기준으로 효율성을 분석함. 사용되는 연산자를 처리하는 횟수가 적을 수록 효율적임. (= 시간복잡도가 적다) 시간복잡도 ↓  &  연산자 사용 횟수 ↓ == 효율성이 높은 알고리즘!
	공간 복잡도	메모리 공간을 적게 사용할 수록 효율성이 높다