[5주차] P NP 문제, ArrayList와 LinkedList, Java vs Python

✅ Q1. P-NP 문제란?

집합 P와 NP가 서로 같은지 다른지를 증명하는 문제이다.

(집합 P가 NP의 진부분집합인지 아닌지)

아직 컴퓨터과학의 미해결 문제중 하나이다.

P = NP

P와 NP문제는 모두 결정문제이다.

(결정문제 - 답이 YES 아니면 NO로 딱 떨어지는 문제들 ex. a는 b의 배수인가?)

↔ 함수형문제: 답이 셋 이상이 있는 경우

P문제

결정문제 중, 쉽게 풀리는 문제를 모은 집합

→ 어떤 결정 문제가 주어지면, 다항식 시간(==합리적인 시간) 이내에 그 문제의 답을 YES? NO? 중 하나로 계산해낼수 있는 알고리즘이 존재하면 P문제이다.

NP문제

결정 문제들 중, 적어도 검산을 쉽게 할 수 있는 것을 모은 집합

→ 다항식 시간 이내에 그 문제의 답을 YES? NO?로 계산해낼 수 있는 알고리즘은 없지만, 어떤 결정문제의 답이 YES 라고 할 때, 그것을 검산할 수 있는 시간이 다항식 시간 이내일때의 문제가 NP문제다.

NP문제의 예시

• 해밀턴 경로 문제 (주어진 지도 위의 모든 도시를 한 번씩만 방문하는 경로가 있을까?)
• 주어진 예산으로 주어진 지도의 도시들을 다 방문하고 돌아올 수 있을까?
• 주어진 부울식이 참이 되게 할 수 있을까?
• 주어진 자연수를 인수분해 해라

→ 사람이 하나씩 주먹구구식으로 찾으면 괜찮지만, 쉽게 찾을 수 있는 알고리즘은 없는 문제들

P, NP의 증명

현재, P가 NP의 부분집한인건 확인되었다.

P-NP문제는 P와 NP가 동일한가? 를 묻는 문제이므로 NP가 P의 부분집합인가? 에도 답을 할 수 있으면 된다.

→ 하지만 이 부분이 어렵다

NP-hard 문제

모든 경우의 수를 전부 확인해보는 방법 외에 정확한 답을 구할 수 없는 문제

어떤 문제가 NP (다항식시간에 풀이x) 이면서 NP-hard라면 NP완전문제(NP-complete) 라고 한다.

*NP-Complete

→ 근사 알고리즘, 발견적 알고리즘, MST, 탐욕 알고리즘(Greedy) 등

---

✅ Q2. ArrayList와 LinkedList를 설명하세요.

LinkedList와 ArrayList 비교

ArrayList

• 데이터들이 순서대로 쭉 늘어선 배열의 형식. 중복 허용, 순서 유지, 인덱스로 원소 관리 등 배열과 유사하다.
• 내부적으로 데이터를 배열에서 관리하며, 데이터의 추가와 삭제를 위해 임시 배열을 생성하고 데이터를 복사하는 방법을 사용한다.
• O(N)만큼의 연산 속도가 걸려서 자료의 최대 개수에 영향을 받는다.
  • 크기가 한정되어 있기 때문에 결국 포화 상태에 이를 수 있다.
  • 용량이 꽉 찼을 경우 동적으로 늘어나는 것이 아니라, 더 큰 용량의 배열을 만들어 옮기는 작업을 한다(상당한 연산량 요구).

‼️ 대량의 데이터를 추가/삭제 할 경우, 복사가 많이 일어나게 되어 성능 저하를 일어킬 수 있다.
✅ 각 데이터가 인덱스를 가지고 있기 때문에 데이터 검색에 유리하다.

 

삽입 과정

1. List의 크기를 삽입할 자료만큼 늘리는 연산 수행
2. 삽입될 자료의 위치를 기준으로 기존 데이터들을 뒤로 or 앞으로 이동하는 연산 수행
3. 해당 위치에 자료를 입력한 후 삽입연산 종료

 

삭제 과정

1. 삭제할 자료가 위치한 인덱스의 자료를 삭제
2. 삭제한 자료의 인덱스를 기준으로 그 뒤의 자료들을 이동하는 연산 수행
3. List 맨 마지막이 비어있는 상태로 삭제 완료

---

LinkedList

• 데이터들이 순서대로 늘어선 것이 아니라 자료의 주소 값으로 서로 연결되어 있는 구조

데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있다.

‼️데이터 검색시에는 처음부터 노드를 순회해야 하기 때문에 성능상 불리하다.
‼️포인터 사용으로 인해 저장 공간의 낭비가 있다.
‼️알고리즘이 복잡하다.

✅ArrayList처럼 데이터 추가/삭제 시 불필요한 복사가 일어나지 않아 추가/삭제에 더 유리하다.
✅리스트 내에서 자료 이동이 필요하지 않다.
✅사용 후 기억 장소의 재사용이 가능하다.

 

삽입 과정

1. 추가될 자료의 node 생성 (node[BB])
2. 추가될 자료의 해당 인덱스 이전의 node[33]의 다음 node를 추가될 node[BB]로 설정
3. 추가될 node[BB]의 다음 node를 인덱스 이전 node의 다음 node[AA]로 설정

 

삭제 과정

1. 삭제할 node[33]의 이전 node[66]의 다음 node를 삭제할 node[33]의 다음 node인 [AA]로 설정

---

✅ Q3. Java vs Python 에 대해서 설명 해보세요.

Java vs Python

공통점

