본문 바로가기

ALGORITHM_PRACTICE

 (44)
백준 11047번: 동전 0 백준 11047번: 동전 0 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 그리디 알고리즘의 기초문제이다. 목표 값이 있고 동전들을 이용해서 그 값을 이루기 위해 최소의 개수를 사용해서 푸는 문제이다. 가장 최적의 방법을 찾아야하는데 동전수를 최소화하는것이 목적이니까 가지고 있는 동전 중에 사용할 수 있는 가장 큰 값의 동전을 먼저 사용하면 작은 동전들의 수를 최소화 할 수 있다. 큰 값의 동전들을 우선순위를 두어 사용하면 필요한 동전 개수의 최..
백준 13335번: 트럭 백준 13335번: 트럭 13335번: 트럭 문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최 www.acmicpc.net 시뮬레이션 문제로 트럭의 순서를 바꾸지 않고 다리길이만큼 무게를 초과하지 않고 트럭을 끝으로 보내는 문제이다. 나는 큐를 사용하여문제를 풀었다. 큐에 지나갈 수 있는 트럭을 넣고 ..
백준 11051번: 이항 계수 2 백준 11051번: 이항 계수 2 수학문제로 문제는 쉬워보이는데 생각보다 정답률이 낮았다. 역시나 예상대로 그냥 아무생각없이 팩토리얼 계산으로 푸는 문제는 아니었다. 0 n >> k; for(int i = 1; i
백준 13913번: 숨바꼭질 4 백준 13913: 숨바꼭질 4 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net 예전에 풀었던 숨바꼭질 시리즈인데 오랜만에 풀어서 그런지 시간초과로 한번에 풀지를 못했다. 결국 예전 코드를 참조해서 다시 기억을 되살려서 풀어냈다. DFS를 사용하면..
백준 11967번: 불켜기 백준 11967: 불켜기 11967번: 불켜기 문제 농부 존은 최근에 N*N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2≤N≤100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다. 베시는 유일하게 불이 켜져있는 방인 (1,1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으 www.acmicpc.net BFS로 푸는 문제인데 푸는 방법이 조금 귀찮았던 문제이다. 방문 체크 여부는 두개의 배열을 사용했다. 방 하나에는 스위치가 여러개 있을 수가 있어서 방 하나가 가지고있는 스위치..
백준 1600: 말이 되고픈 원숭이 백준 1600: 말이 되고픈 원숭이 1600번: 말이 되고픈 원숭이 첫째 줄에 자연수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다. www.acmicpc.net 제한시간 : 2초 메모리 : 256MB 처음엔 DP 문제인줄 알고 DFS를 이용해서 풀려했지만 풀리지 않았고 BFS로도 잘 풀리지 않았다. 결국에는 구글링으로 해결했다. 문제를 처음봤을 때 K의 갯수가 제한이 필요한가 의문이 들었었는데 구글링이 결국 답을 알려주었고, BF..
백준 3197번: 백조의 호수 백준 3197번 백조의 호수 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX www.acmicpc.net 시뮬레이션 느낌이 나는 BFS 문제이다. 문제의 답을 내는대에는 많이 어렵지는 않지만 시간 제버 부분이 많이 촉박하다. 덕분에 시간초과로 꽤 애를 먹었다. BFS를 쓸 때..
백준 15656번: N과 M (7) 백준 15656번: N과 M (7) 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. www.acmicpc.net 재귀를 이용해서 풀 수 있는 간단한 문제이다. 배열을 입력하고 문제에 맞게 배열 조합들을 출력하면 된다. 문제 조건 중 수열이 사전 순으로 증가해야하기 때문에 정렬을 해야했다. 1. 입력한 배열을 오름차순으로 정렬 2. 중복 허용 가능이어서 다른 조건 필요없이 배열 인덱스가 0번째부터 N-1까지 M번 돌 수 있게 작성했다. 3. M까지 재귀로 배열의 숫자 하나하나를 벡터에 넣는다. 4...

티스토리툴바