본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )

 (260)
[백준 / BOJ] 19591 독특한 계산기 문제 출처 : www.acmicpc.net/problem/19591 19591번: 독특한 계산기 숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. www.acmicpc.net 수식이 주어졌을때, 계산을 하는 문제다. 계산을 할때 규칙이 있는데, 가장 앞, 혹은 가장뒤에있는 것만 계산할수있다. 이때, 곱하기 나누기를 더하기 빼기보다 먼저 계산하고, 수식 우선순위가 같다면 계산결과가 큰것부터 계산한다. 풀이 문제에서 하란대로만 구현하면 풀리는문제다. deq자료구조를 이용했다. 숫자을 저장하는 deq, 연산자를 저장하는 deq을 각각 만들고..
[백준 / BOJ] 1005 ACM Craft 문제 출처 : www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 내가 원하는 건물을 건설할때 걸리는 최소 시간을 출력하는 문제다. 풀이 완전탐색으로 풀경우 N 3 이렇게 저장이 될건데, 4번건물을 짓기위해선 4번에 연결된 건물들을 모두 지어야한다(2번과 3번)라는 뜻 2. 끝까지 탐색하며 건물을 지을때마다 check배열을 업데이트 해준다. (바텀업으로 구현함) check배열을 업데이트할때, 전 위치의 건물들중 최댓값을 뽑아서 업데이트 해줘야함 이때 이미 ..
[백준 / BOJ] 20157 화살을 쏘자 문제 출처 : www.acmicpc.net/problem/20157 20157번: 화살을 쏘자! 호준이는 요즘 활 쏘기에 푹 빠져 있다. 열심히 활 쏘기를 연습하던 호준이는 쏠 때 마다 10점이 나오는 경지에 이르렀다. 이렇다 보니 한 방향으로 있는 과녁에 쏘는 것에 실증을 느낀 호준이는 www.acmicpc.net 풍선들의 (X,Y)가 주어졌을때, 호준이가 화살을 쏠때, (화살은 포물선이 아닌 직선으로 날라감) 한번에 터트릴수 있는 풍선의 최대갯수를 구하는 문제다. 풀이 풍선의 갯수가 10만개이다. 일반적인?? 완전탐색으로 모든경우를 볼경우 O(N^2)이 나와서 시간초과가 뜬다. 완전탐색으로 풀되, 저장을 다르게 해야하는데, 나는 딕셔너리에 {기울기, 해당 기울기의 풍선의 갯수} 로 저장해 주는식으로 ..
[백준 / BOJ] 17911 Keyboards in Concert 문제 출처 : www.acmicpc.net/problem/17911 17911번: Keyboards in Concert The first line of input is two space separated integers; n (1 ≤ n ≤ 1 000) the number of instruments, and m (1 ≤ m ≤ 1 000), the number of notes in the tune. This is followed by n lines, each starting with an integer ki (1 ≤ ki ≤ 1 000), the nu www.acmicpc.net 올라브는 전자키보드를 갖고있다. 이 전자키보드로 노래를 연주하려고 하는데, 키보드가 고장나서 모든 음을 연주할수없다. 한번에 ..
[백준 / BOJ] 19581 두 번째 트리의 지름 문제 출처 : www.acmicpc.net/problem/19581 19581번: 두 번째 트리의 지름 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리 www.acmicpc.net 트리가 주어졌을때 두번째로 긴 트리의 지름을 구하는 문제다. 풀이 트리의 지름을 구하는 임의의 지점에서 가장 먼지점 A를 찾고, A에서 가장 먼 지점 B를 찾으면 된다. 이걸 좀더 응용하면 되는데, 1. 임의의 지점 O 에서 가장 먼지점 A를 찾고, A에서 두번째로 먼 지점 B를 찾는다. 2. 임의의 지점 O 에서 두번째로 먼지점 C를 찾고, C에서 가장 먼 지점 D를 찾는다. 두 값..
[백준 / BOJ] 10164 격자상의 경로 문제 출처 : www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net N*M 그리드에서 무조건 (1,1) 에서 시작하여 (Y,X)지점을 지나 (N,M)지점에 최소한의 이동으로 도달하는 경로의 수를 구하는 문제다. 풀이 dp로 풀리는 문제였다. 전 지점에 최소로 도달하는 경로의 수를 알고있다면, 현재위치까지 오는 경로의 수를 알수있다. 예제처럼 3*5 그리드가 있다고 가정해보자 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0..
[백준 / BOJ] 9518 로마 카톨릭 미사 문제 출처 : www.acmicpc.net/problem/9518 9518번: 로마 카톨릭 미사 로마 카톨릭 미사에서 가장 멋진 부분은 사람들이 서로 악수를 하면서 "평화가 함께하기를" 이라고 말하는 평화 의식이다. 성당에는 R개의 벤치가 한 행에 하나씩 있고, 각 벤치에는 총 S명이 앉 www.acmicpc.net 상근이가 교회 미사동안 최대한 많은사람과 악수를 하려고 한다. 악수는 자기 자리에서 8방향으로 할수있으며, (대각선 + 상하좌우) 상근이는 항상 가장 많은사람과 악수를 할수있는 자리에 앉는다고 할때, 미사가 진행되는동안 몇번악수를 할수있는지 구하는 문제다. 풀이 범위가 크지않아서 완전탐색으로 풀리는 문제였다. 주의할점이 "상근이가 악수를 하는 경우" 가 아니라 "모든 사람이 악수를 하는 경우..
[백준 / BOJ] 5427 불 문제 출처 : www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 상근이가 빌딩을 탈출하려고한다. 이때, 벽이있는곳이나 불이 붙은곳으로는 이동할수없다. 불은 1초마다 상하좌우로 번지며 벽으로는 번지지못한다. 상근이는 1초마다 상하좌우로 움직이며, 벽으로 이동하지 못한다. 가장빠르게 빌딩 밖으로 나가는 경우를 찾는 문제다. 풀이 BFS두번으로 풀리는 구현문제였다. 1. 우선, 불의 위치를 전부 저장해놓은다음, 각각의 위치를 기준으로 BFS를 돌린다. 이때 해당(y,x)지점에 ..

티스토리툴바