0x03강 - 배열

배열-메모리 상에 원소를 연속하게 배치한 자료구조

그래서 vector를 이 강의시간에 배우는 이유는, vector가 연속적으로 배치한 자료구조이기 때문이구나. 

 

배열의 성질

 

1. O(1)에 k번째 원소를 확인/변경 가능 -- 연속적으로 배치한 자료구조이기 때문

2.  추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 

3. Cache hit rate가 높음 

4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸린다. 

 

 

 

배열에서 새로운 원소를 추가하는 상황  O(N)

평균적으로는 O(N/2)가 되겠지만 O(N)이라고 해도 상관없다. 

 

 

제거시에도 마찬가지다

 

배열을 직접 구현해보는 코드를 작성해볼때 예시를 들어보면

여기서 정확하게 알고 넘어가야 할 부분은 int idx는 0,1,2,3,4,5로 사용하는 어레이의 원소에 접근하는 번호이고

len은 arr에 있는 원소의 갯수를 나타낸 수이기 때문에 6이라는 것이다. 

그렇기 때문에 insert(3,60,arr,len);에서 3은 3번째 라고 생각하지 말고, arr[ ]의 시작 인자에서 얼만큼 떨어져있는지로 생각해서 3만큼 떨어져있는 인자, 그렇기 때문에 4번째 인자에 대한 접근으로 이해하고 가야한다. 

idx와 len의 차이를 확실하게 이해하고 넘어가도록 하자. 이 차이를 확실하게 이해하지 못하면 숫자 하나차이로 확연하게 다른 접근을 하게 될것이다. 

 

erase함수를 구현할때는 insert를 구현할때와는 다르게 len--;을 먼저 실행해주어서 마지막 없어질 부분에 대한 접근을 없앤뒤에 len--을 해주었기 때문에 i<len으로 처리해서 for문을 돌리면 된다. 

 

**전체를 특정 값으로 초기화 시킬때의 팁** 

중요한 사항이다 

전체를 특정 값으로 초기화 시키는 3가지 방법.

 

1.memset 사용하기

2. for문 사용하기

3. fill 사용하기

 

 

1번 cstring 헤더에 있는 memset 함수 활용하는 방식. 

 그런데  memset 함수는 실수할 여지가 굉장히 많다. 

예를들어 0이나 -1이 아닌 다른 값을 넣으면 오동작한다거나, 2차원 이상의 배열을 함수의 인자로 넘겨

그곳에서 memset을 하면 잘못 들어간다거나 하는 점들이 있다. 

 그래서 memset은 비추천 한다. 

 

2번째로 for문을 돌면서 하나하나 바꾸어주는 방법인데 코드가 투박하지만 실수할 여지가 없기 때문에

무난하고 좋다. 

 

3번째로 algorithm헤더의 fill 함수를 이용하는 것이고, fill함수는 실수할 여지도 별로 없고 코드도 짧으니

익숙해진다면 가장 추천하는 방식. 

 

결국 배열을 설정하고 그 값을 일정한 값으로 초기화를 다 해줄때에는 algorithm 헤더에 있는 fill 함수를 사용하여서 

초기화를 해주도록 하자. 그 방법을 숙달하고 그 방법을 일관되게 사용하도록 하자. 

 

STL vector

STL vector

vector는 배열과 거의 동일한 기능을 수행하는 자료구조로, 배열과 마찬가지로 

원소가 메모리에 연속하게 저장되어 있기 때문에 O(1)에 인덱스를 가지고 각 원소로 

접근할 수 있다. 그런데 vector는 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있다는 장점이 있다. 

후에 그래프의 인접 리스트 라는것을 저장할때에는 vector를 쓰는것이 많이 편해서 vector가 필요하게 되지만

그 전까지는 사실 굳이 배열 대신 vector를 써야 하는 상황이 딱히 없다. 

 

위에 예시를 든 vector 사용 프로그램에서 알 수 있는 STL vector의 사용방법들을 나열해보면

 

vector<int> v1(3,5); //3개의 인자를 가지는 벡터를 만들고 각 인자를 5한다. 

