기록을

Array

• 논리적 저장 순서와 물리적 저장 순서가 일치한다.

• 따라서 인덱스로 해당 원소에 접근할 수 있으므로, 찾고자 하는 원소의 인덱스를 알고 있으면 O(1)의 시간 복잡도로 해당 원소에 접근할 수 있다. (Random access 가능)

• 삽입/삭제의 경우, O(1)에 접근은 할 수 있지만, 삽입/삭제 이후에 대부분의 상황에서 원소들을 shift 해주어야 하기 때문에, 이 shift 비용이 최악의 경우 O(n)이 된다.

LinkedList

• 논리적 저장 순서와 물리적 저장 순서가 관계가 없다.

• Random access가 불가능하다. 즉 특정 원소에 접근하고자 할 때, 처음부터 하나씩 찾아가야 한다. 따라서 검색 시 최악의 시간 복잡도는 O(n)이다.

• 삽입 혹은 삭제를 하는 경우에는, 일단 검색을 통해서 원하는 위치에 접근을 한 이후에는, 연결만 해주거나 끊어주면 되기 때문에 검색을 제외한 삽입/삭제의 시간 복잡도는 O(1)이다.

• 결국 처음부터 삽입/ 삭제를 해야하는 경우 시간 복잡도는 O(n)이다.

• Tree의 근간이 되는 자료구조이다.

배열의 경우에 데이터 삽입을 하려고 하는데 처음에 잡은 배열 크기의 범위를 벗어난다면, 새로이 할당을 하여 크기를 키워줘야 한다. 연결리스트는 이러한 과정이 필요 없다.

결론적으로 데이터의 삽입과 삭제가 빈번하게 일어난다면 연결리스트를 사용하면 된다.

그렇지 않고 미리 정해둔 데이터에서 검색만 빈번히 일어난다면 배열을 사용하는 것이 좋다.

하지만 대부분의 알고리즘 문제를 풀이할 경우에는, 메모리와 변수의 입력크기 범위가 주어지기 때문에, 그 한계치로 배열 크기를 잡아두고 사용하면 빠르게 사용할 수 있다.

또한 연결리스트의 경우, 원소 추가 과정마다 메모리의 할당이 발생하고, 삭제 시에는 메모리 해제가 발생하는데, 이러한 system call이 사용되는 부분에서 시간이 걸린다.

정의

속성과 기능을 포함한 프로그램 단위로 프로그램의 구성 요소를 객체화하는 것. 객체의 핵심은 기능을 제공하는 것이며, 기능들을 오퍼레이션이라고 부른다.

인터페이스: (코딩에서 인터페이스 말고)

객체가 제공하는 모든 오퍼레이션 집합을 객체의 인터페이스라고 부른다. 객체 사용을 위한 명세 의미

메시지

오퍼레이션의 실행을 요청하는 것을 메시지를 보낸다라고 표현. 자바나 파이썬에서 메서드를 호출하는 것이 메시지를 보내는 과정에 해당된다.

책임

객체가 자신이 제공하는 기능으로써 정의된다는 것은, 객체는 어떤 기능에 대한 책임을 진다는 것이다.

객체마다 이러한 책임의 크기가 작을수록 좋다. 즉, 하나의 객체가 제공하는 기능이 적은 것이 좋다.

하나의 객체에 너무 많은 기능이 포함되어서 그 객체의 책임이 커지는 경우에, 그 기능과 관련된 데이터들이 전부 한 객체로 몰리게 된다. 또한 기능들이 그 데이터를 공유하는 방식으로 프로그래밍이 될 수도 있는데, 이는 절차 지향 방식과 다를 것이 없다. 이를 잘 표현한 것이 SRP이다.

의존성

한 객체가 다른 객체에 의존한다는 것은, 특정 객체에서 다른 객체의 메소드를 호출하거나 하는 것을 의미한다. 이러한 의존은, 꼬리에 꼬리를 물며 전파될 수도 있는데, 결국 자기 자신에게까지 영향을 미치게 되는 것을 순환 의존이라고 한다. 이는 DIP 방식으로 해결한다.

캡슐화

객체가 내부적으로 기능을 어떻게 구현하는지를 감추는 것이다. 내부 구현이 변경되더라도, 그 기능을 사용하는 코드는 영향을 받지 않도록 해야 한다. 내부 구현 변경의 유연함을 가져다주는 기법이 캡슐화이다.

OOP에서는 캡슐화를 통해, 어떤 한 곳의 변화가 다른 곳에 미치는 영향을 최소화 한다.

이때 두 개의 규칙이 있다.

