https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net [풀이] 나이트가 이동하는 방향만 잘 고려한다면 결국 최단 거리를 찾는 문제와 동일하기 때문에 전형적인 BFS 문제입니다. 다른 기본적인 BFS 최단거리 문제에서 사용하는 상하좌우로 이동 대신 나이트가 이동 가능한 8방향으로 이동하며 탐색합니다. 목적지까지의 Depth를 찾으면 되는 간단한 문제였습니다. 더보기 #include #include #include using namespace std; i..
분류 전체보기
문제 https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 풀이 가장 처음에 생각난 풀이는 n^3 * logn의 풀이인데 (임의의 세수 합을 구해서 이분탐색으로 찾기) n 이 최대 1000이기 때문에 시간초과가 난다. 정답을 구하기 위해서는 n^2 또는 n^2logn의 풀이를 생각해야 했고 a + b + c = k 라고 할 때 a + b의 값을 갖는 배열을 만들기로 했다. a + b 배열을 만든 뒤 k..
* 개인 블로그에 작성한 내용을 복사해왔습니다. [Algorithm] BOJ 2251 BOJ 2251번 물통BFS를 사용하여 풀이하였습니다. 다른 탐색 문제들에 비해 어떻게 풀이해야 할지 직관적으로 떠오르지 않아, 풀이를 하는 데 조금 시간이 걸렸습니다.처음에는 방문\_여부\[물통 A의 velog.io BOJ 2251번 물통 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net Intro BFS를 사용하여 풀이하였습니다. 다른 탐색 문제들에 비해 어떻게 풀이해야 할지 직관적으로 떠오르지 않아, ..
https://www.acmicpc.net/problem/11655 11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net 문제분석 알파벳을 13개씩 밀어서 출력하는 문제이다. 알파벳이 아닌 문자는 그대로 출력하고 알파벳은 13개씩 출력하는데, 만약 13개를 민 알파벳이 z를 넘어갈 경우, a부터 시작해야 한다. 코드 n = input() for i in n: if 97
문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때, ..
문제 풀이 BFS 문제입니다. 어느 위치에서 움직일 수 있는 거리 k까지 field[][]에 count +1를 저장합니다. 추후에 이 값과 비교하여 더 작으면 skip(boolean visit[][]과 같은 동작) 하고, 아닐경우 값을 저장합니다. field[x2] [y2] 의 값을 출력합니다. 코드 import java.io.*; import java.util.*; class Main { static int dx[] = {0,0,-1,1}; static int dy[] = {-1,1,0,0}; static int k; static int n; static int m; static int chk=1; static char field[][]; static int field1[][]; static boole..
링크 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 풀이 과정 2차원 배열을 BFS로 탐색하는 방식으로 풀었다. 2차원 배열이기 때문에 pair를 사용했고, food 변수에 해당 BFS 탐색에서의 음식물의 크기를 저장했다. 그리고 강의에서 배웠던 방식대로 dx[], dy[]를 이용해서 2차원 배열을 탐색했다. 이 외에는 딱히 기본적인 BFS와 크게 다른 점이 없어서 전체적인 틀 짜는 것 자체는 어렵지 ..
https://www.acmicpc.net/problem/14247 14247번: 나무 자르기 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 www.acmicpc.net 문제 해석 n개의 나무가 존재한다. 하루에 한그루씩 n일동안 나무를 잘라 얻을 수 있는 최대 길이를 구하는 문제이다. 코드 input = __import__('sys').stdin.readline n = int(input()) arr = [] ans = 0 a = list(map(int,input().split())) b = list(map(int,input().split())) for i in ..
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 풀이 최솟값을 출력해야 하므로 BFS방식을 사용하되 이 문제에서는 힙큐(heapq)로 가중치가 작은 위치가 먼저 pop되도록 한다. 가장 위쪽의 표는 문제의 예시들 중 하나고, 아래의 표들은 순차적으로 가중치값을 구하는 과정이다. 첫번째 표는 (0,0)위치에서 시작하기 때문에 왼쪽 상단에 5를 먼저 넣어두고, 해당 칸과 밀접하게 붙어있는 칸들의 값에 5을 각각 더해서 두번째..
https://www.acmicpc.net/problem/16955 16955번: 오목, 이길 수 있을까? 구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 www.acmicpc.net 문제분석 누구나 쉽게 알 수 있는 오목게임이다. 구사과와 큐브러버는 10x10크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는데, 바둑판의 상태가 입력으로 주어지고 구사과가 턴을 한 번 더 가졌을 때, 즉, 한 수를 두었을 때 이길 수 있는지 구하는 프로그램을 작성해아한다. 오목의 승리 룰은 가로,세로 대각선 방향 중 하나에서 자신의 돌이 5개 이상 연속하는 것이다...
https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net n,m=map(int,input().split()) def Dfs(arr): if len(arr)==m: print(' '.join(map(str,arr))) return for i in range(1,n+1): if i not in arr: arr.append(i) Dfs(arr) arr.pop() se=[] Dfs(se) 중복없이 골라야 하는게 핵심이다. 백준을 보니 n과m 이라고 써진 문제..
https://www.acmicpc.net/problem/14623 14623번: 감정이입 첫 번째 줄에 입력으로 주어진 두 이진수 B1, B2의 곱을 이진수로 출력한다. 출력하는 이진수 앞에 불필요한 0이 붙으면 안 됨에 주의해야 한다. 즉 출력하는 이진수의 시작은 항상 1이어야 한다. www.acmicpc.net a=list(input()) b=list(input()) se=[0]*(len(a)+len(b)) for i in range(len(b)): for j in range(len(a)): se[i+j+1]+=int(a[j])*int(b[i]) t=0 for i in range(len(se)-1,-1,-1): se[i]+=t if se[i]>1: a=se[i] se[i]=se[i]%2 t=a//2..
