자료구조 스터디-1주차

1-1)배열과 리스트

파이썬의 리스트는 배열의 특성도 내포하고있음. 파이썬에서의 리스트는 배열의 특성까지 가지게 구현되어있음. 

인덱스로 접근이 가능하고 가변적으로 변하는 크기라는 장점만 가지고있다.

 

자료구조에서 배열: 메모리의 연속된 공간에 값이 채워져있는 형태의 자료구조. 값을 인덱스를 통해 직접 접근할 수 있다.

새로운 값의 삽입이나 삭제가 어렵다는 단점이 있다.

배열의 크기는 선언시에 지정할 수있으며 한번선언한 이후 크기를 조절할 수 없다.

 

자료구조에서 리스트: 값과 포인터를 묶은 노드라는것을 포인터로 연결한 자료구조. 값에 접근하려면 인덱스가 없기때문에 head 포인터로부터 순차적으로 접근해야한다는 단점이 있다. 포인터로 연결되어 데이터 삽입삭제의 속도가 빠르고 선언할 때 별도의 크기를 지정하지 않아도 돼 크기가 변하는 데이터를 다룰 때 적합하다는 장점이 있다.

 

1-2)백준 11720

 

연속된 숫자를 리스트 형태로 입력받는다. 리스트의 각 요소를 for문을 통해 탐생하고 그 값을 정수형으로 변환해 sum에 더해줘 문제를 해결하였다. 

 

1-3) 구간합

구간합은 합 배열을 이용하여 시간복잡도를 더 줄이기 위해 사용하는 특수 목적의 알고리즘.

s[i] = a[0] + a[1] + ,,, + a[i]

s[i]는 배열 a의 0부터 i번째 까지 구간의 합을 의미함.

일반적으로 s[i]로 표현

 

합배열을 만드는 공식

s[i] = s[i-1] + a[i]

 

s[0]은 a[0]과 같을 수 밖에 없음.

s[1]의 값은 s[0]의 값에 a[1]의 값을 더한 결과와 같음.

s[2]의 값은 s[1]의 값에 a[2]의 값을 더한 결과와 같음.

...

 

구간합을 구하는 공식

s[j] - s[i-1]

 

i 부터 j까지 구간의 합을 구하는 공식

 

1-4)백준 11660번

 

문제를 구하는 횟수가 많아졌을 경우 그때그때 정답을 계산하면 시간복잡도 측면에서 불리해질 수있음. 정답을 한번에 만들어놓고 출력하는 방법이 유리하다. 2차원 구간합 배열의 이용하여야함

D[x][y]는 (0,0)부터 (x,y)까지사각형 안에있는 수의 합을 의미한다.

 

2차원 배열의 구간합을 구하는 공식

i,j 부터 n,m구간 내 원소 합을 구할 경우

D[i][j]= D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]

로 D 이차원 배열에 구간합을 구한다

result=D[x2][y2]-D[x1-1][y2]-D[x2][y1-1]+D[x1-1][y1-1]로 구하고자하는 계산값을 구해 출력한다

 

1-5)백준 10986

연속된 부분의 합이 m으로 나눠떨어지는 구간의 개수를 구하기.

특정 구간 수들의 나머지 연산을 더하여 나머지 연한산 값이 구간합의 나머지 연산값과 같음을 활용.

s[i]와 s[j]의 나머지 연산의 값이 같을 경우 원본 리스트의 i+1 부터 j 원소까지의 구간합의 나머지 연산값이 0임을 의미함.

 

합배열 S와 같은 나머지의 인덱스를 카운트하기위한 리스트 C를 선언해준다.

 

for i in range(n) 합배열을 나머지 연산한 결과를 reminder변수 안에 저장해준다.

만약 나머지 연산 결과가 0이라면 C[reminder]를 1 증가시킨다.

 C[i]에서 2개를 뽑는 경우의 수를 정답에 더한후 정답값을 출력해주면 문제를 해결할 수 있다.

 

 

1-6)백준11003

최솟값 찾기

n개의 숫자와 l이 주어짐.

인덱스를 하나씩 넘어가며 0번인덱스에는 그냥 출력, 1번 인덱스는 0,1번을 비교하여 최솟값 출력, 2번 인덱스에서는 0,1,2를 비교하여 최솟값을 출력하는 방식의 문제.

숫자가 500만개까지 주어질 수 있기때문에 시간복잡도에 걸리지 않게 하는게 포인트.

따라서 정렬을 하기에는 시간복잡도 문제가 있어 데크를 사용하여 문제를 풀기.

데크에서는 (인덱스,숫자)형식으로 노드를 추가

뒤에서부터 노드를 비교하여 숫자에 저장된 데이터가 입력된 데이터보다 크다면 데크에서 삭제하는 처리를 해준다.숫자값이 작은 데이터를 만날때 까지 과정을 반복해준다.

과정중 인덱스의 범위가 슬라이싱 윈도우를 벗어났을 때,기존 노드를 삭제해준다.

숫자 비교와 윈도우 범위 계산이 끝난 데크에서 맨 앞 노드를 출력하면 정답임.

문제해결 방법

for n반복:

1. 나보다 값이 큰 데이터를 제거한다

2.데크의 마지막 위치에 현재값을 저장

3. 데크의 1번째 위치에서부터 l범위를 벗어난 값을 데크에서 제거함

4.데크의 1번째 데이터 출력

 

1-7)스택과 큐

 

스택 : 후입선출.가장 마지막 데이터가 가장 먼저 나감.top은 가장 나중에 들어온 원소를 가리키고 pop()은 top이 가리키는 값을 스택에서 빼옴 s.append(data),s.pop()

큐 : 선입선출.먼저들어온 값이 먼저 나간다. 삽입과 삭제가 양방향에서 이루어짐. 파이썬에서는 일반적으로 데크를 이용하여 큐를 구현함. s.append(data), s.pop()

우선순위큐 : 들어간 순서와 상관없이 우선순위가 높은 원소부터 빠져나감

 

1-8)백준 17298

 

오큰수 NGE(오른쪽에 있으면서 a보다 큰 수 중 가장 왼쪽에있는 숫자,없을 경우는 -1)

 

스택을 이용해서 해결 가능함.

스택에 들어오는 수가 top에 있는 숫자보다 크면 그 수는 오큰수가 된다.

오큰수를 구한 후 오큰수가 존재하는 않는 숫자에 -1를 출력한다.

 

풀이과정

1. 스택이 채워져있고 top보다 새로들어온 숫자가 큰 경우 정답수열에 오큰수 저장 후 pop().

2.현재 인덱스를 스택에 push()하고 다음 인덱스로 넘어감.

3. 앞 두 과정들을 수열의 길이만큼 반복한 다음 현재 스택에 남아있는 인덱스에 -1을 저장함