기록을

Array

• 논리적 저장 순서와 물리적 저장 순서가 일치한다.

• 따라서 인덱스로 해당 원소에 접근할 수 있으므로, 찾고자 하는 원소의 인덱스를 알고 있으면 O(1)의 시간 복잡도로 해당 원소에 접근할 수 있다. (Random access 가능)

• 삽입/삭제의 경우, O(1)에 접근은 할 수 있지만, 삽입/삭제 이후에 대부분의 상황에서 원소들을 shift 해주어야 하기 때문에, 이 shift 비용이 최악의 경우 O(n)이 된다.

LinkedList

• 논리적 저장 순서와 물리적 저장 순서가 관계가 없다.

• Random access가 불가능하다. 즉 특정 원소에 접근하고자 할 때, 처음부터 하나씩 찾아가야 한다. 따라서 검색 시 최악의 시간 복잡도는 O(n)이다.

• 삽입 혹은 삭제를 하는 경우에는, 일단 검색을 통해서 원하는 위치에 접근을 한 이후에는, 연결만 해주거나 끊어주면 되기 때문에 검색을 제외한 삽입/삭제의 시간 복잡도는 O(1)이다.

• 결국 처음부터 삽입/ 삭제를 해야하는 경우 시간 복잡도는 O(n)이다.

• Tree의 근간이 되는 자료구조이다.

배열의 경우에 데이터 삽입을 하려고 하는데 처음에 잡은 배열 크기의 범위를 벗어난다면, 새로이 할당을 하여 크기를 키워줘야 한다. 연결리스트는 이러한 과정이 필요 없다.

결론적으로 데이터의 삽입과 삭제가 빈번하게 일어난다면 연결리스트를 사용하면 된다.

그렇지 않고 미리 정해둔 데이터에서 검색만 빈번히 일어난다면 배열을 사용하는 것이 좋다.

하지만 대부분의 알고리즘 문제를 풀이할 경우에는, 메모리와 변수의 입력크기 범위가 주어지기 때문에, 그 한계치로 배열 크기를 잡아두고 사용하면 빠르게 사용할 수 있다.

또한 연결리스트의 경우, 원소 추가 과정마다 메모리의 할당이 발생하고, 삭제 시에는 메모리 해제가 발생하는데, 이러한 system call이 사용되는 부분에서 시간이 걸린다.

문제 링크는 다음과 같다.

https://www.acmicpc.net/problem/13300

위와 같은 예시를 보면, 쉽게 이차원 배열을 사용해야겠다는 생각을 떠올릴 수 있다.

특정 학년의 특정 성별을 가지는 학생의 수를 그대로 배열에 저장해준다.

k보다 인원이 작으면 방은 1개만 있으면 되고, 그 이상일 경우 k로 나눈 몫 + 1개만큼 방이 필요하다.

#include<iostream>
using namespace std;

int arr[2][7];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, k;
	cin >> n >> k;

	int s, y;
	while (n--) { //n명의 정보를 2차원 배열에 저장
		cin >> s >> y;
		arr[s][y]++;
	}

	int room = 0;

	for (int i = 0; i < 2; i++) {
		for (int j = 1; j <= 6; j++) {
			if (!arr[i][j]) //특정 학년과 성별의 학생수가 0이면 continue
				continue;
			
			if (arr[i][j] < k) // k보다 작으므로 방은 하나만 있으면 됨
				room++;
			else { //k보다 크거나 같을 때
				if (arr[i][j] % k == 0) {
					//k로 나눠 떨어질 때
					room = room + arr[i][j] / k;
				}
				else {
					room = room + arr[i][j] / k + 1;
				}
			}
		}
	}

	cout << room << '\n';

	return 0;
}

문제링크

https://www.acmicpc.net/problem/1919

순서를 섞었을 때 문자열이 같아질 수 있느냐를 물어보는 문제였다.

단순히 문자열에서, 각 알파벳의 개수를 파악해주고 비교해주면 된다.

#include<iostream>
#include<string>
#include<math.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	string org, cpr;
	int orga[26] = { 0, }, cpra[26] = { 0, };

	cin >> org >> cpr;

	for (int i = 0; i < org.length(); i++) {
		orga[org[i] - 'a']++;
	}
	for (int i = 0; i < cpr.length(); i++) {
		cpra[cpr[i] - 'a']++;
	}

	int cnt = 0;
	
	for (int i = 0; i < 26; i++) {
		cnt = cnt + abs(orga[i] - cpra[i]);
	}
	cout << cnt << '\n';

	return 0;
}
/*
strfry와 같은 원리. 단어에 쓰인 알파벳별 개수를 파악해서 비교.
입력 문자열의 길이가 다른 경우도 생각해줘야함
*/

문제링크

https://www.acmicpc.net/problem/2577

설명은 코드의 주석으로 대체하겠다.

#include<iostream>
#include<string>
using namespace std;
int A, B, C, arr[10];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> A >> B >> C;
	long long res = A * B*C;	
	string str = to_string(res);
	for (int i = 0; i < str.length(); i++) {
		arr[str[i] - '0']++;
	}
	for (int i = 0; i < 10; i++) {
		cout << arr[i] << '\n';
	}
	return 0;
}
/*
각 자리수의 숫자를 확인하기 위해 계산 결과를 long long에서 string 으로 변환
string으로 변환된 값의 각 자리수인 char에서 int로 변환을 -'0'을 활용
*/

https://www.acmicpc.net/problem/17140

열이든 행이든 연산 하나를 제대로 구현하면, 나머지 하나는 똑같다.

보통 개수를 셀 때, cnt[m[i]]++ 이런 방식으로 세는데, 이 경우에는 1회 이상 등장한 숫자의 개수도 함께 필요하고,

이 수들의 빈도와 수 자체를 가지고 정렬을 해야하기 때문에 다른 방식을 사용했다.

먼저 map을 사용해서 숫자별 개수를 기록했다. 이후에 벡터에 pair 형태로 옮기면서 정렬했다.

주의할 것이, 중간에 R연산을 할 때는 열의 길이가 갱신되고, C연산을 할 때는 행의 길이가 갱신되는데, 따라서 연산을 시작할 당시의 값으로 반복문의 범위를 잡아줘야, 중간에 반복문의 범위가 바뀌는 것을 방지할 수 있다.

https://www.acmicpc.net/problem/17406

배열 돌리기 목록을 꼭 "모두 사용해야 한다"고 했다. 또한 배열을 돌리는 순서에 따라서 결과가 달라지기 때문에, 순열을 사용해서 돌릴 순서를 정해준다.

모든 경우를 다 돌려봐야 하고, 주의할 사항은, 한 순열을 돌린 이후에, 반드시 배열을 원래 상태로 초기화 시켜줘야 한다는 것이다.

배열을 돌릴 때에는, 모든 값을 보존하면서 돌리는 것이 불가능 하다. 돌리는 순서, 방향에 따라서 반드시 모서리중 어느 한 값은 손실이 발생할 수 밖에 없는데, 그 값을 정해서 미리 담아두고, 마지막에 채워주면 된다.

본인은 가장 좌측 상단의 값을 기억해두고, 그 위치를 없어지는 값으로 정했다. 마지막에 그 값이 옮겨가야 할 곳에 넣어주면 된다.