1. Tell, Don't ask -> 데이터를 읽으려고 하지 말고 기능을 실행하라는 것이다. 즉 데이터를 읽더라도 메서드를 통해 데이터를 반환하도록 구현하는 것. 데이터를 읽는 것은 데이터를 중심으로 코드를 작성하게 만드는 원인이 된다.

2. 데미테르 법칙

메서드에서 생성한 객체의 메서드만 호출

파라미터로 받은 객체의 메서드만 호출

필드로 참조하는 객체의 메서드만 호출

객체 지향 설계 과정

1. 제공할 기능을 세분화하고, 기능을 적절한 객체에 구현(할당)한다.

2. 필요 데이터를 객체에 추가한다.

3. 그 데이터를 활용하는 기능을 추가한다.

4. 이때 최대한 캡슐화하여 구현한다.

5. 객체 간에 메시지를 어떻게 주고받을지 결정한다.

OOP의 전반적인 장점

OOP 방식으로 코드를 작성하면, 사전에 작성한 코드에 대한 재사용성이 높아지게 된다. 자주 사용되는 로직(기능, 코드)를 라이브러리 혹은 모듈화 해서 사용할 수 있으며, 이것이 사전에 제대로 만들어졌다는 가정하에 신뢰성을 확보할 수 있다.

또한 라이브러리를 각종 예외 상황에 대비하여 잘 만들어두었다면, 컴파일 단계에서 에러를 잡아낼 수 있기 때문에 버그 발생이 줄어든다? -> (이 부분은 피부로 잘 와 닿지 않는다)

아무튼 라이브러리화 해서 사용하면, 그것을 가져다 쓰는 개발자는, 그 라이브러리가 어떻게 작동하는지 내부적인 작동 원리를 모르고도 그 기능을 가져다 쓸 수 있기 때문에, 생산성이 높아진다.

또한 객체 단위로 코드를 나눠서 작성하기 때문에, 유지 보수와 디버깅에 용이하다.

또한 데이터 모델링 시에 객체와 매핑하는 것이 수월하기 때문에, 요구사항을 보다 명확하게 파악하여 프로그래밍할 수 있다. -> (이 부분도 명확히 와 닿지 않음)

OOP의 단점(문제점)

객체 간의 정보 교환이 모두 메시지 교환을 통해 일어나는데, 이는 시스템에 많은 overhead를 준다.

하지만 이 부분은 하드웨어의 발전으로 상당 부분 보완되었다고 한다.

치명적인 단점은, 함수형 프로그래밍 패러다임의 등장 배경을 통해서 알 수 있다. 문제는 객체가 상태를 갖는다는 것이다. 어떤 변수가 존재하고, 그 변수를 통해서 객체가 예측할 수 없는 상태를 갖게 되어 애플리케이션 내부에서 버그를 발생시킨다는 것이다. 이러한 문제로, 최근 함수형 패러다임이 주목받고 있다.

상속을 통한 재사용의 단점

1. 상위 클래스의 변경이 어렵다

많은 클래스가 상속하고 있는 상위 클래스가 변경되면, 하위 클래스에 영향이 퍼지게 된다.

2. 기능 확장을 하면서 클래스의 개수가 증가한다. -> 근데 이걸 피하려면 하나의 클래스 안에 많은 기능을 넣어야 하는데, 충돌하는 거 아닌가?

상속에서 나오는 문제를 해결하는 것이 조립(Composition)

단점: 런타임 구조가 복잡해진다.

상속보다 구현이 어렵다.

구조 / 구현이 복잡하더라도, 변경의 유연함이 상속보다 크기 때문에 먼저 고려된다.

상속을 사용할 때는, 재사용의 관점이 아니라 기능 확장의 관점에서 적용해야 한다.

객체 지향적 설계 원칙

1. SRP(Single Responsibility Principle) : 단일 책임 원칙

  클래스는 단 하나의 책임을 가져야 한다. 또한 클래스를 변경하는 이유는 단 하나의 이유이어야 한다.

2. OCP(Open-Closed Principle) : 개방 - 폐쇄 원칙

  확장에는 열려 있어야 하고, 변경에는 닫혀 있어야 한다.

3. LSP(Liskov Substitution Principle) : 리스코프 치환 원칙

  상위 타입의 객체를 하위 타입의 객체로 치환하더라도, 상위 타입을 사용하는 프로그램은 정상 동작해야 한다.

4. ISP(Interface Segregation Principle) : 인터페이스 분리 원칙

  인터페이스는 그 인터페이스를 사용하는 클라이언트를 기준으로 분리해야 한다.