• 객체지향언어이다.
• 파이썬과 자바 모두 데이터 과학과 데이터 분석 및 머신러닝 작업을 지원하는 라이브러리 목록을 제공한다.
  → 자바 : 자바 머신러닝, 딥러닝4j, 아파치 스파크, WEKA 3
  → 파이썬 라이브러리: 판다스, 싸이파이, 넘파이, 텐서플로

차이점

1. 정적 타입을 지향하는 대표적 언어 vs 동적 타입을 지향하는 대표적 언어
2. 다중상속의 가능성 → 가능 vs 불가능
3. [JAVA] 다중 상속(multiple inheritance) 이란?
4. 가독성 측면 → 함수, 변수에 대해 자바는 camelCase를 선호, 파이썬은 snake_case를 선호한다. + 파이썬의 코드가 짧고 직관적인 편이다.
5. 컴파일 vs 해석(인터프리터)
6. 연산자 → 덧셈, 뺄셈, 곱셈은 동일
7. 숫자와 문자열의 결합 → 자바에서는 숫자 자동으로 문자열 변환 + 파이썬은 str(숫자) 해야지 에러 발생하지 않음
8. 기타 문법

Java

정적타이핑 언어

자료형(type)을 컴파일 당시에 결정하는 것으로, 변수에 들어갈 값의 형태에 따라 자료형을 사전에 지정해야한다. 컴파일 진행 시 자료형에 맞지 않은 값이 전달되면 컴파일 에러를 발생시킨다. 컴파일 당시에 자료형에 대한 판단을 진행하기 때문에 속도가 빠르며, 타입 에러로 발생하는 문제점을 초기에 발견할 수 있는 장점이 있다.

다중 상속이 불가능

: 자바는 변수를 사용하기 위해 데이터유형을 선언해야 하는 정적 타이핑 언어이다. 이 데이터유형은 명시적으로 변경할 수 없으며 프로그램의 수명동안 유지된다.

컴파일

: 자바는 해석되어야 컴파일이 되는 언어로, 자바 가상 머신(JVM)이 필요하다. → 파이썬보다 실행 속도가 빠른 편이다.

연산자

나누기 연산자 /

public class Divide{
	public static void main(String[] args){
		int a = 2, b = 4;
		System.out.println(a/4);  // 0
		System.out.println((double)a/4); // 0.5
	}
}

→ 자바의 나누기 연산자인 / 를 사용하면 본래 소수점이 나와야 할 것이 몫으로, 즉, 정수 형태로 나온다. 만약 2 나누기 4의 값인 0.5를 구하고 싶다면, (double)로 캐스팅해주는 과정이 필요하다!

제곱 연산 Math.pow()

public class Pow{
	public static void main(String[] args){
		System.out.println(Math.pow(10, 3)); // 1000
	}
}

→ 자바에서의 제곱은 반복문을 통해 곱해주거나 아니면 그냥 계속 곱하거나 Math.pow 메서드를 사용해야 한다.

문장 끝

• 세미콜론(;) 필요함

배열

• 같은 자료형만 들어갈 수 있음

반복문

// while문
int i = 0;
while(i <= 4){
	Syste.out.println(i);
	i++;
}

// for문
for(int i = 0; i < 4; i++){
	System.out.println(i);
}

Boolean 타입

→ true, false

조건문(if, else if, else)

int number = 1;
if(number == 1){
	System.out.println("1입니다.");
} else if(number == 2){
	System.out.println("2입니다.");
} else{
	System.out.println("1, 2가 아닙니다.");
}

Python

동적타이핑 언어

: 파이썬은 변수유형을 선언할 필요가 없는 동적타이핑 언어이다. → 데이터타입이 런타임에 자동으로 정의된다. 또한, 변수의 타입은 프로그램 수명 동안 변경될 수 있다.

다중 상속이 가능

: MRO(Method Resolution Order)로 다중상속이 가능하다.

파이썬(python) - MRO(Method Resolution Order)

해석

: 파이썬은 해석된 언어로, 이 코드를 실행하기 위해서는 코드를 읽고 해석할 수 있는 인터프리터를 설치해야 한다.

→ 파이썬의 강점이자 약점이다. 약점이 되는 이유는 파이썬으로 어떤 것을 만들기 위해서는 외부 도구나 까다로운 프로세스에 의존해야 하기 때문이다. 또한 이러한 특성 때문에 소스 코드 속도가 느리다는 단점이 존재한다. 하지만 CMD, terminal에서 직접 코드를 작성할 수 있다는 장점도 있다.

연산자

나누기 연산자 /

print(2/4) # 0.5
print(2//4) # 0

→ 자바와 달리 파이썬에서는 나누기 연산자 / 을 하면 소수점까지 나온다. 만약 몫을 구하고 싶다면 다시 한 번 나누기 연산자를 붙여 //을 쓰면 된다.

**제곱 연산 ****

print(10**3) # 1000

→ 자바와 달리 파이썬에서는 제곱을 하고 싶으면 곱하기 연산자를 한 번 더 작성해주면 ab가 되고, 이는 Math.pow(a, b)**와 의미가 같아진다.

문장 끝

• 세미콜론(;) 필요하지 않음

배열

• 서로 다른 자료형이라도 배열에 저장될 수 있음 → list = [1, “이", “3]

반복문

# while문
i = 0
while i <= 5:
	print(str(i)+"번")
	i = i + 1
# for문
for i in range(6);
	print(str(i) + "번")

Boolean 타입 입력

→ True, False

조건문(if, elif)

number = 2
if number == 1:
	print("1입니다.")
elif number == 2:
	print("2입니다.")
else:
	print("1, 2가 아닙니다.")