본문 바로가기

CS

 (51)
문자열 관리 자료구조 - 트라이(Trie) 개념/구현 C++로 PS를 공부할 때나 코딩테스트를 볼 때 문자열 문제가 나오면 일단 짜증이난다. 파이썬은 문자열 다루기가 편하다는데 C++는 아무래도 문자열을 다룰때 힘든 면이 많다. 문자열 문제가 나오면 파이썬을 쓰고 다른 문제에선 C++을 쓰는 사람도 있을 정도다. 아무튼, 트라이는 문자열을 다루는 방식 중에서도 특히 문자검색을 할 때 가장 유용하고 효과적인 자료구조가 바로 트라이 이다. 먼저 트라이는 문자열로 트리를 만든다고 보면 된다. AB, ABC, BCD, ABD 라는 단어가 들어온다고 치자. 그렇다면 root / \ A B / \ B* C / \ \ C * D* D* 이런식으로 트리를 구성한다. 이렇게 하고 단어가 끝나는 글자들에는 표시를 해둔다. 즉 , 단어를 찾을 때 표시가 되어있는 글자라면 끝났..
DFS를 활용한 순열 이전에 dfs를 활용한 조합을 봤습니다. 순열도 비슷한 방식으로 백트래킹을 사용합니다. 조합과 순열의 가장 큰 차이는 순서입니다. 조합은 1 2 3, 1 3 2 가 같지만 순열은 다르다고 봅니다. 때문에 조합은 idx라는 인수를 갱신하면서 1 2 3 에서 2개를 뽑는다고 치면 1 2, 1 3 하고 끝! 이었습니다. 그러나 순열은 순서를 중요시 생각하기 때문에 2 부터 시작하는 순서도 2 1 가 나와줘야합니다. 이를 이해해야합니다. #include #include #define MAX 4 using namespace std; vector num; vector result; bool visited[5] = { false, }; void dfs(int cnt) { if (cnt == MAX) { for (in..
유클리드 호제법(Euclidean algorithm) - 최대공약수, 최소공배수 알고리즘 최대공약수는 암호학에도 자주쓰이고 알고리즘 문제를 풀 때도 자주 등장합니다. 우리가 초등학교 때 배웠던 최대공약수 구하는 법은 ex) 4 8 이라 하면 두 수가 공통으로 나누어질 것 같은 수를 나눕니다. 2로 나누겠죠. 그럼 2 4 가 되고 이를 또 2로 나누면 1 2 가 되며 이때 마지막으로 더 나누어지는 수가 없으면 지금까지 나눈 수들을 곱한 값이 최대공약수 입니다. 이는 사람머리로는 간단하지만 알고리즘적으로 생각하면 복잡합니다. 이를 타개하기 위해 무려 기원전 유클리드라는 천재가 발명한 것이 유클리드 호제법 입니다. 먼저 유클리드 호제법의 원리는 다음과 같습니다. 1980 , 168 의 최대공약수를 구한다면 1980 % 168 = 132 -> 나누어 떨어지지 않습니다. 즉 최대공약수는 168이 아닌..
DFS를 활용한 조합 조합이란 우리가 고등학교 때 배웠던 Combination을 말한다. 조합은 순서를 반영하지 않는다. 즉 1 2 3 과 2 1 3 은 같은 조합이다. 우리가 아이폰, 에어팟 조합과 에어팟, 아이폰 조합을 구분하지 않는 것과 같다. 개발을 하다보면 조합을 활용해야할 경우가 상당히 많다. 그때 dfs를 활용한 조합 코드를 유용하게 사용할 수 있다. 그러나 완전탐색을 해야하는 경우나 N이 크다면 조합은 지양하는 것이 좋은데, 우선 백트레킹 방식을 사용하는 dfs 조합은 재귀 방식을 사용하기 때문에 자연스럽게 오버헤드의 부담이 생길 수 밖에 없다. EX) 1, 2, 3, 4 중 3개를 뽑는다고 가정하자. 그렇다면 1 2 3 1 2 4 1 3 4 2 3 4 앞자리수를 고정하는게 가장 편리하다 . dfs또한 이를 따..
[git 오류]Another git process seems to be running in this repository, 잘 사용하던 깃이 갑자기 푸쉬가 안될 경우이다. Another git process seems to be running in this repository, e.g. an editor opened by 'git commit'. Please make sure all processes are terminated then try again. If it still fails, a git process may have crashed in this repository earlier: remove the file manually to continue. 일반적으로 두개의 깃 명령어가 실행된 경우이다. 나는 그런 적 없는데 왜...? 어쨌든 Git Bash에 rm -f .git/index.lock 명령어를 실행시키면 해결.
C/C++ 포인터와 참조 : 화살표 -> 과 점 . 의 차이 C/C++에서 포인터를 쓰다보면 Ver.a()라고 쓰려 하면 IDE가 Ver -> a()로 바꿔주는 경우가 있다. 신경쓰지 않을 수도 있지만 뭐가 다른걸까? 간단히 말하면 -> 는 간접 . 는 직접이라고 볼 수 있다. 아래 코드를 보자 #include using namespace std; class Rect { int width, height; public: Rect(int x, int y) : width(x), height(y) {} int area() { return width * height; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); Rect obj(3, 4); Rect* foo, * bar, ..
C++ : In-line function 이란 무엇인가 In-line fucntion이란 마치 C/C++의 매크로처럼 함수를 In-line 라인 안에 숨긴다는 뜻이다. 예를 들어 void add(int a, int b){ return a + b; } main(){ cout add -> 연산 -> 출력 순이다. 만약 inline을 쓰면? inline void add(int a, int b){ return a + b; } main(){ cout 연산 -> 출력 순이된다. 이미 컴파일러는 인라인함수 때문에 저 함수 자체를 알고 있는 상태이기 때문이다. 우리가 어떤 수학 공식을 알면 문제에서 바로 적용 가능하지만 그 공식의 이름만 안다면 책에서 찾아보고 써야하는 것과 같다. inline은 함수를 컴파일러에게 외우게 하는 것이다. 때문에 inline은 함수의 실행시간..
OOP 기초 (왜 쓰는가?, 캡슐화 등) 1. 소프트웨어공학의 궁극적 목표는 최소한의 비용으로 소프트웨어의 개발, 유지보수를 하는 것이다. 2. 일반적으로 OOP는 프로그래머의 생산성, SW퀄리티, 생명주기, 가독성, 이해력을 증가시킨다. 3. 커플링은 모듈(컴포넌트)간의 의존성을 나타낸다. 일반적으로 커플링은 최소화 해야한다. 4. 응집도는 모듈 내부의 데이터들이 얼마나 하나의 목표를 위해 긴밀한가를 나타낸다. 응집도는 최대화 해야한다. 5. 추상 클래스는 최소 한개의 추상메소드를 포함해야한다. 6. 캡슐화란? 7. 캡슐화를 할때의 장점은 무엇인가? 8. 그냥 인스턴스를 사용할때와 포인터를 사용할 때의 차이는? 일반 인스턴스는 값의 복사값을 콜리에게 주기 때문에 데이터가 안전하다. 포인터를 사용할 경우는 본래의 값이 변경 될 수 있다.

티스토리툴바