v1.size(); // vector에 있는 인자의 갯수를 알려준다. 

v1.push_back(7); // {5,5,5,7} 푸시는 밀어 넣는것이고, 백은 뒤에다 이므로, 맨 뒤에 7 이라는 인자를 밀어넣어서 벡터에 추가한다

 

vector<int> v2(2); // {0,0}--> 2개의 원소를 가진 vector를 정의하고, 초기에 원소의 값을 지정해주지 않아서 0으로 초기화한다. 

v2.insert(v2.begin()+1,3); // {0,3,0}; --> v2.begin()은 가장 처음 원소의 위치를 나타내고, insert는 몇번째 위치에 어떤 인자를 넣을지를 수행한다. 

 

vector<int> v4; // { } --> vector를 선언할때 아무것도 지정하지 않으면 원소가 비어있는 vector로 만들어진다

v4=v3; // {1,2,4} 이런식으로 vector에 vector를 대입하여서 값을 복사해서 대입할 수 있다. 

cout<<v4[0]<<v4[1]<<v4[2]<<'\n'; //124 --> arr[]에서 각각의 인자에 인덱스번호로 접근하듯이 각각의 벡터에 인덱스번호로 접근해서 출력 할 수 있다. 

v4.pop_back(); //{1,2} pop이란건 빼내는거고, back은 뒤니까, pop_back은 맨 뒤에있는 인자를 빼는 것이다. 

v4.clear(); //{ } --> clear는 깨끗하게 정리하는 것이므로 vector에 있는 인자들을 모두 제거하고 null로 만든다. 

 

STL iterator

 

STL의 iterator에 대한 공부가 필요하다고 한다. 이 부분에 대해서는 따로 찾아서 공부하도록 하자. 

https://blankspace-dev.tistory.com/348

[STL] STL 반복자 정리 (iterator)

반복자에 대한 블로그 글을 첨부한다. 한번씩 가서 확인하고 습득하도록 하자. 

위 게시글에서 주의해야할 부분은 [begin,end)라는 포함관계를 잘 알고있어야 한다는 것으로 보인다. 

맨 마지막은 제외되고 있는데, 많은 함수들에서 이런식으로 포함관계를 설정하여서 이미 만들어놓은 함수들을 볼 수있다. 

포함관계를 항상 주의하도록 하자. 만들어놓은 함수들, 혹은 메서드를 사용할때 포함관계를 어떻게 설정해놓았는지 확인해보고 사용하는 습관을 들이도록 하자. 

vector에는 push_front, pop_front가 없다

재미난 부분은 push_back과 pop_back은 있는데, push_front, pop_front는 없다는 것이다. 

맨 뒤와 관련된 함수들은 있는데, 앞과 관련된 함수들은 없다. 

이걸 명심하도록 하자. 

 

 

vector에서 =를 사용하면 deep copy가 발생한다. 16번째 줄에서 v4는 {1,2,4}가 되었고, 이후v4를 바꿔도

v3에는 영향을 주지 않는다.

 

<vector에 있는 모든 원소를 순회할때의 사용방법>

vector에 있는 모든 원소를 순회하는 방법들

 

vector에 있는 모든 원소를 순회하려고 할때, range-based for loop를 이용할 수 있다. 

04,05번째 줄처럼 int e:v1 이라고 하면 e에 v1의 원소들이 하나씩 들어가는 for문이 된다. 

 

지금은 값을 바꾸지 않고 그냥 출력만 해서 별 상관이 없지만, 만약 int e: v1 이라고 하면 복사된 값이 e에 들어가고, 

int& e: v1이라고 하면 원본이 e에 들어간다. 

그렇기 때문에 int e: v1라고 쓴 for문 내에서 e를 바꿔도 v1에는 영향이 가지 않지만, 

int& e: v1이라고 쓴 for문 내에서는 e를 바꾸면 원본인 v1에서 실제 해당 원소의 값이 바뀌게 된다. 

 

