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

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의 거리를 순서에 따라 합산한다. 합산한 것들 중 최소한의 값을 구한다. 주요 포인트 무조건 가까운 지점만 찾는다고 최적의 거라기 구해지진..

Type : 다이나믹 프로그래밍 나의 접근 탐색 방법을 생각 해보았다 50 10 100 20 40 30 50 70 10 60 (1) n+1 대각선 - 상, 하, 좌, 우 스티커가 동시에 뜯기므로 제거할 수 있는 대상은 n+1칸의 대각선에 위치한 스티커이다 (2) n + 2 상 - 스티커가 뜯긴 뒤 n+2 칸의 위쪽에 위치한 스티커는 온전히 제거 할 수 있다. (3) n + 2 하 - 스티커가 뜯긴 뒤 n+2 칸의 아래에 위치한 스티커는 온전히 제거 할 수 있다 문제점 (1) n+2칸 부터는 상, 하 모든 스티커를 온전히 제거할 수 있는데 모든 경우의 수를 탐색 해야 하는가? (2) 탐색과정에서 스티커를 뜯고 난 뒤 온전히 제거 하지 못하는 위치는 어떻게 할 것인가? (3) 팀색 과정에서 최대 값만 찾아 ..