넘어지고 일어나기 넘어지고 일어나기

문제 바로가기 Type : 투포인터, 브루트포스 접근 (1) 하나의 배열 마다 가능한 모든 부분 배열을 생성 한다. (2) 두개의 부분배열에서 합이 t 가 되는 경우의 수를 찾는다. 플로우 차트 (1) 가능한 모든 부분 배열을 생성하기 위한 알고리즘 (2) t 가 되는 경우의 수를 세기 위한 알고리즘 구현 코드 #include #include #include using namespace std; int t; vector subsA, subsB; void solve(){ long long cnt = 0; sort(subsA.begin(), subsA.end()); sort(subsB.begin(), subsB.end()); for(int i = 0 ; i < subsA.size() ; i++){ int d..

문제 바로가기 Type : 브루트 포스, 투 포인터 접근 (1) 연속된 수의 합을 찾기 위한 O(n) 알고리즘으로 투 포인터 알고리즘 이 있다 (2) 투 포인터 알고리즘 이란 피봇 2개를 적절히 움직여 답이 되는 구간 혹은 경우의 수를 찾는 알고리즘을 말한다. 플로우차트 주의할 점 (1) i보다 j가 더 커지는 경우가 존재 한다. ex) n = 8, arr = 1, 2, 9, 2i가 9 위에 존재 할 때 항상 sum이 n 보다 크므로 j를 계속 증가 시킨다 이를 대비하여 j가 i를 넘어 갈때는 sum 과 i 를 다시 초기화 시켜 준다. 구현 코드 #include #include using namespace std; vector arr; int n, m; int solve(){ int cnt = 0; in..

문제 바로가기 Type : BFS, 브루트 포스 접근 (1) 맨 초기 상태에서 상, 하, 좌, 우 로 테이블을 기울여나간다 (BFS 탐색 사용) (2) 기울인 상태마다 가장 큰 블록의 수를 찾는다 (3) 맨 초기부터 5회 이상 기울였다면 BFS 탐색을 중지 한다. 자료 구조 (1) typedef vector table : 블록의 상태를 저장할 2 차원 정수 배열 자료형 (2) typedef vector crashed : 충돌 여부를 저장할 2차원 불리언 배열 자료형 (3) map dist : 맨 초기 상태로 부터의 거리를 저장할 map 자료 구조 주의할 점 (1) 초기 상태는 시도하지 않은것으로 간주한다. (2) 블록을 합칠때는 2가지의 조건을 확인 한다. 합치고자 하는 대상이 이미 충돌한 블록인가 옮기..

문제 바로가기 Type : 브루트포스 접근 범위 설정 수빈이가 이동하려는 채널의 최대값은 500000 이다. 이동할 수 있는 채널은 무한대이다. MAX ch 보다 작은 곳에서 이동하는 경우, MAX ch 보다 큰곳에서 이동하는 경우를 모두 고려해야 한다. 따라서 탐색범위를 0 ~ 1000000 으로 설정해야 한다. 최소값을 찾는 방법 최소값을 찾기위해선 버튼을 누르는 순서가 중요하다 +,- 버튼을 누른 뒤 숫자버튼을 누르면 +,- 가 상쇄된다 (+ + - - ++) 의 경우엔 중복된 탐색이 발생한다. 반드시 숫자 버튼을 누른 뒤 +, - 를 눌러야 한다 +, - 중 하나의 버튼만을 연속해서 눌러야 한다 버튼 누르는 방법 숫자 버튼을 누르기 위해선 0~100000 만까지의 숫자를 발생 시켜 본다 발생된 숫..

문제 바로가기 Type : 브로트포스 접근 조합 생성 0 ~ n 까지 나올 수 있는 2/n 길이의 조합을 생성한다. a, b, c 와 b a c 혹은 동일한 선수가 들어간 모든 팀의 능력치는 동일하다 매번 다른 수의 조합을 생성하여 비교 해야 한다 능력치 비교 조합으로 선택된 선수는 a팀, 그렇지 않은 선수는 b팀으로 나눈다. 모든 선수 쌍의 능력치를 팀별로 구한 후 두 팀의 차이를 구한다. 플로우 차트 구현 코드 #include #include using namespace std; vector board; vector selected; int n, ret; int between(){ vector a, b; for(int i = 0 ; i < n ; i++){ if(selected[i]) a.push_b..

문제 바로가기 Type : 브루트 포스 접근 나열해보기 (ex : m = 5, n = 7) 1: 7 : 2: 8 : 3: 9 : 4: 10: 5: 11: 6: 12: 불필요한 연산 제거 문제의 목표는 x와 y가 모두 일치하는 해를 찾는 것이다 M * N 의 최대값은 40000 ^ 2 = 16억 이므로 1씩 증가시키면 시간 초과 발생 x 가 일치하지 않은 해를 건너띄어 연산수 감소 시켜야 함 규칙 찾기 및 해 건너 띄기 x는 m 주기로 나타난다 y는 n 주기로 나타난다 year를 m, n으로 나눈 값이 x와 y 가 ..

문제 바로가기 Type : 브루트 포스 + 백트랙킹 접근 행렬 생성 규현이는 비행기에서 구간합을 2차원 행렬로 표현하였다 각 행과 열에는 구간합의 기호를 표시 하였다 (+, 0, -) ex) -2, 5, -3, 1 i\j 1 2 3 4 1 - + 0 + 2 + + + 3 - - 4 + 퇴각 검사 순열의 n 번째 숫자를 지정할 때, n 번째 숫자가 모든 구간합의 기호를 만족하는지 검사 한다 즉 위의 도표에서 j 번째 숫자가 들어 왔을 때 모든 i ~ j 구간합 기호가 일치 하는지 검사 한다. ex) j = 4 : check(4, 4), check(3, 4), check(2, 4), check(1, 4) 브루트 포스 퇴각 검사를 모두 통과하여 n 번째의 순열을 만들 수 있을때 모든 순열의 숫자를 출력한 후 ..

문제 바로가기 Type : 백 트랙킹 Queen 이란? 상,하, 좌, 우 대각선으로 모두 움직일 수 있는 체스의 말을 뜻한다. 나의 접근 공격 범위를 1부터 n까지 증가 시키며 첫 Queen의 위치를 (y, x)로 둔다. 공격 범위 1 첫 Queen의 위치 : (0, 0) 첫 Queen의 위치 : (0, 1) 첫 Queen의 위치 : (0, 2) ... 공격 범위 2 첫 Queen의 위치 : (0, 0) 첫 Queen의 위치 : (0, 1) 첫 Queen의 위치 : (0, 2) ... ... 주어진 위치와 공격범위를 대상으로 n개의 queen을 놓을 수 있는지 검사한다. 주어진 위치에는 반드시 Queen을 놓는다. 공격 거리를 점차 증가 시킨다. y, x가 어느것과도 겹치지 않으면 Queen을 놓는다. ..