본문 바로가기
728x90
반응형

알고리즘&자료구조54

재귀(recursion) *** 재귀란?하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 재귀를 이용해 문제를 풀때는 수학적 귀납법을 이용하면 간결하게 풀 수 있다.제일 앞의 도미노를 쓰러트리면 모든 도미도는 쓰러질 것이다.그런데 왜? 모든 도미노가 쓰러지는가를 설명해보자 첫번째 설명 방법은 제일 앞에 있는 1번 도미노가 쓰러지면 2번도미노, 3번도미노... 순차적으로 쓰러진다는 설명방법이고 두번째 설명 방법은 1번 도미노가 쓰러진다. K번 도미노가 쓰러지면 K+1번 도미노도 쓰러진다 결국에는 모든 도미노가 쓰러진다는 귀납적 방식을 이용한다.  절차지향적 사고방식)// N~1까지 차례대로 출력void func1(int val) { if (val == 0) return; cout  func1(10000...) .. 2024. 5. 2.
백준 5427 1. 문제이해 매초마다 불은 상하좌우 빈공간으로 이동 상근이도 매초마다 상하좌우로 이동 가능 벽쪽으로 이동 X, 불이 있는 칸 또는 이제 불이 붙으려는 칸으로 이동 X 빌딩을 탈출하기 위한 최소 시간을 구하기 2. 문제분석 지도(board), 불이동시간(fireMoveT), 상근이 이동시간(playerMoveT) 총 3개의 배열 필요 불이붙는 이동시간을 계산할때 불이 최초에 있는 지점은 0초이고 0이상인 경우 불이 있는 곳이기 때문에 체크 X 상근이의 이동시간(PT)이 불이 붙는시간(FT)보다 무조건 작아야지 이동가능 - 지도에 불과 상근이의 위치를 나타내면서 불이 있는 모든 위치를 큐에 넣음 - 큐를 통해서 지도 전체에 불이 붙는 시간을 모두 계산함 - 상근이의 시작위치를 큐에 넣음 - 상근이가 이동하.. 2024. 5. 1.
백준 7562 문제분석 체스판 길이(size) 8 -> 8 * 8  나이트의 최초 시작 지점(startPoint) 나이트가 이동하려고 하는 칸(endPoint) --> endPoint까지 최소 몇번만에 이동할수 있는지? 0. 시작지점을 큐에 넣음  1. 나이트가 이동할 수 있는 모든 방향을 미리 지정해둠  어떻게 지정할 것인가?  총 8가지 방향  ex) 0,0 기준으로 생각해보기 (x : 행, y : 열)  1. 왼쪽상단 대각선(열감소, 행감소) -> 상(행감소) x -> -2, y -> -1  대각선(열감소, 행감소) -> 좌(열감소) x -> -1, y -> -2 2. 오른쪽상단 대각선(열증가, 행감소) -> 상(행감소) x -> -2, y -> +1  대각선(열증가, 행감소) -> 우(열증가) x -> -1, .. 2024. 4. 30.
백준 7569 1. 문제이해 M은 가로 칸의 수, N은 세로 칸의 수 N개의 줄이 H번 반복하여 입력이 주어짐 ex)5(M), 3(N), 2(H)H 1번 1 0 0 0 11 0 0 0 11 0 0 0 1 H 2번1 0 0 0 11 0 0 0 11 0 0 0 1 2. 문제 분석3차원 배열을 이용해서 토마토 상자의 크기를 구성board[N][M][H] -> 이렇게 크기가 구성되야 함  board[2][2] 이차원 배열일 때 board[0][0]의 뜻은 0행에서 0열을 의미한다.첫번째 세로칸에서 첫번째 가로칸을 가리킨다.  board[2][2][2] 삼차원 배열일 때 board[0][0][0]의 뜻은 0행 0열에서 0층에 있는 값을 의미한다. 3. 코드#include#include #include using namespac.. 2024. 4. 28.
728x90
반응형

티스토리툴바