씅의 기록하는 개발노트

3 4
1 2 3 4
0 0 0 5
9 8 7 6

31

3 3
1 0 0
0 1 0
0 0 1

3

4 3
1 2 3
6 5 4
7 8 9
12 11 10

47

문제는 간단하다. 기본적인 DP문제이다. 유의할 점은 dp[i][j]를 구할때 대각선으로 가는 것은 고려하지 않아도 된다는 것이다. 왜냐하면 음수값을 입력하지 않기 때문이다. 즉 점화식을 구하면

dp[i][j]=max(dp[i-1][j],dp[i][j-1])+d[i][j]가 된다. 

객체 지향의 4대 특성

캡 - 캡슐화 : 정보 은닉

상 - 상속 : 재사용 

추 - 추상화 : 모델링

다 - 다형성 : 사용 편의

객체 지향에서 Inheritance 즉 상속은 가장 중요하고 강력한 특성임은 분명하다.

지금까지 객체지향을 한번쯤이라도 공부한 사람이라면 클래스와 객체의 관계를 붕어빵틀과 붕어빵 이라는 비유를 많이 봤을 것이다. 하지만 이 비유가 적절한 지 생각해보자(이러한 개념을 일단 버려라!)

클래스 객체명 = new 클래스();

일반적 객체를 생성하는 문법이다 이 문법을 붕어빵틀과 붕어빵에 적용시켜 보자

붕어빵틀 붕어빵 = new 붕어빵틀();

!!!! 위 논리가 맞다고 생각되는가? 붕어빵틀을 생산하는 기계가 있다고 하자. 그럼 붕어빵틀이 붕어빵을 찍어내서 클래스라고 한다면! 같은 논리로 기계는 붕어빵틀을 찍어내는 클래스가 된다.

기계 붕어빵틀 = new 기계(); => 새로운 기계를 만들었는데 붕어빵틀이 되었다.

붕어빵틀은 붕어빵을 만드는 팩토리일 뿐이였던 것이다. 

클래스는 분류에 대한 개념이지 실체가 아니다. 하지만 객체는 실체다.

추상화 : 모델링

공통되는 특성이나 속성 따위를 추출하여 파악하는 것! 즉 추상화란 구체적인 것을 분해해서 관찰자가 관심있는 특성만 가지고 재조합하는 것이며 이는 곧 모델링이라고 할 수 있다.

객체 - 세상에 존재하는 유일무이한 사물

클래스 - 분류, 집합, 같은 속성과 기능을 가진 객체를 총칭하는 개념

세상에 존재하는 유일무이한 객체를 특성(속성 + 기능) 에 따라 분류해 보니 객체를 통칭할 수 있는 집합적 개념, 즉 클래스가 나오게 된다. 따라서 클래스는 같은 특성을 지닌 여러 객체를 총칭하는 집합의 개념이다.

애플리케이션 경계 - Context

내가 만들고자 하는 애플리케이션은 어디에서 사용될 것인가?에 대한 답이 바로 Context다.

즉 Context에 따라 클래스의 설계가 달라질 수 있다는 것이다. 

여기까지 다시 개념정리를 했다면 추상화를 다시 정의해 보도록 하겠다.

추상화란 구체적인 것을 분해해서 관심 영영(Context) 있는 특성만 가지고 재조합하는 것이다. == 모델링

이러한 모델링은 실제 사물을 정확히 복제하는 것이 아니라 목적에 맞게 관심있는 특성만을 추출해서 표현하는 것이다. 클래스를 설계하거나 데이터베이스 테이블을 설계할 때 필요한 기법이기도 하다.

자바에서는 이러한 추상화를 class 키워드를 통해 지원하고 있다. 

추상화 = 모델링 = class키워드

1.1 문자열에 포함된 문자들이 전부 유일한지를 검사하는 알고리즘을 구현하라. 다른 자료구조를 사용할 수 없는 상황이라면 어떻게 하겠는가?

sol) 문자열이 ASCII코드라고 가정할 때 문자는 총 256개이다. 즉 문자열의 길이가 256 이상이면 중복이 존재할 것이다. 이후 boolean형 배열을 정의해 문자열을 탐색하여 기존에 있던 문자면 false를 반환하도록 한다.

1.2 널 문자로 끝나는 문자열을 뒤집는 reverse(char* str)함수를 C나 C++로 구현하라.

쉬운 문제이므로 pass!

1.3 문자열 두 개를 입력으로 받아 그중 하나가 다른 하나의 순열인지 판별하는 메서드를 작성하라.

1.4 주어진 문자열 내의 모든 공백을 '%20'으로 바꾸는 메소드를 작성하라. 문자열 끝에 추가로 필요한 문자들을 더할 수 있는 충분한 공간이 있다고 가정하라. 그리고 공백을 포함하는 문자열의 길이도 함 주어진다고 가정하라.

Ex) 입력 : "Mr John Smith"

     출력 : "Mr%20John%20Smith"