본문 바로가기

전체 글

 (336)
map의 다양한 사용법 - key, value 순으로 정렬, auto 반복문 기본적인 사용법: 선언 - map test; 삽입 - test.insert(make_pair(key, value)) 제거 - test.erase(key) ex) #include #include #include using namespace std; int main() { map test; test.insert(make_pair(1, 10)); test.insert(make_pair(2, 9)); test.insert(make_pair(3, 8)); test.insert(make_pair(4, 7)); test.insert(make_pair(5, 6)); cout
프로그래머스 - 카카오 프렌즈 컬러링북(C++) 기본적인 그래프 탐색 문제이다. 각 좌표에서 그래프 탐색 후 방문체크를 한다. bfs를 해도되지만 각 타일에서 다음 타일과 비교해야하는 부분도 있으니 dfs로 풀이했다. 그러나 bfs로 풀이해도 문제없다. 유사한 문제 - https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net #include using namespace std; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int M; int N; int ar..
프로그래머스 - [3차]자동완성 (C++) Trie 자료구조를 공부하게 된 이유가 바로 이 문제 때문이었다. https://tigerfrom2.tistory.com/74 문자열 관리 자료구조 - 트라이(Trie) 개념/구현 C++로 PS를 공부할 때나 코딩테스트를 볼 때 문자열 문제가 나오면 일단 짜증이난다. 파이썬은 문자열 다루기가 편하다는데 C++는 아무래도 문자열을 다룰때 힘든 면이 많다. 문자열 문제가 나오 tigerfrom2.tistory.com 대표 실습 문제라고도 할 수 있는데 Trie 자료구조에서 변수하나를 추가해줘야한다. 개념에서 알 수 있듯, 트라이 자료구조는 트리의 형태로 go -> gone 순으로 추가한다고 치면 g, o는 두번 방문될 것이고 n, e는 한번 방문될 것이다. 즉, 노드에 따로 방문 횟수를 저장한다. 그렇다면,..
문자열 관리 자료구조 - 트라이(Trie) 개념/구현 C++로 PS를 공부할 때나 코딩테스트를 볼 때 문자열 문제가 나오면 일단 짜증이난다. 파이썬은 문자열 다루기가 편하다는데 C++는 아무래도 문자열을 다룰때 힘든 면이 많다. 문자열 문제가 나오면 파이썬을 쓰고 다른 문제에선 C++을 쓰는 사람도 있을 정도다. 아무튼, 트라이는 문자열을 다루는 방식 중에서도 특히 문자검색을 할 때 가장 유용하고 효과적인 자료구조가 바로 트라이 이다. 먼저 트라이는 문자열로 트리를 만든다고 보면 된다. AB, ABC, BCD, ABD 라는 단어가 들어온다고 치자. 그렇다면 root / \ A B / \ B* C / \ \ C * D* D* 이런식으로 트리를 구성한다. 이렇게 하고 단어가 끝나는 글자들에는 표시를 해둔다. 즉 , 단어를 찾을 때 표시가 되어있는 글자라면 끝났..
백준 14888번 연산자 끼워넣기(C++) 삼성 역량 기출 문제를 모두 풀어보는 것이 이번학기 목표이다. 먼저 생각난 풀이는 트리를 구성한 후 dfs 하는 것이었다. 예를 들어 + - x 한개씩 들어왔다고 생각하고 트리를 구성해보면 + x - / \ / \ / \ - x - + + x | | | | | | x - + - x + 이렇게 6가지 경우의 수가 나온다. 이렇게 트리를 구성하고 각 루트를 시작으로 dfs 하면 완전탐색을 할 수 있을 것이다. 그러나 트리를 구성하는것도 귀찮은 일이고 순서대로 트리를 계속 넣는 게 어려웠다. 그 다음 생각난 풀이가 순열이다. + - x 를 원소로 모든 수를 사용하는 순열을 만들어 완전탐색했다. 백트래킹을 이용한 순열의 대한 글은 아래를 참조하면 좋다.https://tigerfrom2.tistory.com/72..
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..
프로그래머스 - N개의 최소공배수(C++) https://tigerfrom2.tistory.com/70 유클리드 호제법(Euclidean algorithm) - 최대공약수, 최소공배수 알고리즘 최대공약수는 암호학에도 자주쓰이고 알고리즘 문제를 풀 때도 자주 등장합니다. 우리가 초등학교 때 배웠던 최대공약수 구하는 법은 ex) 4 8 이라 하면 두 수가 공통으로 나누어질 것 같은 수를 tigerfrom2.tistory.com 이 글을 참고! 어차피 몇개가 들어오던 (1,2,3,4) 라고 하면 1, 2의 최소공배수 a, a와 3의 최소공배수 b, b와 4 의 최소 공배수 c 라고 순차적으로 구해나가면 그게 정답이다. 수학적 증명은 하지않았지만 뭐 맞았다. #include #include using namespace std; int gcd(int a,..
유클리드 호제법(Euclidean algorithm) - 최대공약수, 최소공배수 알고리즘 최대공약수는 암호학에도 자주쓰이고 알고리즘 문제를 풀 때도 자주 등장합니다. 우리가 초등학교 때 배웠던 최대공약수 구하는 법은 ex) 4 8 이라 하면 두 수가 공통으로 나누어질 것 같은 수를 나눕니다. 2로 나누겠죠. 그럼 2 4 가 되고 이를 또 2로 나누면 1 2 가 되며 이때 마지막으로 더 나누어지는 수가 없으면 지금까지 나눈 수들을 곱한 값이 최대공약수 입니다. 이는 사람머리로는 간단하지만 알고리즘적으로 생각하면 복잡합니다. 이를 타개하기 위해 무려 기원전 유클리드라는 천재가 발명한 것이 유클리드 호제법 입니다. 먼저 유클리드 호제법의 원리는 다음과 같습니다. 1980 , 168 의 최대공약수를 구한다면 1980 % 168 = 132 -> 나누어 떨어지지 않습니다. 즉 최대공약수는 168이 아닌..

티스토리툴바