본문 바로가기

Algorithm/Baekjoon117

1016. 제곱 ㄴㄴ 수 (Python) 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 풀이 에라토스테네스의 체를 활용하여 문제를 해결할 수 있다. 일단 입력으로 주어진 두 수 사이에 있는 수의 개수만큼 크기를 가진 배열을 만든다. 예를 들어 51과 100이 입력으로 주어졌다면 총 50개의 숫자가 있기 때문에 50의 크기를 가지는 배열을 만들어준다. 이때 51 ~ 100에 해당하는 임의의 숫자 n은 해당 배열의 n - 51번째 인덱스에 해당한다. 즉, 임의의 숫자 n에서 입력으로 주어진 min값을 빼주면 해당 배열에 접근할 수 있다.. 2022. 4. 19.
1826. 연료 채우기 (Python) 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 풀이 현재 연료의 양으로 갈 수 있는 거리를 간 후 방문할 수 있었던 주유소 중 가장 연료를 많이 채울 수 있는 주유소에 들렀다고 가정하고 해당 연료를 트럭에 추가해준다. 추가해준 연료의 양만큼 이동하고 방문할 수 있게 된 주유소를 추가로 탐색한다. 그 후 가장 연료를 많이 채울 수 있는 주유소에 들렀다고 가정하고 해당 연료를 트럭에 추가하는 과정을 반복하면 된다. 문제에 나와있는 예제는 다음과 같다. 처음 트럭이 갖고 있는.. 2022. 4. 18.
2573. 빙산 (Python) 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 빙산의 정보를 icebergs 배열에 (행, 열, 높이)의 형태로 저장해둔다. 그리고 다음 과정을 수행한다. 빙산을 녹이면서 높이가 0이 되는 빙산과 그렇지 않은 빙산을 나누어 저장한다. 그 후 맵에 빙산들의 높이를 업데이트한다. 새로운 빙산 정보에 대하여 bfs를 진행한다. 임의의 빙산을 시작점으로 잡고 bfs를 수행한다. bfs를 수행하면서 만난 빙산의 개수를 카운트한다. 카운트 된 빙산의 개수와 icebergs 배열에 있는 빙산의 개수가 같다면 .. 2022. 4. 17.
2668. 숫자고르기 (Python) 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 dfs를 통해서 사이클이 존재하는지를 체크해주어 해결할 수 있는 문제다. 먼저 입력을 받으면서 뽑으면 안되는 정수를 걸러준다. 위의 예를 보면 아래 숫자 목록에서 2와 7은 존재하지 않는다. 그렇기 때문에 위의 숫자 목록에서 2와 7은 굳이 dfs를 하지 않아도 일치하는 집합을 만들 수 없음을 알 수 있다. 그 후 차례대로 숫자 1부터 dfs 탐색을 진행한다. 1부터 숫자를 뽑아가며 배열에 저장하고 사이클이 이루어지는지를 확인한다. 예를 들어 .. 2022. 4. 15.
14466. 소가 길을 건너간 이유 6 (Python) 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 풀이 입력 받은 길은 문자열 형태로 만들어서 딕셔너리를 통해 기록했다. 만약 입력으로 2 2 2 3이 주어졌다면 "2 2 2 3"과 "2 3 2 2"의 형태로 딕셔너리의 키 값을 만들어서 길이 있음을 표시했다. 모든 소에 대하여 bfs 탐색을 진행한다. 이때, (x, y)에서 (nx, ny)로 이동할 때 길이 존재한다면 그쪽으로는 이동하지 않도록 한다. 즉, 길이 없는 곳으로만 이동하여 탐색하고 이때 만났던 소들을 체크한.. 2022. 4. 14.
3190. 뱀 (Python) 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 뱀의 위치 정보만 잘 기록하면 크게 어려움 없이 해결할 수 있다. 보드에서 뱀의 몸이 있는 위치를 deque을 통해 관리한다. 해당 deque에 있는 위치 정보는 (꼬리의 위치, 몸, 몸, 몸, ......, 머리의 위치)로 되어있다. 뱀이 이동할 때마다 deque의 rear에 머리의 위치를 추가한다. 이렇게 하면 기존 머리의 위치는 몸이 되고 새롭게 rear에 추가된 위치 정보가 머리의 위치가 된다. 뱀이 이동했을 때 사과를 먹지 못했다면 deque의 front.. 2022. 4. 13.

티스토리툴바