5. DIP(Dependency Inversion Principle) : 의존 역전 원칙

  고수준 모듈은 저수준 모듈의 구현에 의존해서는 안된다.

참고한 링크

https://asfirstalways.tistory.com/177, https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Development_common_sense#%ED%95%A8%EC%88%98%ED%98%95-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D

기본적인 데이터 타입과 자료형에 관해서 간략히 정리하고자 한다.

정말 기본적인 특성도 이 글에서 함께 정리하려고 한다.

1. 먼저 변수란 데이터를 참조하기 위해 메모리 주소를 대신하는 별명 정도로 이해하면 된다.

2.python에서는 문자와 문자열을 구분하지 않는다. str 형으로 통합되어 있다.

3. 정수를 사용할 경우, c++에서는 int형은 약 +-21억 정도 사용할 수 있었던 것으로 기억하는데

파이썬의 경우 메모리가 허용하는만큼 수를 크게 사용할 수 있다.

4. 하지만 실수의 경우에는 8바이트 선에서 표현된다.

5. 형변환을 할 때에는 int(str형) 과 같은 방식으로 한다.

6. C++에서 처럼 나눗셈 연산을 할 때 기본적으로 버림을 하지 않는다. 몫만 구하는 연산자가 // 로 정의되어 있다.

7. .format을 활용한 출력은 아래 코드에 정리되어 있다.

이런식으로 쓰기도 가능

8. else if를 의미하는 것이 elif

9. range(0, 10, 1) 0부터 시작해서 10보다 작을동안 1씩 증가하면서

아래로는 컨테이너 자료형에 대한 정리이다.

1. 튜플은 리스트와 비슷하다. 차이점은 튜플은 데이터를 수정할 수 없다는 것이다.

길이를 구하고, 튜플끼리 결합하고, 슬라이싱, 인덱스를 활용한 접근, 특정 데이터가 몇 개 있는지 확인 등은 모두 가능하다

2. 딕셔너리: {}로 표현되고, key value 페어로 데이터가 관리된다.

https://programmers.co.kr/learn/courses/30/lessons/17678

콘이 탈 수 있는 가장 늦은 셔틀버스를 타고 가려면, 몇시에 줄을 서야 하는지를 구하는 문제이다.

다음과 같은 방식으로 생각해 볼 수 있다.

기본적으로 가장 늦은 버스를 탄다는 것은, 막차를 탄다는 것이다. 따라서 막차에 자리가 있으면 그냥 막차를 타면 된다.

막차에 자리가 없는 경우를 생각해보면, 버스를 가장 늦은 시각에 탄 사람보다, 1분 더 빨리 나와서 버스를 타면 탈 수 있는 가장 마지막 순간에 버스를 타게 된다.

동일 시각이라도 콘은 가장 뒤에 줄을 선다고 했기 때문에, 1분 더 빨리 나와서 버스를 타면 되겠다.

위 두가지 경우로 구현을 해주면 되겠다.

https://programmers.co.kr/learn/courses/30/lessons/17680

현재 캐시의 크기와, 사용 빈도에 관련된 정보를 배열을 활용해서 계속 검사해주며 miss와 hit 여부를 판단해주면 된다.

주의할 것은, 대소문자에 상관없이 비교를 하기 때문에 (Seoul과 seoul이 둘 다 입력으로 들어올 수 있는데, 같다고 판단해야 함) 이 부분을 잘 확인하면 된다.

어떤 문자열을 소문자로 변환하는 경우, algorithm 헤더에 있는 transform 함수를 이용한다.

파라미터는 transform(변환할 문자열의 시작주소, 변환할 문자열의 끝주소, 변환 결과를 저장할 문자열의 시작주소, ::변환방식)이다.

transform(ct[i].begin(), ct[i].end(), ct[i].begin(), ::tolower);

이런식으로 사용해준다.

1. std::transform을 쓰는 방법

#include <algorithm>
#include <string>

std::string str = "Hello World";
std::transform(str.begin(), str.end(),str.begin(), ::toupper);

범위에 있는 모든 원소에 대해 function을 수행한 결과를 다른 범위에 저장

toupper 혹은 tolower 앞에 :: 꼭 붙어야한다.

원형은

template< class InputIt, class OutputIt, class UnaryOperation >
OutputIt transform( InputIt first1, InputIt last1, OutputIt d_first,
                    UnaryOperation unary_op );

//또는

template< class InputIt1, class InputIt2, class OutputIt, class BinaryOperation >
OutputIt transform( InputIt1 first1, InputIt1 last1, InputIt2 first2, 
                    OutputIt d_first, BinaryOperation binary_op );

