Joon's Blog Joon's Blog

문제 문제 풀어보기 풀이 사실 String 으로도 엄청 간단하게 구현이 가능합니다. 그런데 삽입,삭제가 너무 많아서 시간 초과가 나네요. 그래서 삽입,삭제가 유용한 리스트를 사용합니다. 대부분 벡터랑 비슷한데 리스트는 Iterator 를 기반으로 움직입니다. 그래서 삭제하는 과정에서 해당 cursor 위치의 노드를 삭제하면 그다음 Iterator 의 정보를 받아와야 합니다. cursor = list.erase(cursor) 이런 느낌이 되겠죠. erase 는 삭제 후 다음 노드의 Iterator를 반환해줍니다. 코드 #include #include #include #include #include using namespace std; #define safe(x,y) x>=8 || x> s >> n; lis..

문제 문제 풀어보기 풀이 완전 탐색을 하는데 중복되는 계산을 줄여주는 방법을 선택합시다. 재귀 문을 보면 그냥 포문 돌면서 하나씩 다 더해보는 겁니다. 그런데 저기서 st 인자를 없애고 모두 처음부터 본다면 어마어마한 중복이 발생합니다. 예를 들어 1, 2, 3, 4의 인자가 있다면 st 인자없이 모두 처음부터 탐색을 하는 경우 이러한 순서로 탐색할 겁니다. 하지만 현재 선택한 인덱스보다 작은 인덱스를 선택하는 경우는 모두 중복 수열이 됩니다. 따라서 st 인자를 사용해서 이전 인덱스는 넘어가게 해 줍시다. 코드 #include #include #include #include #include #include using namespace std; #define safe(x,y) x>=8 || x

문제 문제 풀어보기 풀이 진짜 우리는 이 난독증을 어떻게 헤쳐나가야 할까. SWEA 문제는 안 되는 테스트 케이스 위주로 설명을 해보겠습니다. 자신이 이것까지 확인했는지 확인해보세요. 1. 블록홀과 웜홀을 없을수도 있다. 2. 오직 빈공간에서만 시작한다. 3. 블록의 수평수직면을 맞으면 반대방향으로 이동한다. 4. 벽을 맞아도 점수를 얻는다 (case 3) 저는 문제에 다 적혀있는걸 항상 놓치게 됩니다. 어렸을 때 책을 많이 읽으라는게 괜히 하는 소리가 아닌가 봅니다. 코드 #include #include #include #include #include #include using namespace std; #define safe(x,y) (x>=n || x ans) ans = score; break; }..

문제 문제 풀어보기 풀이 이 문제는 완전 탐색 문제입니다. 우선 탐색을 시작할 시작점의 좌표를 정하는 FOR문 두 개 두 대각선의 길이를 정하는 FOR문 두 개를 메인에서 정해줍니다. 그리고 그 조건으로 문제를 푸는 거죠. 허접하지만 이해를 돕기 위해 그림을 그려보면 저는 시작점을 왼쪽 끝에 있는 파란 동그라미로 잡았습니다. 시작점을 어느 점으로 정 하냐에 따라 순서가 조금씩 달라질 수 있습니다. 그리고 두대 각선의 길이는 빨간색선으로 표시했습니다. 굉장히 유사한 문제를 가져왔습니다. https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재..

문제 문제 풀어보기 풀이 비트 마스크를 통해 길이 이어져있는지만 확인하면서 BFS를 하면 풀 수 있는 간단한 문제입니다. 그 간단한 문제를 저는 엄청 실수를 많이 했네요. 비트 마스크 할 때 항상 하는 실수인데 이진수랑 십진수를 자꾸 바꿔 쓰는 게 문제네요... 여러분들은 꼭 이진수 1000을 십진수 8이라고 쓰시기 바랍니다. 코드 #include #include #include #include using namespace std; #define safe(x,y) x>=n || x= 1) continue; int reverse; if (k % 2 == 0) reverse = k + 1; else reverse = k - 1; if ((arr[x][y] & (8 >> k)) && (arr[nx][ny] &..

문제 문제 풀어보기 풀이 재귀를 돌면서 모든 경우를 탐색하는 것은 굉장히 기본적인 완전 탐색 방법입니다. 하지만 이상하게 교환횟수가 7개 정도만 넘어가면 계속해서 시간초과가 뜨더군요. 생각해봅시다. 주어지는 수는 최대 6자리의 숫자입니다. 여기서 두개의 인수를 교환해서 원하는 숫자를 얻기 위해서는 최대 몇번의 교환이 필요할까요? 카드게임을 예를 들어 봅시다. 도둑잡기, 원카드, 훌라 어떤 게임이든 상관없이 손에 6장의 카드가 있습니다. 우리는 이 카드를 정리하기 위해 한 카드 씩 원하는 위치에 가져다 놓습니다. 이 과정은 두 개의 위치를 교한 하는 것과 크게 다르지 않습니다. 그리고 우리는 정확히 카드의 개수만큼 교환할 수 있다면 어떤 순서의 배열이든 만들 수 있습니다. 그렇기 때문에 이 문제에서도 재귀..

문제 문제 풀어보기 (로그인 후 접속 가능) 풀이 냅색 문제에서 비트 마스크를 사용하여 선택한 물건들을 출력할 수 있도록 하였습니다. 냅색 알고리즘은 배낭문제에서 나온 기법인데 생각보다 자주 나오는 유형입니다. 최대의 만족도를 구하는 방법은 냅색을 이용해서 구하게 됩니다. 그리고 만족도를 인덱스로 하는 배열에 비트 마스크를 저장합니다. 출력 과정에서 정답이 되는 만족도에 있는 비트 마스크를 통해 어떤 옷을 선택했는지 출력합니다. 코드 #include #include #include #include using namespace std; int max(int a, int b) { if (a > b) return a; else return b; } int T; int ans; int n, m; int v[26..

문제 문제 풀어보기 풀이 퀸을 먼저 배치하고 가능한 경우인지 판단하는 알고리즘을 하면 시간 초과로 문제를 풀 수 없었습니다. 그래서 다른 분의 블로그를 참조해서 백트래킹을 사용했습니다. 간단히 설명하자면 퀸을 하나 넣고 퀸의 이동반경을 모두 덱에 넣습니다. 퀸이 들어갈수 있는 곳에 넣으면서 계속 덱에 넣다 보면 퀸의 수가 N 개 이면서 덱의 사이즈가 N * N 이 되는 경우가 생깁니다. 바로 이경우가 퀸을 N 개 위치시킨 경우가 됩니다. 코드 #include #include #include #define safe(x,y) x>=0&&x=0&&y < n using namespace std; int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,-1,..