배열
배열은 메모리상에 원소를 연속하게 배치한 자료구조이다.
1. 데이터의 크기를 정해놓기 때문에 추가적으로 소모되는 메모리의 양이 거의 없다.
2. Cache Hit Rate가 높다고 하는데 뭔지 몰라서 찾아봤다.
자주 사용하는 데이터를 빠르게 가져올 수 있는 캐시 메모리에서 원하는 데이터를 가져오려고 할때 그 데이터가 캐시에 존재할 때 Cache hit 이라고 한다.
Cache Hit Rate = Cache hit 횟수 / 총 참조 횟수
깊게 파고들면 끝도 없겠지만 배열은 원소를 메모리상에 연속하게 배치하기 때문에 캐시 적중률이 높다고 한다.
3. 메모리상에 연속한 구간을 잡아야하기 때문에 할당에 제약이 있음
배열을 사용할때 시간복잡도
배열은 연속한 메모리 공간에서 인덱스로 접근 가능하기 때문에,
원하는 위치에 있는 원소를 확인/변경 하는것은 O(1)의 시간 복잡도를 가진다.
가장 끝에 추가/ 삭제를 할때도 O(1) 이다.
하지만 중간에 원소를 삽입/삭제 할때는 그만큼 당기고 밀어야 하기 때문에
삽입/삭제는 O(n)의 시간복잡도를 가진다.
배열의 초기화
int a[10];//쓰레기값
int b[10] = {};
int c[10] = {0};
int d[10] = {0,};
이러면 0으로 전부 초기화가 가능하다.
하지만 0이 아닌 다른 수로 초기화를 해야한다면 얘기가 다르다.
int main()
{
int a[10] = {5,};
for (int i = 0; i < 10; i++)
cout << a[i] << endl;
return 0;
}
이렇게 하면 될거같지만..
안타깝게도 첫번째 요소만 5로 초기화가 되었다.
for문 돌리기
for (int i=0;i<10;i++)
{
a[i] = 10;
}
가장 원초적인 방법으로는 for문을 돌려 초기화 시켜주는 방식이 있다.
memset 함수 이용하기
int main()
{
int a[10] = {5,};
memset(a, 0, sizeof(a));
for (int i = 0; i < 10; i++)
cout << a[i] << endl;
return 0;
}
0이나 -1로 초기화 시켜주는 경우 memset을 이용해도 된다.
하지만 다른 숫자를 넣으면 엉뚱한 숫자로 초기화 된다.
fill , fill_n 함수 이용하기
int main()
{
int a[10] = {5,};
fill(a, a + 10,10);
for (int i = 0; i < 10; i++)
cout << a[i] << endl;
return 0;
}
fill(변경하려는 요소의 시작주소, 종료 주소, 변경 값)
int main()
{
int a[10] = {5,};
fill_n(a, 10,10);
for (int i = 0; i < 10; i++)
cout << a[i] << endl;
return 0;
}
fill_n(변경하려는 요소의 시작주소, 변경하려는 요소의 개수, 변경 값)
아마 이 두 함수를 쓰는것이 제일 좋을 것 같다.
배열 문제 풀어보기
백준 1475번 - 1475번: 방 번호 (acmicpc.net)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int Room[9] = { 0, };
int N = 0;
int Cnt = 0;
cin >> N;
while (N > 0)
{
if(N%10 == 9) Room[6]++;
else
Room[N%10]++;
N /= 10;
}
Room[6] = (Room[6] + 1) / 2;
for (int i = 0; i < 9; i++)
{
if (Room[i] > Cnt)
Cnt = Room[i];
}
cout << Cnt;
return 0;
}
굳이 문에 플라스틱 숫자로 방번호를 붙인다고 한다.
0번부터 9번까지의 숫자가 1세트인데, 주어진 방번호를 문앞에 붙이려면 이 세트가 몇개 필요한지를 구해야한다.
까다로운건 6과 9는 서로 뒤집어서 쓸 수 있다는 점이다.
배열을 선언하고 방번호를 하나하나 잘라가며 해당 인덱스를 ++ 해주었다.
하지만 6번과 9번은 뒤집어서 쓸 수 있으니, 9가 들어오면 6번 인덱스를 ++ 해주었다.
6번째 요소만 몇 세트가 필요한지 계산해서 넣어주었고,
for문을 돌면서 최대값을 찾게 했다.
최대값이 곧 최소로 필요한 세트의 수 이기 때문에 그 수를 출력하였다.
백준 3273번 - 3273번: 두 수의 합 (acmicpc.net)
#include<bits/stdc++.h>
using namespace std;
int Res[2000001];
int Input[100001] = {};
int main()
{
int n = 0;
int x = 0;
int Cnt = 0;
cin >> n;
for (int i = 0; i < n; i++)
cin >> Input[i];
cin >> x;
for (int i = 0; i < n; i++)
if (x-Input[i] > 0 && Res[x - Input[i]] == 1) Cnt++;
else Res[Input[i]] = 1;
cout << Cnt;
return 0;
}
간단한 문제라고 생각했지만 정답 비율이 상당히 낮아서 흠칫했다.
처음엔 2중 for문을 돌려서 해결하려고 했다가 시간 초과가 떴다.
아마 조건이 (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 커서 그런것 같았다.
그래서 Input이라는 배열에 수열에 포함되는 수들을 입력 받았고,
입력받은 수중에 몇쌍이 서로 더하면 x가 나오는지를 판단해야 했다.
그래서 x의 범위만큼 Res 배열을 선언하고, x에서 입력받은 숫자를 뺀 숫자를 인덱스로 사용해서 검사했다.
ex >
x가 100이고 입력받은 첫번째 숫자가 53 이라면 Res[100-53] , 즉 Res[47] 이 1인지 검사했다.
없다면 Res[53]에 1을 넣어주는 방식, 있다면 카운트 1을 추가했다.
배열의 인덱스로 바로바로 접근하기 때문에 시간초과를 피할수 있었다.
코드를 다 짜고 런타임에러(OutOfBounds)가 계속 떠서 뭐가 틀린지 계속 찾았었는데,
x-input[i]가 음수일수도 있다는 사실을 깨닫지 못해 한참을 헤맸다.
'프로그래밍 공부 > 코딩테스트 준비' 카테고리의 다른 글
#3 코테준비 - 스택(Stack) (0) | 2022.09.22 |
---|---|
#2 코테준비 - 연결리스트 (0) | 2022.09.22 |
코테 준비하기 - 기본 사항들 (2) | 2022.09.21 |
LeetCode 문제 풀어보기 - 278번 First Bad Version (0) | 2022.07.22 |
LeetCode 문제 풀어보기 - 35번 Search Insert Position (0) | 2022.07.16 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!