파라미터

• first1, last1 : transform 할 첫 번째 원소
• first2 : transform 할 2번째 범위의 첫 번째 원소
• d_first : transform 결과를 저장할 범위의 첫 번째 위치
• unary_op : 객체를 바꾸는 unary 함수
• bianry_op : 객체를 바꾸는 binary함수

https://programmers.co.kr/learn/courses/30/lessons/17682

문자열에서 숫자를 골라내야 하는데, 이 때 10이 포함된 경우를 잘 확인해주면 된다.

https://www.acmicpc.net/problem/11328

문자열을 무작위 재배열해서 반환하는 함수에 대한 문제이다.

두 문자열의 알파벳 성분이 일치하면 되기 때문에, 각 문자열을 이루는 알파벳의 개수를 파악해주면되겠다.

입력은 소문자로만 들어온다는 것을 확인하고, 각 문자열의 알파벳 개수를 파악해주자.

#include<string>
#include<iostream>
using namespace std;
int alpSrc[26], alpDes[26];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tc;
	cin >> tc;
	string src, des;
	bool res = true;
	while (tc--) {
		
		cin >> src >> des;
		for (int i = 0; i < src.length(); i++) {
			alpSrc[src[i] - 'a']++;
			alpDes[des[i] - 'a']++;
		}
		res = true;
		for (int i = 0; i < 26; i++) {
			if (alpSrc[i] != alpDes[i]) {
				res = false;
				break;
			}
		}
		if (res)
			cout << "Possible" << '\n';
		else
			cout << "Impossible" << '\n';

		for (int i = 0; i < 26; i++) {
			alpSrc[i] = 0;
			alpDes[i] = 0;
		}
	}
	return 0;

문제 링크이다.

https://www.acmicpc.net/problem/11722

풀면서 정답률이 이렇게 높게 나올 문제인가 하면서 자책했는데,

가장 긴 증가하는 부분 수열이라는 문제가 있어서 정답률이 상대적으로 높았던 것 같다.

(문제 풀이)

먼저 배열을 입력받고, 데이터들을 앞에 있는 모든 성분들과 비교해야 한다.

10 30 10 20 20 

위와 같이 배열이 주어졌다고 하면.

3번째 수인 10을 10과 30 모두와 비교하고, 20은 다시 처음부터 10, 30, 10 이런식으로 

이전에 나온 수들과 비교해야 한다.

즉 앞에서 해결한 문제가 뒤의 문제를 해결할 때 사용되기 때문에 dp라는 감을 잡고 접근하면 되겠다.

d[i]를 index i까지의 수를 활용해서 만들 수 있는 감소수열의 최대 길이라고 정한다.

확인하는 숫자가 이전 숫자보다 크다면 이전까지 나온 감소 수열의 길이에 영향을 미치지 않기 때문에 넘어가 주고, 

이전 숫자보다 작다면 처리를 해주면 된다.

길이의 최댓값을 찾고 있기 때문에, d[i]의 갱신도 최대 길이일때만 해주면 된다.

즉 위의 예시에서, 4번째 수인 20에 대한 처리를 한다고 해보자.

먼저 20은 10보다 크기 때문에 넘어간다.

이어서, 20은 30보다 작다 -> 30인 지점에서 감소 수열의 길이는 1이다. (엄밀히 말하면 0이라고 생각하지만 풀이의 간편성을 위해 1이라고 했다). 그렇다면 30까지의 수열과, 20이 연결되어서 수열의 길이는 1이 증가하게 되고, 수식으로 표현하면 d[20의 인덱스] = d[30의 인덱스] + 1 이다.

이것도 확정이 아니라, 만약 같은 방식으로 20보다 큰 30과 같은 수가 20의 이전에 여러개 나올 수 있는데,

d[20의 인덱스] = d[20보다 크고, 20보다 앞에 나온 수의 인덱스] + 1 이것들을 비교해서 최댓값을 d[20의 인덱스]로 결정해주면 된다.

#include<iostream>
using namespace std;
int d[1002];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	int arr[1002];
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	for (int i = 1; i <= n; i++) {
		int Max = 0;
		for (int j = 0; j < i; j++) {
			if (arr[i] < arr[j]) {
				//작은 인덱스의 값보다 더 작은 값이 들어오면
				if (d[j] > Max) {
					Max = d[j];
				}
			}
		}
		d[i] = Max + 1;
	}
	
	int Max = 0;
	for (int i = 1; i <= n; i++) {
		if (Max < d[i]) {
			Max = d[i];
		}
	}
	cout << Max << '\n';
	
	return 0;
}