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

문제 바로가기 Type : 브루트포스 + 백트랙킹 접근 빈 칸을 채워 나갈때 존건에 부합하는지 검사 한다 (퇴각 검사) 가로 및 세로 줄의 모든 숫자는 중복없이 고유 해야 한다 위치에 속한 3x3 영역 내의 숫자도 중복없이 고유 해야 한다. 위치 판별 y와 x를 각각 3으로 나눈다 => 0, 1, 2 중 하나의 숫자가 나온다 영역 시작 점 = 3 * 몫 영역 종료 점 = 3 * (몫+1) 완전 탐색 및 종료 조건에 부합하는 모든 수를 채우면 테이블을 출력하고 종료 한다. 플로우 차트 빈칸에 채워질 숫자가 고유한지 검사하는 isUnique 구현 코드 #include #include using namespace std; int table[9][9]; vector emptyPoints; bool isUniqu..

문제 바로가기 Type : 브루트포스 접근 n 이하의 모든 소수를 저장한 배열을 만든다. 소수 배열을 만들때는 에라토스테네스의 체를 활용 한다 에라토스테네스의 체 2부터 n 까지의 소수를 구하는 방법 이다. x의 배수는 x를 약수로 가진다는 원리를 이용 한다. 2부터 n까지 순회 하며 만약 숫자가 소수 라면 (숫자 + 숫자) ~ n 까지 순회 소수[숫자]는 false 숫자 = 숫자 + 숫자 부분 합 문제와 동일하게 투포인터 알고리즘을 활용하여 소수 만으로 n을 만들 수 있는 경우의 수를 구한다 주의할 점 (1)인덱스 초과 에러를 방지 하기 위해 탐색 범위를 n 이 아닌 vector의 size로 지정 해야 한다 (2)n이 1로 주어질때는 만들 수 있는 소수가 없기 때문에 소수 배열에 접근하려고 할때 인덱스..

문제 바로가기 Type : 브루트포스 접근 완전 탐색으로 구현하면 시간초과 발생하는 문제 o(n^2) 분할정복을 하면 중간값을 계산하지 못해 틀리는 문제 특정 구간을 정하여 작업을 수행할 수 있는 투포인터 알고리즘을 활용 해야 하는 문제이다. 투 포인터 알고리즘은 시간복잡도가 o(n)이다 투포인터 알고리즘 이란? 두개의 피봇(start, end)을 적절히 움직여 배열의 특정 구간을 지정하는 것이다 end를 한칸 뒤로 옮긴 후에는 sum에 arr[end]를 더해준다 start를 한칸 뒤로 옮긴 후에는 sum에서 arr[start]를 빼준다 투포인터 알고리즘 진행 방식 start, end를 0으로 초기화 한다. sum 은 배열의 첫번째 원소로 초기화 한다. start가 end 이하이며 end가 n 미만 일동..

Type : 브루트포스, BFS 1. 문제 분석 최소한의 기울임 동작으로 빨간 구슬을 빼내는게 목적이다 실패 조건 (1) 파란구슬만 빠졌을 경우 (2) 파란구슬과 빨간공이 동시에 빠졌을 경우 -> 순서와 상관 없이 파란공이 구멍에 빠졌다면 실패이다 성공 조건 (1) 빨간 구슬이 구멍에 빠졌을 경우 2. 접근 자료구조 (1) 위치(y,x)를 저장할 pair ball (2) 공 두개의 위치를 저장할 vector balls (3) 공의 탐색 위치와 거리를 저장할 map dist -> 많은 풀이에서 4차원 배열을 사용했지만 나는 좀더 직관적인 자료구조로 map을 사용 하였다 -> map에 각 공의 탐색 위치(상태)와 도달하기 위한 거리를 저장 할 수 있다. 최소의 동작을 위한 BFS 탐색 공 두..

Type : 브루트포스 접근 'a'~'z' 로 이루어진 k 개의 알파벳 조합을 생성한다 (1) 조합에 속한 알파벳은 배운것으로 가정한다 (2) 그렇지 않은 알파벳은 배우지 않은 것으로 가정한다. 말할 수 있는 단어 세기 (1) 입력으로 들어온 단어를 순회 한다. (2) 만약 말할 수 있는 단어라면 숫자를 카운트 한다. 말할 수 있는 단어인지 검사 (1) 단어의 스펠링을 순회 한다. (2) 만약 스펠링이 배우지 않은 알파벳이라면 'false'를 반환 한다. (3) 모든 스펠링을 배웠다면 'true'를 반환 한다. 주의사항 1. 문자열 입력에서 'anta'와 'tica' 를 제거한다 2. 'a', 'n..

문제 바로가기 Type : 브루트포스 접근 상태를 2가지로 나눈다. (1) 번호가 선택된 상태 (2) 번호가 선택되지 않은 상태 깊이 우선 탐색을 통해 각 행별로 숫자를 선택한다. (1) 숫자를 선택해나가며 깊이 우선 탐색을 실시한다. (2) 선택을 해재한 뒤로 다시 깊이 우선 탐색을 실시한다. (3) 연속된 재귀함수로 가능한 모든 분할의 경우를 만들어 낸다. T T T T T T T T T F T T T F T T T T F F T T F T T T T F T F T T F F T T T F F F ... 가로, 세로 별로 종이에 적힌수를 합산한다. 주요 포인트 x >= m 일때 x를 0으로 만들고 y를 증가 시킨다 반복문 없이 x+1, y+1을 통해 조합을 만들어 낸다 재귀안의 재귀를 만들어 부가적인..