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

문제 바로가기 Type : BFS 접근 문제에 주어진 조건을 잘 지키면서 일반적인 BFS와 유사한 탐색을 진행 한다. 조건 1. 시간이 지날때마다 한칸이 사라지므로 시도횟수가 n을 넘어서면 안된다. 조건 2. x>=n 이다. 배열의 시작은 0부터 시작되므로 n과 동일하기만 해도 범위를 벗어난 것이다. 조건 3. 시간이 지나 사라지거나 0이 표시된 위치로는 접근 할 수 없다. 조건 4. 이미 방문한 곳은 다시 방문 할 수 없다. 구조체 선언 위치 (y, x)와 시간(time)을 저장할 수 있는 구조체를 선언한다. 탐색 진행 탐색이 끝나거나 게임에 성공할때까지. 큐로부터 walker 객체를 꺼낸다 문제에 주어진 동작에 따라 3가지의 새로운 walker 객체를 만든다. 만약 새 walker의 x가 n보다 크거..

문제 바로가기 Type : Dynamic Programming 접근 0부터 시작하여 1,2,3을 각각 더해 n까지 도달할 수 있는 경우를 재귀탐색 한다 f(0) -> f(0+1) + f(0+2) + f(0+3) f(1) -> f(1+1) + f(1+2) + f(1+3) f(2) -> f(2+1) + f(2+2) + f(2+3) ... 만약 n이라는 숫자가 정확하게 만들어 졌다면 true 그렇지 않다면 false를 반환 한다. 일반 재귀 함수 int find(int num){ if(num == n){ return true; } if(num > n){ return false; } return find(num+1) + find(num+2) + find(num+3); } 문제에선 최대 값이 11이므로 메모이제이..

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

Type : Dynamic Programming 접근 주요 방식 (1) 메모이제이션을 활용한 탐색 (2) 1원 부터 k원까지 최소한의 동전수를 구해나간다 (3) money를 만들기 위해 한 종류의 동전을 n개 사용했을때 최소값이 되는지 확인한다 (4) dp[money] = min(dp[money], dp[money - (coin * n)] + n) 초기화 (1) 모든 배열의 값을 INF 로 초기화 한다 (2) 동전의 가치 (value)가 주어졌을때, 가치 만큼의 돈은 동전 1개로 만들 수 있다. 10원의 동전이 주어진다면 10원은 동전 1개로 만들 수 있다 탐색 (1) 1원부터 k원까지 진행한다 (2) 각각의 동전을 탐색 한다 (3) 만약 구하고자 하는 돈보다 동전의 가치가 크다면 pass 한다 (4) ..

Type : BFS 접근 위치, 거울의 갯수, 방향을 저장할 수 있는 구조체를 선언 한다. 거울의 최소 설치 갯수를 저장할 수 있는 2차원배열을 선언한다 다중의 구조체를 동시에 탐색시켜 최소의 Install 갯수를 구한다. 탐색 과정 중 방향이 달라진다면 거울을 설치 한다. BFS 탐색 조건 설정 (1) 지정된 범위 (2) 벽이 아닌 지점 (3) 더 많은 수의 거울을 설치 해야 하는지 주의사항 1. 동일한 수의 거울을 설치할 때도 탐색을 실행 해야 한다. 2. 거울의 수를 증가 시킬 때 새로운 변수를 사용해야 한다. 현재 구조체의 거울 설치수를 변경하면 안된다. 코드 구현 #include #include #include #include #define INF 987654321 #define MAX 101 ..

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을 통해 조합을 만들어 낸다 재귀안의 재귀를 만들어 부가적인..

Type : BFS + DFS 접근 BFS를 통해 로봇, 각 쓰레기 간의 거리를 구한다. (1) 로봇 -> 쓰레기 1, 쓰레기 2, 쓰레기 3 (2) 쓰레기 1 -> 로봇, 쓰레기 2, 쓰레기 3 (3) 쓰레기 2 -> 로봇, 쓰레기 1, 쓰레기 3 (4) 쓰레기 3 -> 로봇, 쓰레기 1, 쓰레기 2 각 지점간의 거리를 MST Table로 생성한다. R T1 T2 T3 R 0 T1 0 T2 0 T3 0 Robot에서 출발하여 어떤 순서로 가야 최소한의 거리로 모든 쓰레기를 치울 수 있는지 구한다 DFS 순열 생성을 통해 각기 다른 순서를 만들어 낸다 MST Table의 거리를 순서에 따라 합산한다. 합산한 것들 중 최소한의 값을 구한다. 주요 포인트 무조건 가까운 지점만 찾는다고 최적의 거라기 구해지진..