자료구조 1차시

개발자한텐 필요한 기초역량

- 논리력

- 문제를 파악하고 추상화하는 능력 / 추상화된 문제를 해결하는 능력

==> 논리적 구성이 동일한 같은 문제를 더 쉽게 이해해서 풀면 최고의 개발자가 됨

 

But

- 대다수의 개발자들은 논리적이기보단 직관적으로 프로그래밍을 함

- 대다수의 개발자들이 설계자 관점보다는 사용자 관점에서 개발을 하고 있음

==> 직접 프로그램을 만들기보다는 만들어진것을 사용함 (그렇다고 프로그램이 전부 있는 것은 아님)

---

SW와 HW의 차이

SW : 설계자가 많이 필요

=> 소프트웨어는 생산에 돈이 별로 들지 않음

=> 다른 분야에 비해 생산품의 종류가 많음

 

HW : 조립하는 사람이 많이 필요

=> 하드웨어는 생산에 돈이 많이 듬

=> SW보다 생산품의 종류가 적음

---

The HALTING Problem (정지 문제)

임의의 A라는 프로그램에 임의의 B라는 입력을 넣었을 때 언젠가 알고리즘이 끝날 것인가 혹은 영원히 끝나지 않을 것인가?

 

엘론 튜링이 해결함 (이미테이션 게임에서 나옴)

 

귀류법 (증명을 하기위한 하나의 방법)

 

ex)

증명하고자 하는 것의 반대를 정의

=> p : 안경잡이개발자는 남자가 아니다

 

그 반대가 모순된다는 것을 증명

=> 안경잡이개발자가 남자가 아니라면,

그 남자만이 가질 수 있는 것을 가질 수 없다.

하지만 안경잡이개발자는 그것을 가지고 있다. 

 

원래 증명하고자 하는 것이 결국 참이라는 것을 증명

~p : 안경잡이개발자는 남자다 

 

정지 문제를 판별하는 알고리즘 : halting(A,B)

function check (A) {
  if halting(A,A) == false)
    return true;
  else
    infinitie loop;
}

check(check); //check 함수에 check를 넣음

 

 

정답 = 컴퓨터는 정지문제를 해결할 수 없다

 

The HALTING Problem ft. 동빈나

https://www.youtube.com/watch?v=xz1jyK9FqyE 

==> 해킹이나 현업에서도 이런 문제가 실제로 일어날 수 있음 (해결할수 없는 문제)

 

 

자료구조 시험

답보다는 이유를 설명해야 함