<div id="readability-page-1" class="page"><div><h2 id="array"><a href="#array" aria-label="array permalink"></a>Array</h2>
메모리 상에 원소를 연속하게 배치한 자료구조
<h3 id="성질"><a href="#%EC%84%B1%EC%A7%88" aria-label="성질 permalink"></a>성질</h3>
<ol>
<li>O(1)에 k번째 원소를 확인 / 변경 가능</li>
<li>추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음</li>
<li>Cache hit rate가 높음</li>
<li>메모리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸림</li>
</ol>
<h3 id="시간복잡도"><a href="#%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84" aria-label="시간복잡도 permalink"></a>시간복잡도</h3>
<ul>
<li>임의의 위치에 있는 원소를 확인/ 변경 : O(1)</li>
<li>원소 끝에 추가 : O(1)</li>
<li>임의의 위치에 원소를 추가, 제거 : O(N)</li>
</ul>
<h3 id="️예제문제"><a href="#%EF%B8%8F%EC%98%88%EC%A0%9C%EB%AC%B8%EC%A0%9C" aria-label="️예제문제 permalink"></a>✍️예제문제</h3>
배열 insert, erase 함수 구현하기
<blockquote>
insert
</blockquote>
<div data-language="cpp"><pre><code>void insert(int index, int num, int arr[], int&amp; len) {
	for(int i = len; i &gt; index ; i--) arr[i] = arr[i - 1];
	arr[index] = num;
	len++;
}</code></pre></div>
<blockquote>
erase
</blockquote>
<div data-language="cpp"><pre><code>void erase(int index, int arr[], int&amp; len) {
	len--;
	for(int i = idx; i &lt; len; i++) arr[i] = arr[i + 1] ;
}</code></pre></div>
전체를 특정 값으로 초기화시킬 때 어떻게 하면 효율적으로 할 수 있을까? 🤔
⭐⭐ fill 함수 사용
<div data-language="cpp"><pre><code>// fill(array, array+sizeOfArray, number);
int a[21];
fill(a, a+21; 0);</code></pre></div>
<hr>
<h3 id="️예제문제-1"><a href="#%EF%B8%8F%EC%98%88%EC%A0%9C%EB%AC%B8%EC%A0%9C-1" aria-label="️예제문제 1 permalink"></a>✍️예제문제</h3>
<blockquote>
알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오.
</blockquote>
<div data-language="cpp"><pre><code>int count[26] = {};
 string str;
 cin &gt;&gt; str;
 for(int i=0;i&lt;str.size();i++) {
 count[str[i] - 'a']++;
 }
 for(int i = 0;i&lt;26;i++) {
 cout &lt;&lt; count[i] &lt;&lt; " ";
 }</code></pre></div>
<blockquote>
주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라. arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다.
</blockquote>
<div data-language="cpp"><pre><code>int func2(int arr[], int N) {
 int count[101];
 for(int i=0;i&lt;N;i++) {
 count[arr[i]] = 1;
 // if(count[100 - i])
 if(count[100 - i] == 1) return 1;
 }
 return 0;
}</code></pre></div></div></div>

Seulog💘

이예슬

Array
메모리 상에 원소를 연속하게 배치한 자료구조
성질
O(1)에 k번째 원소를 확인 / 변경 가능
추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음
Cache hit rate가 높음
메모리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸림
시간복잡도
임의의 위치에 있는 원소를 확인/ 변경 : O(1)
원소 끝에 추가 : O(1)
임의의 위치에 원소를 추가, 제거 : O(N)
✍️예제문제
배열 insert, erase 함수 구현하기
insert
void insert(int index, int num, int arr[], int& len) {
	for(int i = len; i > index ; i--) arr[i] = arr[i - 1];
	arr[index] = num;
	len++;
}
erase
void erase(int index, int arr[], int& len) {
	len--;
	for(int i = idx; i < len; i++) arr[i] = arr[i + 1] ;
}
전체를 특정 값으로 초기화시킬 때 어떻게 하면 효율적으로 할 수 있을까? 🤔
⭐⭐ fill 함수 사용
// fill(array, array+sizeOfArray, number);
int a[21];
fill(a, a+21; 0);
✍️예제문제
알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오.
int count[26] = {};
 string str;
 cin >> str;
 for(int i=0;i<str.size();i++) {
 count[str[i] - 'a']++;
 }
 for(int i = 0;i<26;i++) {
 cout << count[i] << " ";
 }
주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라. arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다.
int func2(int arr[], int N) {
 int count[101];
 for(int i=0;i<N;i++) {
 count[arr[i]] = 1;
 // if(count[100 - i])
 if(count[100 - i] == 1) return 1;
 }
 return 0;
}

Array

댓글