관심이 가는 개발 보물창고

풀이 문제의 지문이 엄청 길지만 요약하면 다음과 같다. 두 문자열이 주어지는데, 두 문자열에서 교집합과 합집합을 구한 다음에 교집합 / 합집합의 결과를 65536으로 곱한 값을 리턴하면 된다. 하나씩 확인해보자. 1. 문자열에서 영문자로 된 글자 쌍만 유효하며, 아래와 2글자씩 문자열을 쪼개서 넣어놔야 한다. 어떻게 쪼갤 수 있을까? string의 substr을 이용해서 간단하게 쪼갤 수 있다. 또한 영문자가 아니라면 무시하자. 또 문제에서 보면, "AB" = "Ab" = "ab" 모두 같은 문자로 취급하므로 다 소문자로 만들어서 넣어준다. vector a; vector b; for (int i = 0; i < str1.size() - 1; i++) { string s = str1.substr(i, 2)..

풀이 N X N 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 문제다. 단순하게 생각하면 N^N^2(true, false) 모든 경우의 수를 비교해서 찾을 수 있지만, N의 크기가 커질수록 연산량이 감당할 수 없는 수준으로 된다. 따라서 가지치기(Pruning)를 하면서 문제를 해결해야 한다. 가치지기란? 어떤 강을 건너기 위해 돌다리를 두들겨보듯이 그 돌이 안전한지 안한지, 유망했는지 아닌지를 검사해서 유망하면 건너가고 아니라면 다시 돌아와서 다른 길을 선택하는 방법이다. 기존의 DFS처럼 주먹구구식으로 끝까지 가보는 것은 어떤 문제에서는 좋지만 이 문제에서는 연산량이 감당이 되지 않기 때문에 DFS처럼 탐색은 하지만 유망한 지 안 한 지를 검사해서 탐색의 범위를 좁혀가면서 문제를 해결한다. N-..

풀이 1. 인쇄 대기목록의 가장 앞에 있는 문서 J를 대기 목록에서 꺼낸다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 있다면 J를 대기 목록에서 가장 마지막으로 넣는다. 3. 그렇지 않으면 J문서를 인쇄한다. 앞에서 빼고, 뒤에서 다시 넣고 하는 자료구조는 Deque가 있다. 현재 가장 앞에 있는 문서의 중요도가 뒤에 있는 모든 중요도보다 높거나 같다면 그 문서를 출력하고, 아니라면 현재 가장 앞에 있는 문서를 뽑아서 뒤에 다시 넣는다. 뒤에 있는 모든 중요도 중에서 가장 높은 중요도는 어떻게 뽑을까? 간단하게 for문을 돌려 뽑을 수도 있지만 *max_element를 이용하면 쉽게 뽑아올 수 있다. 다만 시간 복잡도는 for문과 동일하지만, 간단하게 코드를 짤 수 있어서 편하고 용이하..

파라메트릭 서치 생각보다 받아들이는데 어려운 개념이다. 이 알고리즘은 최적화 문제를 결정 문제로 바꾸는 기법이다. 조건을 만족하면서도 최대한 많이 가져갈 수 있는 방법을 찾는 느낌?? 혹은 조건을 만족하면서도 최대한 적게 가져갈 수 있는 방법을 찾는 느낌이라고 생각하면 좋다. 예시를 들어보면 아래의 문제를 인용해서 생각해보자. BOJ2110 공유기 설치 대표적인 파라메트릭 서치 문제다. 공유기 C개를 설치해야 하는데 두 공유기 사이의 거리를 최대한으로 하려면 어느 정도쯤에 설치해야 할까?라는 문제다. (아래의 예시는 위의 문제 스포가 될 수 있어서 임의로 그냥 생각한 풀이입니다.) 예를 들어보자. 공유기 3개를 설치해야 하는데 만약에 내가 두 공유기 사이의 거리를 2로 설치한다고 가정했을 때, 2씩 공유..

cmath cmath에는 c++에서 각종 수학 함수들을 가지고 있다. 신기하게도 min, max는 algorithm에 구현되어있다는 것을 명심하자. 제곱 구하기 #include // C++ (함수 오버로딩 = 함수 중복 정의) double pow(double x, double y); float pow(float x, float y); float pow(float x, int y); long double pow(long double x, long double y); long double pow(long double x, int y); C++에서는 함수의 이름을 pow로 통일해서 사용하면 된다. 제곱근 구하기 #include double sqrt(double x); float sqrt(float x); lo..

유클리드 호제법? 두 수의 최대 공약수를 O(lgN)만에 구하는 방법이다. 생각보다 자주 까먹으니까.. 틈틈이 시간 나면 한 번씩 봐주자. 재귀 함수 구현 int gcd(int a, int b) { if(b == 0) return a; else return gcd(b, a % b); } 반복문 구현 전제 조건 : a > b while(1) { int r = a % b; if(r == 0) return b; a = b; b = r; } 최소 공배수는? int lcm(int a, int b) { return (a / gcd(a, b)) * (b / gcd(a, b)) * gcd(a, b); } 최소 공배수에서 gcd(a, b)를 3번이나 해주는 이유는 특정 구간에서 오버플로우의 방지를 막기 위해서이다.

stoi c++의 매력을 느낄 수 있는 함수입니다. 바로 문자열을 정수로 바꿔주는 엄청난.. #include int a = stoi("1234"); // 1234 int b = stoi("-1234"); // -1234 int c = stoi("+1234"); // 1234 신기한 점은 문자열 앞에 '+' 나 '-' 부호가 있어도 그것을 반영해서 나타내 준다는 점!!

풀이 처음에는 이 문제를 보고 어떤 자료구조를 사용해야 빠르게 해결할 수 있을까?를 많이 고민한 문제. 문제에서 2, 5, 8, 0을 누를 때는 왼쪽 엄지랑 오른쪽 엄지중 더 가까운 곳에 있는 엄지가 먼저 누르기 때문에 좌표를 사용해야겠다는 생각이 떠올랐다. 좌표 (행,열) 기준! 1번 키패드의 좌표는 (0, 0) 2번 키패드의 좌표는 (0, 1) 0번 키패드의 좌표는 (3, 1) ~번 키패드의 좌표를 표시해주는 자료구조 중 map을 사용하면 편할 거 같아서 map을 채택하면 쉽게 구현할 수 있다. 이렇게 각 키패드 번호마다 좌표를 부여해서, 해당 키패드를 누를 때 왼쪽 엄지랑 오른쪽 엄지의 거리를 구해서 더 작은 거리를 가진 엄지가 먼저 누르도록 구현하면 된다. #include #include #inc..

풀이 문제 요약. 1. 단 한 명의 선수를 제외하고 나머지 모든 선수들은 완주를 했다. 2. 선수들의 수는 10만 간단하게 생각하면 참가자와 완주자를 2중 포문으로 모두 대조해서 찾을 수 있지만 10만 X 10만은 시간 초과가 발생할 수 있다. 따라서 더 간단하게 대조하는 방법은 map 자료구조를 사용하는 것이다. map의 특징 중 하나인 검색의 속도가 O(lgN)을 보장하기 때문에 N이 10만이 들어온다 하더라도 무리 없이 해결할 수 있다. 우선 참가자들을 순회하면서 해당 선수 이름의 횟수를 늘려준다. 그리고 완주자들을 순회하면서 해당 선수 이름의 횟수를 빼준다. 만약에 해당 선수의 이름을 조회하였을 때 그 선수의 값이 0이 아닌 다른 숫자라면? 그 선수는 완주하지 못한 이름이다. 따라서 그 이름을 리..

풀이 크레인 인형 뽑기를 할 때, 제일 위에 쌓여있는 인형부터 뽑아지므로 '스택' 자료구조를 이용하면 쉽게 해결할 수 있다. 문제에서 주어진 board를 각각의 stack에 넣는다. 주의할 점은 0일 때는 인형이 존재하지 않는 것이므로 0이 아닌 값만 스택에 push 해야 한다. 예를 들어 문제에 나온 예시를 기준으로 stack에 쌓이는 결과를 보면 3 4 5 2 2 1 4 5 1 3 4 1 2 1 3 주어진 board를 stack에 넣고 나서 moves 배열을 하나씩 돌면서 인형 뽑기를 시작한다. 이때 moves 배열로 뽑힌 것을 담는 바구니 역시 stack으로 선언한다. 이제 문제에서 요구하는 상황을 위와 맞물려서 생각해보자. 1. 만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인..