본문 바로가기

전체 글124

[BOJ 20056 파이썬] 마법사 상어와 파이어볼 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 문제 어른 상어가 마법사가 되었고, 파이어볼을 배웠다. 마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다. 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 .. 2022. 6. 30.
[BOJ 3190 파이썬] 뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은.. 2022. 6. 28.
[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 의 개념과 차이 알고리즘을 풀다보면 그래프를 탐색해야하는 상황이 많이 발생한다. 그래프를 탐색하는 방법에는 크게 깊이 우선 탐색 (DFS)과 너비 우선 탐색 (BFS)가 있다. 두개의 알고리즘을 그림으로 보면 다음과 같다. 1. 깊이 우선 탐색 (DFS) ✅ 깊이 우선 탐색의 개념 한 노드로 부터 시작해서 다음 분기(다른 경로)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 예를 들어서, 미로찾기를 한다고 가정해보자. 최대한 한 방향으로 가다가 해당 방향의 막다른 길에 다다랐을때, 다시 갈림길로 돌아와서 다른 경로를 똑같이 탐색하고, 이를 탈출구를 찾을 때까지 반복하는 것이 바로 DFS 깊이 우선 탐색이다. 그런데, 만약 잘못 선택한 경로가 올바른 경로에 비해 매우 깊은 (시간이 많이 걸리는) 경로라면?.. 2022. 6. 27.
[BOJ 1715 파이썬] 카드 정렬하기 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶.. 2022. 6. 25.

티스토리툴바