그냥 하는 노트와 메모장

* XOR 그룹 [ 분류 - DSU ] CS Academy Round #9의 Array Removal이라는 문제를 먼저 푸는 것을 권장합니다. 1. 수가 작은 것 부터 제거해나가므로, 지우는 순서는 정해져 있다. 2. k번째 수를 제거했을 때의 XOR 그룹의 합 최대값과 k+1번째 수를 제거했을 때의 XOR 그룹의 합 최대값은 서로 종속적이다. 3. 지우는 과정에서 나오는 XOR 그룹의 합 최대가 되는 값을 출력한다. 삭제하는 순서대로 답을 도출해내기란 쉽지 않다. 따라서 문제 접근 방식을 조금 다르게 해야하는데, 삭제하는 과정 자체에 의미가 없다는 것을 깨닫는 것부터 시작한다. 무슨 소리나면, 1.처럼 순서는 정해져 있으며, 2.처럼 서로 종속적이기 때문에 종속의 의미 지니게끔 접근하는 것이다. 주어진..

* CS Academy Round #9 - Array Removal[ 분류 - DSU ] 이 문제의 특성은 다음과 같다. 1. 지워야하는 순서가 정해져 있다. 2. 순서가 정해져 있는 만큼, k 번째 수를 지웠을 때 큰 수 S_k와 k+1번째 수를 지웠을 때 큰 수 S_k+1는 서로 종속적이다. 3. 수를 제거해나가며 큰 수를 출력해야 한다. 먼저 Greedy하게 접근해보자. S_k와 S_k+1를 비교해보자면 S_k >= S_k+1이 성립함을 직관적으로 알 수 있다. 또한 2.번에 의해 서로 종속적이기 때문에, "순서를 거꾸로" 생각하자. 거꾸로 생각하면, 초기에 없는 데이터에서 하나씩 생성됨을 알 수 있다. 따라서 이를 DSU로 합치는 방식을 택하며, 지금 합친 것과 지금까지의 최대값을 비교해나가며 답..

새로 등장한 코딩테스트 대행 스타트업 사이트다. 문제를 보아하니 그렇게 나쁘지 않은 난이도 및 구성이라 시험을 치뤄봤다. ㅎㅎ 7등이 나온걸 보아 아직 난 멀었나보다 싶다. [ Solution ] 1. 문자열 변환 그냥 문제 설명 그대로 해주면 되겠다.. #include using namespace std; class Solution{ public: string decryptSpell(string str){ for(int i=2;i

* BOJ 2549 - 루빅의 사각형 [ 분류 - BFS(Bidirectional search)/ Backtracking ] 푸는 방법이 다소 다양해서 포스팅하고자 한다. 주어진 문제에서 보면 최대 7번까지만 움직여도 충분히 해결가능한 입력만 주어진다고 한다. 그렇다면 주어진 입력과 목표 4x4배열을 E와 S라고 하자. 그러면 E가 최대 3~4번, S가 최대 3~4번을 움직이면 그 안에 겹치는 교차지점이 반드시 생긴다. 특정 지점 4x4 배열 k에 대해 움직일 수 있는 가지수는 (4+4)*3이 된다. 즉 24 가지수가 나올 수 있는데, S또는 E에서 최대 7번을 움직이기 때문에 24^7의 경우의 수가 나오는데 이 값은 너무나 크다. 시간초과가 자명하다. 따라서 S,E가 교차지점까지 3~4번 이동하는 최대..

1. 숫자 게임 [ Greedy/ Sorting ] Greedy하게 접근해보자. A팀의 점수를 알고 있다. 여기서 B팀의 순서를 결정하여 최대 이길 수 있는 회수를 결정한다. 이기기 위해서는 A 팀원의 수보다 큰 수를 B가 내야한다. B의 최대값을 X라고 하자, A의 최대값을 Y라고 하자. 그러면 X가 Y보다 작다면, 답은 명확하게 0이다. 다르게 표현하자면, X가 Y보다 크다면 X와 Y를 짝을 지어주자. 그러면 답은 1이 증가한다. 만약 B안에 X보다 작고 Y보다 큰 값이 있다면 어떻게 될까. 어떻게 되든 X는 "반드시" 소모되며 A의 모든 요소보다 크기 때문에 큰 값끼리 묶어 주는 것이다. 더보기 #include #include #include using namespace std; int soluti..

