패턴찾기
Flag 써서 찾거나, 함수를 만들어서 찾는다
#include <iostream>
using namespace std;
char vect[12] = "BTABCCQABC";
char pattern[4] = "ABC";
bool isPattern(int startIdx)
{
for (size_t i = 0; i < 3; i++)
{
if (pattern[i] != vect[startIdx + i])
{
return false;
}
}
return true;
}
int main()
{
for (size_t i = 0; i < 7; i++)
{
if (isPattern(i) == true)
{
cout << "Pattern found at index: " << i << endl;
break;
}
}
return 0;
}
JavaScript
복사
2차원배열에서도 패턴을 찾을수 있다.
또다른 패턴찾는 예시
#include <iostream>
using namespace std;
int vect[3][5] =
{
1,2,3,4,1,
3,1,0,0,1,
2,3,4,1,2,
};
int pattern[3] = {3,4,1};
bool isPattern(int dy, int dx)
{
for (size_t i = 0; i < 3; i++)
{
if (pattern[i] != vect[dy][dx + i])
{
return false;
}
}
return true;
}
int main()
{
bool ret = false;
for (int y = 0; y < 3; y++)
{
for (size_t x = 0; x <3; x++)
{
ret = isPattern(y, x);
if (ret)
break;
}
if (ret == true)
{
// 존재
}
else
{
// 존재하지 않음
}
}
return 0;
}
JavaScript
복사
패턴이 게임에서 활용되는 예시의 대표적으로 스타듀밸리가 있디.
해시 테이블
해시 테이블이란 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조를 말한다. 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다.
Direct Address Table
먼저 가장 간단한 형태의 해시테이블로 이름 뜻대로 키 값을 주소로 사용하는 테이블을 말한다. 이는 키 값이 100이라고 했을 때 배열의 인덱스 100에 원하는 데이터를 저장하는 것이다.
int bucket[256] = {};
char str[7] = "ADBFAD";
for (int i = 0; i < 6; i++)
{
bucket[str[i]]++; //str[i](아스키코드)값 자체를 index로 활용
}
C++
복사
Hash Table - DAT(Direct Addressing Table)
#include <iostream>
int main()
{
// DAT(Direct Addressing Table) - Hash Table
// 값 자체를 index로 활용해서 사용하겠다.
// 넉넉한 크기의 배열을 선언
int bucket[256] = {};
char target = 'A';
// 'A'의 아스키코드는 65
// bucket 배열의 65번째에 1을 대입
bucket[target] = 1;
return 0;
}
C++
복사
Hash Table
해시함수를 사용하여 특정 해시값을 알아내고 그 해시값을 인덱스로 변환하여 키 값과 데이터를 저장하는 자료구조이다. 이는 보통 알고 있는 해시 테이블을 얘기하며 개념자체가 어려운 것은 아니지만 문제가 되는 것은 충돌(Collision)이다. 충돌에 대해서 이해하기 위해선 먼저 적재율(Load Factor)에 대해서 이해해야 한다.
적재율이란 해시 테이블의 크기 대비, 키의 개수를 말한다. 즉, 키의 개수를 K, 해시 테이블의 크기를 N 이라고 했을 때 적재율은 K/N 이다. Direct Address Table은 키 값을 인덱스로 사용하는 구조이기 때문에 적재율이 1 이하이며 적재율이 1 초과인 해시 테이블의 경우는 반드시 충돌이 발생하게 된다.
만약, 충돌이 발생하지 않다고 할 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1) 에 수행되지만 충돌이 발생할 경우 탐색과 삭제 연산이 최악에 O(K) 만큼 걸리게 된다. 이는 같은 인덱스에 모든 키 값과 데이터가 저장된 경우로 충돌이 전부 발생했음을 말한다. 따라서, 충돌을 최대한으로 줄여서 연산속도를 빠르게 하는 것이 해시 테이블의 핵심인데 이에 중요하게 작용하는 것이 바로 해시함수를 구현하는 해시 알고리즘이다. 해시 알고리즘이 견고하지 못하게 되면 해시함수로 도출된 값들이 같은 경우가 빈번하게 발생하게 되므로 잦은 충돌로 이어지게 되는 것이다.
활용의 예
배열에 존재하는 알파벳 갯수 찾기
#include <iostream>
int main()
{
// 넉넉한 크기의 배열을 선언
int bucket[256] = {};
char str[7] = "ADBFAD";
for (int i = 0; i < 6; i++)
{
// 아스키코드 자체를 인덱스로 사용
int idx = str[i];
bucket[idx]++;
}
// for문을 사용해서 하나하나 count하여 찾을 수도 있다.
int count = 0;
for (int i = 'A'; i <= 'Z'; i++)
{
std::cout << (char)i << " : " << bucket[i] << std::endl;
}
// 2가지 방법의 장단점이 존재한다.
// HashTable을 사용하면 너무 많은 메모리 공간을 차지한다. 대신 코드는 쉬워진다.
// for문을 사용하면 코드가 복잡하다. 대신 정해진 공간만 사용한다.
return 0;
}
C++
복사
배열에 존재하는 알파벳의 종류 찾기
#include <iostream>
int main()
{
// 넉넉한 크기의 배열을 선언
int bucket[256] = {};
char str[7] = "ADBFAD";
for (size_t i = 0; i < 6; i++)
{
// 아스키코드 자체를 인덱스로 사용
// 알파벳 갯수를 확인
char idx = str[i];
bucket[idx]++;
}
for (size_t x = 0; x < 256; x++)
{
// 알파벳이 존재한다면
if (bucket[x] != 0) {
// 사용된 알파벳의 종류가 출력된다.
std::cout << (char)x;
}
}
return 0;
}
C++
복사
배열에 존재하는 알파벳의 종류와 각 갯수 출력
#include <iostream>
int main() {
// 넉넉한 크기의 배열을 선언
int bucket[256] = {};
char str[7] = "ADBFAD";
for (size_t i = 0; i < 6; i++)
{
// 아스키코드 자체를 인덱스로 사용
// 알파벳 갯수를 확인
bucket[str[i]]++;
}
for (size_t x = 0; x < 256; x++)
{
// 알파벳이 존재한다면
if (bucket[x] != 0) {
// 사용된 알파벳의 종류가 출력된다.
// 사용된 알파벳의 종류 별 갯수도 함께 출력한다.
std::cout << (char)x << " : " << bucket[x] << "개\n";
}
}
return 0;
}
C++
복사
배열의 글자를 순서대로 정렬하여 출력
버블정렬, 선택정렬보다 훨씬 간단하다.
#include <iostream>
int main()
{
// 넉넉한 크기의 배열을 선언
int bucket[256] = {};
char str[7] = "ADBFAD";
for (size_t i = 0; i < 6; i++)
{
// 아스키코드 자체를 인덱스로 사용
// 알파벳 갯수를 확인
bucket[str[i]]++;
}
for (size_t x = 0; x < 256; x++)
{
// 알파벳이 존재한다면
if (bucket[x] != 0)
{
// 사용된 알파벳을 정렬하여 출력
for (size_t i = 0; i < bucket[x]; i++)
{
std::cout << (char)x;
}
}
}
return 0;
}
C++
복사
패턴 찾기
#include <iostream>
char vect[10] = "BTABCQABC";
char pattern[4] = "ABC";
// 문자열 배열은 끝났을 때 어디서 끝나는지 알려줘야 하기 때문에
// 마지막 문자인 '\0' null 문자의 자리까지 포함해서 문자열 배열의 사이즈를 선언한다.
// char pattern[4] = "ABC\n" 라는 값을 가진 것이다.
int isPattern(int idx) {
for (size_t i = 0; i < 3; i++)
{
if (pattern[i] != vect[idx + i]) {
return 0;
}
}
return 1;
}
int main() {
// 패턴찾기 (함수 이용)
int result = 0;
for (size_t i = 0; i < 7; i++)
{
result = isPattern(i);
if (result == 1) {
break;
}
}
if (result == 0) {
std::cout << "발견";
}
else {
std::cout << "미발견";
}
return 0;
}
C++
복사
안녕하세요,
야무지고 맛있게 코딩하는 얌얌코딩입니다!
단순히 영상을 보는 것만으로는 부족한 분들,
"직접 손으로 풀어보며 성장하고 싶다"는 분들을 위해
얌얌코딩 유튜브 멤버십 전용 혜택을 마련했습니다.
멤버십 전용 혜택
단계별 연습문제 & 복습문제 PDF 제공
→ 강의에서 배운 내용을 직접 연습하며 복습할 수 있어요!
디스코드 전용 채널 입장 가능
→ 질문, 피드백, 코드 리뷰, 실습 자료 공유까지
선공개 자료 및 전용 코드 예제 제공
커리어, 포트폴리오 관련 Q&A/코멘트도 비정기적으로 제공
얌얌코딩 숙제, 전용 자료실은 "학생얌얌이" 등급 이상부터 제공됩니다.일반 멤버십(입문얌얌)은 접근이 제한되며,
연습문제 다운로드 및 디스코드 채널 열람은 "학생얌얌" 등급 이상이어야 가능합니다.
가입 방법
1.
아래 링크 클릭하여 멤버십 가입
2.
디스코드 서버 입장
3.
유튜브 계정과 디스코드 계정 연동
→ 자동으로 멤버 등급 확인 후, 전용 채널 열립니다
→ (문제 시 디스코드 내 안내 채널에서 도움 요청 가능)
