본문 바로가기

전체 글199

재귀(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.
투사체 사정거리 계산 원점에서 시작하지 않는 벡터의 크기를 구하는 방법을 알아보자왜냐하면 캐릭터가 이동할 때 마다 투사체의 시작 위치가 변하기 때문에 그에 맞춰서 투사체의 이동거리를 계산해야 된다. V2의 시작 좌표는 (1, 2) 끝 좌표는 (4, 6) 이다. 끝 좌표에서 시작 좌표를 빼고 루트를 씌워서 크기를 구하면 5가 나온다.마찬가지로 V1의 크기도 5가 나오는데, 원점에서 시작하지 않는 V2의 크기를 구하기 위해서 x축 방향으로 -1 감소시키고 y축 방향으로 -2 감소시켜서 원점부터 시작하는 벡터를 만들고 크기를 구한다는 것을 알수 있다. 즉, 원점에서 시작하지 않는 벡터의 크기를 구하기 위해서는 "벡터의 시작 좌표" - "벡터의 끝 좌표" 이후 각 x, y, z .. 값을 제곱시킨 이후 루트를 씌워서 크기를 구하면 .. 2024. 4. 28.
백준 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.
백준 10026 1. 문제이해  적록색약이 아닌 사람 기준) 같은 색상이 상하좌우로 인접해 있으면 같은 구역에 속한 것으로 인식 적록색약이 있는 사람 기준) 빨간색과 초록색의 차이를 느끼지 못함 빨강과 초록이 인접해 있어도 동일한 색깔로 인식 2. 문제분석 2개의 이중for문을 돌면서 RGB 구역과 R+G, B 구역을 찾음    큐를 두개 만들어서 구역을 구분함  시간제한은 1초로 최대 100*100 = 10,000번 연산을 수행  2개의 이중 for문이므로 대략 20,000번 연산을 함 O(n*n) 시간복잡도로 풀어도 됨  3. 코드#include#include using namespace std;// define 뒤에 ; 써서 틀림 // #define X first// #define Y secondchar board.. 2024. 4. 27.

티스토리툴바