이 기능은 vector뿐만 아니라 나중에 배울 list, map, set 등에서도 모두 사용할 수 있기 때문에 기억해두면 좋은데

다만 이 기능은 C++11부터 추가된 기능이다. 만약 코딩테스트가 C++11을 지원하지 않는다면 사용할 수 없다. 

 

range-based for loop가 그다지 익숙하지 않다면 아주 무난하게 for문으로 인덱스를 하나씩 다 돌아도 상관없다.

2번과 3번이 전부 그렇게 처리한 코드인데 3번처럼 쓰면 아주 잘못 될 수 있다. 

 

기본적으로 vector의 size 메소드는 시스템에 따라 unsigned int 혹은 unsigned long long 을 반환한다. 

그렇기 때문에 32비트 컴퓨터 기준 3번같이 쓰면 v1이 빈 vetor일때 v1.size()-1이 unsigned int 0에서 int 1을 빼는 식이 되고, unsigned int와 int를 연산하면 unsigned int 로 자동 형변환이 발생하기 때문에 (unsigned int)0-(int)1은 -1이 아니라

4294967295이 된다. 

4294967295라는 이상한 값은 unsigned int overflow로 인해 생기게 된 값이다. 

 

그래서 아무것도 출력을 하지 않고 종료되는 것이 아닌, v1[0],v1[1],v1[2],... 이렇게 i가 계속 커지다가 어느 순간 런타임에러가 발생하게 될 것이다. 

 

정리하자면 vector에 있는 모든 원소를 순회하고 싶으면 range-based for loop를 사용해도 되고 그냥 인덱스를 하나씩 다 돌아도 상관없는데, size 메소드의 반환값이 unsigned이기 때문에 3번처럼 구현하면 큰일난다는 것이다. 

 

BOJ 10808번: 알파벳 개수

소스코드

이 코드를 보면서 내가 익혀야 할 부분은, 

string s;로 정의한 s에 

제시된 스트링을 받아들이게 만드는 부분은

cin>>s;로 처리하면 글자들의 연속인 스트링을 받아들이고, 

알파벳들을 하나씩 증가시키면서 체크할 수 있게 만드는 부분은

for(char a='a'; a<='z'; a++) 와 같이 표현할 수 있으며( 이때 char a에서 a라는건 꼭 a일 필요가 없이 그저 변수명일 뿐이다)

int cnt에서 cnt라는건 count를 나타내어서 숫자를 세기 위한 변수명이고, 

for(auto c: s) 의 형태를 통해서 

range-base for loop 형태로 for루트를 도는데 이때 string s의 내부 글자별로 for문을 돌 수 있게 만들어주고, 

그 각각의 판별마다 if(a==c) 인경우 cnt++를 시행시켜 준뒤에, 각각의 cnt값을 출력시켜 주는 것이다. 

처음에는 c++이라고 해서 문자열과 각각의 문자를 통한 판별이 굉장히 딱딱하고 숫자적으로 캐스팅해서 접근해야 하는줄 알았는데 막상 코드를 보니 그런식으로 접근하지 않더라도 처리가 가능하다는걸 알 수 있었다. 

 

각각의 알파벳에 대하여 한번씩만 연산되는 풀이

 

아래에 추가된 방법은 각각의 글자들에 대해서 a부터 z까지 쭉 비교하는 연산을 한번씩만 진행해서 찾아내는 과정에 대한 코드이고, 이 방법을 사용하는데 있어서 추가적으로 내가 알아야 할 사항들을 적어보면

일단 freq 배열의 초기값은 0이어야 할텐데 전역에 선언하면 알아서 0으로 채워진다. 

main을 벗어난 영역에서 위에다가 선언해서 모든 배열의 내부값을 0으로 알아서 채워지도록 초기화할 수 있다는걸 알아두도록 하자. 

지역변수 freq[26]이었다면 다른 0이 아닌 쓰레기값이 채워졌을 것이다. 

이걸 한번 main 함수 내에서 freq[26] 을 새롭게 정의해서 비교해보도록 하자. 