* 2017 카카오코드 본선이 글은 카카오가 제시한 해설과 다소 다를 수 있습니다.카카오 기술 공식 블로그에서 에디토리얼을 작성하였으니 참고해주세요 URL : http://tech.kakao.com/2017/09/14/code-festival-round-2/ 1. 단체 사진 찍기 [ 분류 - Brute force/ Permutation ] 전체 경우의 수를 생각해보면 8!밖에 되지 않고, 조건의 수가 최대 100개이기 때문에 완전 탐색으로 답을 도출해낼 수 있다. next_permutation이나 기타 완탐 구조를 통해 답을 도출해내자.#include #include #include #include using namespace std; struct _d { int a,b,cnt, code; }; int ..

* Algospot - 정렬 게임(SORTGAME, ) [ 분류 - BFS ] 간단한데, 이상하게 자꾸 시간초과가 뜨는 문제다. * 접근 방법 1. 길이가 x인 수열을 한 번 이상의 연산을 수행했을 때, 정렬 결과로 나올 수 있는 경우의 수는 x!이다. 2. 내부에서 연산을 수행하는 속도는 약 O(x)다. 따라서 1.의 결과로 보면 속도는 최대 8!*8이다. 3. 하지만 이를 들어오는 쿼리마다 수행할 수는 없으므로 "미리" 저장을 해놓고 들어오는 입력에 따라 O(C lg(x!*x)) 시간으로 찾을 수 있도록 한다. 4. 최대가 8이므로 길이 8짜리만 구하고, 나머지 길이에 대해서는 남는 부분을 오름차순으로 채우고 찾으면 된다. - 코드 #include #include #include #include #i..

