본문 바로가기

BOJ89

백준 알고리즘 1697 (숨바꼭질) - C++, Python [문제] 백준 알고리즘 1697 (숨바꼭질) > https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net N에서 M까지 이동하는데, 1초에 +1이나 -1이나 *2를 이동할 수 있다. 최소 시간을 .. 2019. 10. 16.
백준 알고리즘 14888 (연산자 끼워넣기) - C++, Python [문제] 백준 알고리즘 14888 (연산자 끼워넣기) > https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net N개의 숫자가 들어있는 수열 사이에 N-1개의 연산자를 끼워넣어 최소/최대값을 찾는 문제. 연산 순서는 앞에서부터 차례대로 계산한다. 그나마 편한 조건. 연산자는 +, -, *, / 순으로 갯수가 주어지고, 브루트포스이면서 백트래킹 개념의 문.. 2019. 10. 16.
백준 알고리즘 11404 (플로이드) - C++, Python [문제] 백준 알고리즘 11404 (플로이드) > https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 www.acmicpc.net 플로이드-와셜 알고리즘을 사용하는 문제이다. ( 시간 복잡도 = O(N^3) ) 1.. 2019. 10. 16.
백준 알고리즘 7569 (토마토(3D)) - C++, Python [문제] 백준 알고리즘 7569 (토마토(3D)) > https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마 www.acmicpc.net 7576번 (토마토)의 3D ver. 문제이다. > https://wlstyql.ti.. 2019. 10. 16.
백준 알고리즘 2580 (스도쿠) - C++, Python [문제] 백준 알고리즘 2580 (스도쿠) > https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 빈 자리(숫자 0)에 스도쿠를 채우는 문제이다. 여러 경우가 존재한다면 하나만 출력한다. D.. 2019. 10. 16.
백준 알고리즘 1865 (웜홀) - C++, Python [문제] 백준 알고리즘 1865 (웜홀) > https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 www.acmicpc.net 11657 (타임머신)과 거의 같은 벨만-포드 알고리즘 문제이다. > https://wlstyql.. 2019. 10. 16.
백준 알고리즘 9663 (N-Queen) - C++, Python [문제] 백준 알고리즘 9663 (N-Queen) > https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N x N 맵에 퀸 N개를 서로 공격할 수 없게 배치하는 문제이다. 백트래킹을 이용한 문제이다. [문제 해결 (정답)] > https://rebas.kr/761 이 분이 설명해놓은 답이 가장 깔끔하다. BOJ 9663 · N-Queen 알고리즘 분류 : 백트래킹 N-퀸은 백트래킹 알고리즘에서 가장 대표적인 문제다. N x N 사이즈의 체스판에 N개의 퀸을 놓는.. 2019. 10. 16.
백준 알고리즘 11657 (타임머신) - C++, Python [문제] 백준 알고리즘 11657 (타임머신) > https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 1753 (최단 경로) 문제와 비슷한데, 가중치에 음수(-)도 존재하는 문제이다. > https://wlstyql.tistory.com/90 백준 알고리즘 1753 (최단경로) - C++, Python [문제] 백준 알고리즘 1753 (최단경로) > https://www.acmicpc.n.. 2019. 10. 16.
백준 알고리즘 17070 (파이프 옮기기 1) - C++ [문제] 백준 알고리즘 17070 (파이프 옮기기 1) > https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net 파이프를 오른쪽 또는 대각선 아래 또는 아래 방향으로 옮길 수 있.. 2019. 10. 16.
728x90

티스토리툴바