지역변수로 초기화를 하지 않고 실행한 프로그램의 모습

 

전역변수면 0으로 자동으로 초기화 되는데,  지역변수로 초기화 없이 프로그램을 작성한뒤에 실행하니까 이런식으로

엉뚱한 값이 들어가서 프로그램이 의도하지 않은 형태로 동작한다. 

지역변수로 설정해서 이런식의 프로그램을 만들기 위해서는 int freq[26]={ } 혹은

fill(freq,freq+26,0);과 같은 조치가 필요했을 것이다. 

이 두가지 과정을 한번 진행해서 어떻게 변하는지 확인해보도록 하자. 

실제로 활용해보니 둘다 아주 잘 동작한다. 

그러니까 이런 문제에서

전역변수로 freq[26];

으로 시작하던지, 아니면 지역변수면 

int freq[26]={};

혹은 

int freq[26];

fill(freq,freq+26,0);

까지 작성해주어야 한다. 

 

이 문제의 시간 복잡도를 O(N)으로 떨어뜨려 보자

 

핵심적인 아이디어

 

각 수의 등장 여부를 체크하는 배열을 만들어서 시간복잡도를 줄이는 방식으로 접근해보자. 

구현 자체는 간단하게 할 수 있다. 

이 문제의 시간복잡도를 줄이는 방법에서의 핵심은, 

아이디어이다. 

차례차례 확인해보면서 이전에 등장했는가? 그렇다면 1을 넣어주고, 아니라면 0으로 놓고 넘어간다

그리고 차례대로 다음 원소에 접근할때마다 같은 절차로 1을 넣어주고, 아니라면 0으로 놓고 넘어간다면

그 과정에서 합이 100이 되는 것을 찾게될것이고, 그렇게 되었을때 1을 출력해주면 되는것이다. 

 

참고로 if(1){}은 1이 참으로 해석되어 중괄호 안의 내용이 실행되고

if(0){}은 0이 거짓으로 해석되어 중괄호 안의 내용이 실행되지 않기 때문에

04번째 줄을 그냥 if(occur[100-arr[i]])로 써도 동일하게 동작한다. 

 

10807번 문제

 

풀어보라고 제시된 문제에서 10807번 문제에서 소스코드를 보았을때 내가 익힐만한 부분이 있어서 기록해보자면, 

16번째 줄을 보면, 처음 받은 인풋 N의 값을 이용해서 N번만큼 반복문을 돌고싶을때, 

while(N--)라는 식으로 작성하게 되면, 

N=11인 경우라고 예를 들어보면, 11번의 while내부의 값을 반복할 수 있게 된다. 

저번에 실험해보았을때도 N--형태로 식을 작성할때, N=5라면 5번의 반복실행을 하게 되는것을 확인하였다.

저런 식의 표현을 익히고 잘 활용하도록 하자. 

 

 

배열의 원소로 음수를 제공하는 문제의 경우 인덱스 처리 방법

그리고 20번째줄과 21번째 줄을 보면 배울수 있는 부분은, 

원소들을 음의 정수까지 확장해서 제시해 주는 문제에서, 각 배열에 인덱스로 접근하기 위한 방법으로, 

기존 인덱스+100으로 배열에 인덱스 번호를 매겨서 저장하게 되면, 각각의 음수로 제공해주는 원소들도 +100이라는

과정을 통해서 인덱스로 접근할 수 있는 방법을 알 수 있다. 

이런 방법을 처음부터 생각해내고자 한다면 쉽지 않을 수 있다. 

이러한 방법을 잘 기억하고 있다가 다음에 음수까지 확장된 영역의 원소를 제공하는 문제에서 인덱스 표현 방법을 사용할때 활용하도록 하자. 

 

결국 이 문제의 경우는 각각의 수가 주어질때 그걸 그 수에 배정된 각각의 배열의 원소 그릇에

숫자를 증가시켜서 표시해놓고, 마지막에 제시된 어떤 그릇을 출력할지에 따라서 그 그릇에 차곡차곡 쌓인

등장 횟수를 출력하면 되는 것이다.