* Algospot - 어린이날 (CHILDRENDAY, https://algospot.com/judge/problem/read/CHILDRENDAY) [ 분류 - BFS/ Mathematics ] 접근 방식이 다소 까다롭다. N명 중 M이 하나씩 더 받기 위해선 N%ans = M이며 이 나머지에 대해 사이클이 존재함을 알아야 한다. 또한 이를 증명하는 페르마의 소정리에 대해 알고 있어야 한다. * 접근 방법 1. 찾고자 하는 ans에 대해 N%ans = M이기 위해선 기저(시작 지점)은 숫자(한자리 수)부터 시작한다. 여기에 하나씩 이어붙이며 진행하는 BFS를 구성한다. 2. 나머지이기 때문에 후보를 [0, N]으로 줄일 순 없다. 적어도 하나 이상의 장남감을 줘야하기 때문에 [0, 2*N]가 후보가 ..

* BOJ 3987 - VOYAGER (보이저 1호, https://www.acmicpc.net/problem/3987) [ 분류 없음 ] 지정된 좌표에서 시작해서 상하좌우 방향으로 진행할 때, 가장 많은 칸을 밟을 수 있는 것이 답이 된다. 이전 포스팅과 비슷한 문제이긴 하다. 방향이 좌표당 4개가 있기 때문에 해당 방향으로 또 방문한다면 이를 사이클로 보자. 사이클이 존재한다면 무한히 반복할 수 있기 때문에 Voyager를 출력해야 한다. 단, 그 무한히 반복할 수 있을 때의 처음 방향을 출력해야 한다. 가령 오른쪽으로 시작했을 때 반복이 된다면 아래처럼 출력한다. RVoyager - 코드 #include #include int main() { char board[500][501], dirp[]="U..

* BOJ 6084 - Laserphones (레이저 통신) [ 분류 - BFS ] 이 문제는 비슷한 문제가 있긴하다. 어떤걸 먼저 풀어도 상관은 없다. (거울설치 - https://www.acmicpc.net/problem/2151) 문제에서 요구하는 것은 C에서 C로, 레이저를 쏠 때 필요한 거울의 수다. 단 90도 로만 반사된다. 가령 d방향으로 레이저가 진행하고 있다고 가정해보자. 그렇다면 현재 바라보는 방향을 기준으로 직진, 좌우 밖에 갈 수 없다(180를 반사, 즉 오던 방향으로 쏠 순 없음). ↑ → / → ＼ ↓ → → → * 접근 방법 1. 두 개의 C 중 하나를 Source로 두고, 4 방향으로 레이저를 쏘는 것으로 시작한다. (시작할 때는 어느 방향이라도 가능하기 때문. 2. 막상 발..

* BOJ 5213 - TOTEM (과외맨) [ 분류 - BFS,DFS / 기타 최단경로 알고리즘 ] 주어진 문자들을 어떻게 노드로 정의할 것이며, 어떻게 자료구조를 설정할 것인지 물어보는 문제. 단순 최단경로 알고리즘을 사용한다면 별다를 문제는 없다. 문제에서는 타일은 두 개의 숫자로 이루어진다. 두 개의 숫자는 각자 '칸'을 의미하며 최대가 6이다. 인접한 타일과 같은 숫자로 접점이 있다면 두 타일은 이어져 있다고 볼 수 있다. * 접근 방식 1. 각 타일은 2개의 칸이고, 각 칸의 최대가 6이므로 두자리 수 하나로 퉁칠 수 있다. 2. 입력으로 주어지는 순서는 맨위 좌측 타일부터 맨 아래 우측 타일까지를 주어주므로 indexing 절차가 필요함을 알 수 있다. 즉, 단순 2차원 배열로 두고 접근할 ..

* BOJ 1765 - The Gangs (닭싸움 팀 정하기, https://www.acmicpc.net/problem/1765) [ 분류 - BFS, DFS/ DSU/ Hashing ] 이분 그래프가 여러개 생길 수 있는 구조를 생각하자. 조건에 따르면 특정 Component A에 대해 A의 적은 단 하나 밖에 존재하지 않는다. 따라서 자신의 적을 저장할 자료구조(Hashing)와 친구를 저장할 자료구조(인접 행렬 및 리스트/ DSU)를 정해야 한다. * 풀이 친구를 저장할 때는 인접 행렬 및 리스트로 저장하는 것은 꽤 간단하다. 하지만 적을 저장할 때는 어떻게 해야 할까? 이분 그래프이기 때문에 적을 단 하나만 저장한다. 이를 루트로 두고, 들어오는 데이터에 따라 자신의 적을 읽어들여, 적과 적을 이..

* BOJ 3964 - 팩토리얼과 거듭제곱 (https://www.acmicpc.net/problem/3964) [분류 - Mathematics/ GCD/ Sieve of eratosthenes ] 으음.. 생각해야할 부분이 굉장히 많은 문제다. 사실 어떻게 풀어야하겠다는 접근 자체는 다소 간단하다. 하지만 이 과정에서 발생할 수 있는 Overflow를 까다롭게 다뤄야 풀 수 있다. * 접근 방식 1. n!이 k^i에 나누어 떨어지기 위해서는 k^i = GCD(n!, k^i)이어야 한다. 2. 최대 공약수의 후보를 산출하기 위해서 k^i는 lg(k)의 시간이 걸리는 반면 n!은 lg(n!)이 걸린다. k^i가 lg(k)인 이유는 i제곱꼴은 k의 약수의 승수에 i를 곱하면 되기 때문. 따라서 후보를 추출하..

* BOJ 1103 - 게임 (https://www.acmicpc.net/problem/1103) [ 분류 - DFS/ Dynamic programming ] 여러분이 이 문제가 그래프임을 알았다고 가정하고 정리해보자. 1. 동전은 (0,0) 에서 시작한다. 2. 동전이 있는 지점에 있는 숫자만큼 상하좌우로 이동할 수 있다. 3. 구멍 H에 들어가거나 보드 밖으로 나가는 것도 동전을 움직이는 것으로 간주한다. 따라서 (0,0)부터 시작해서 상하좌우로 움직일 수 있는 곳의 최대치로 이동한다. 이는 memoization으로 구현할 수 있다. 하지만 무한번 움직일 수도 있는데, 바로 사이클이 생기는 경우다. 사이클이 하나라도 생긴다면 그 안에서 계속 움직일 수 있기 때문에 -1을 출력해줘야 한다. 따라서 me..

* BOJ 2981 - 검문 (https://www.acmicpc.net/problem/2981) [ 분류 - GCD ] 수학 개념이 필요한 문제다. 주어지는 N개의 수를 정렬한 수열의 결과를 a1, a2, ..., an 이라 하자. 임의의 정수 M으로 나눴을 때 수열의 나머지를 m라고 할 때, 수식을 아래처럼 나타낼 수 있다. 이에 대해 근접한 원소끼리 차이를 정리해보면, ... 서로 다른 두 원소 차이에 대해 "약수"로 M이 들어가 있는 것을 확인할 수 있다. 따라서 이 차이에 대해 최대공약수를 구하여 그것의 약수를 모두 출력하면 된다. - 코드 #include #include #include using namespace std; int gcd(int p, int q) { if (q == 0) ret..