본문 바로가기

알고리즘

[알고리즘] (BFS) 경쟁적 전염 (from. 이코테) 문제 N x N 크기의 시험관이 있습니다. 시험관은 1 x 1 크기의 칸으로 나누어지며. 특정한 위치에는 바이러스가 존재할 수 있습니다. 바이러스의 종류는 1 ~ K번까지 K가지가 있으며 모든 바이러스는 이 중 하나에 속합니다. 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식하는데, 매초 번호가 낮 은 종류의 바이러스부터 먼저 증식합니다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 있다면, 그곳에는 다른 바이러스가 들어갈 수 없습니다. 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때. S초가 지난 후에 (X, y)에 존재하는 바이 러스의 종류를 출력하는 프로그램을 작성하세요. 만약 S초가 지난 후에 해당 위치에 바이러스가 존 재하지 않는다면, 0을 출력합니다.. 더보기
[알고리즘] (DFS, 순열) 연산자 끼워넣기 (from. 이코테) 문제 N개의 수로 이루어진 수열 A,,42, ..., 1이 주어집니다. 또, 수와 수 사이에 끼워 넣을 수 있는 N-1개의 연산자가 주어집니다. 연산자는 덧셈 (+), 뺄셈(-), 곱셈(x), 나눗셈(: )으로만 이루어 져 있습니다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서. 수식을 하나 만들 수 있는데 이때 주어진 수의 순서 를 바꾸면 안됩니다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈 (+) 2개, 뺄셈 (-) 1개, 곱셈(x) 1개, 나눗셈(:) 1개인 경우에는 총 60가지의 식을 만들 수 있습니다. 예를 들 어. 다음과 같은 식을 만들 수 있습니다. 식의 계산은 연산자 우선순위를 무시하고 앞에서부터 진행해야 합니다. 또. 나눗셈은 정수.. 더보기
[알고리즘] (bfs 유형) 최단거리의 도시 찾기 문제 어떤 나라에는 1 ~ N번까지의 도시와 M개의 단방향 도로가 존재합니다. 모든 도로의 거리는 1입 니다. 이때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K 인 모든 도시의 번호를 출력하는 프로그램을 작성하세요. 또한 출발 도시 ※에서 출발 도시 X로 가 는 최단 거리는 항상 0이라고 가정합니다. 예를 들어 N = 4, K = 2, X = 1일 때 다음과 같이 그래프가 구성되어 있다고 합시다. 이때 1번 도시에서 출발하여 도달할 수 있는 도시 중에 서, 최단 거리가 2인 도시는 4번 도시뿐입니다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않습니다. 입력 • 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K. 출발 도시의 번호.. 더보기
[알고리즘] bfs (c++) queue를 이용해야 하기에 dfs보다 조금더 복잡하다.. 이런식으로 벡터와 큐 등 자료구조에 익숙해져야 겠다. 헤더를 인클루드 하는데 문제가 있는데, 아마 m1맥북을 사용해서 그런것 같다... #include #include #include std::vector graph[9]; boolvisited[9]; voidbfs(int start) { queue q; q.push(start); visited[start]= true; while(!q.empty()) { intx = q.front(); q.pop(); std::cout 더보기
[알고리즘] dfs알고리즘 (c++) 최근 c++을 공부하며, 그동안 공부해왔던 알고리즘들을 c++로 다시 작성해보고 있다. 벡터의 사용에 친숙해져야 하며, 코딩테스트의 경우 전역변수 사용이 자유롭기에 그 이점을 적극적으로 활용해야겠다. #include #include boolvisited[9]; std::vector graph[9]; voiddfs(int x) { visited[x] = true; std::cout 더보기
[알고리즘] (구현 유형) game (from. 이코테) 문제 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 횐전한 다음 왼쪽.. 더보기
[알고리즘] (구현 유형) 상하좌우 (from. 이코테) 문제 여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나 누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행 가 는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다. 우리 앞에는 여행 카 A가 이동할 계획이 적힌 계획서가 놓여 있다 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L. R, U, D 중 하나의 문자가 반복적으로 적혀 있다. 각 문자의 의미는 다음과 같다. • L: 왼쪽으로 한 칸 이동 • R: 오른쪽으로 한 칸 이동 • U: 위로 한 칸 이동 • D: 아래로 한 칸 이동 이때 여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.. 더보기
[알고리즘] (구현 유형) KnightOfKingdom.cpp (from 이코테) 문제 행복왕국의 왕실정원은 체스판과 같은 8 * 8좌표 평면이다. 왕실 정원의 특저안 한 칸에 나이트가 서있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다. 나이트는 말을 타고 있기 때문에 이동을 할때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위취에서 다음과 같은 2가지 경우로 이동할 수 있다. 1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 2. 수직으로 두칸 이동한 뒤에 수평으로 한 칸 이동하기 이처럼 8 * 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이떄 왕실의 정원에서 행 위치를 표현할 떄는 1부터 8로 표현하며, 열 위치를 표현 할 때는 a부터 h까지 로 표현.. 더보기

티스토리툴바