목록알고리즘 (89)
개발자 김수진
[문제] www.acmicpc.net/problem/3020 [풀이] 처음에는 반복문을 사용해서 풀려고 했지만 N,H 범위를 생각해서 따지면 반복문 10억번에 1초라고 생각하면 20,000 * 50,000 이므로 1초를 훨씬 넘길 것이다. 따라서 이분 탐색 방법으로 풀어야겠다고 생각했다. lower_bound는 x 이상인 값이 처음 나오는 index를 return하고 upper_bound는 x 이하인 값이 처음 나오는 index를 return 하므로 전체 갯수에서 return 된 값을 빼면 파괴하는 장애물의 수를 구할 수 있다. [코드] 시간 : 60ms ( 이분 탐색 직접 구현해서 다시 풀어봐야겠다.) #include #include #include #define MAX 100000 using name..
[문제] www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net [풀이] 표의 크기 N과 합을 구해야 하는 횟수 M이 입력으로 주어진다. 그 다음으로 표의 값이 주어지고 구간의 시작 좌표, 마지막 좌표가 주어진다. 이 구간의 합을 구해서 출력하면 된다. 처음에는 이중 for문을 사용해서 시작점인 (x1,y1)부터 구간의 마지막 부분인 (x2,y2) 까지의 합을 구했다. 당연히 시간초과가 나왔고 다른 방법을 찾아봤다. 찾아보..
[문제] www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net [코드] N 명의 학생들을 M번 비교하고 그 결과가 입력으로 주어진다. 이를 통해 학생들을 줄을 세우는 결과를 출력하면 된다. 학생들의 키가 모두 주어진 것이 아니고 일부만 주어졌으므로 '위상 정렬'을 사용해서 풀었다. Degree에 각 노드에 대한 연결 차수를 저장하고 연결 차수가 0인 노드만 queue에 push 하여 순서대로 출력했다. [풀이] 시간 : 44ms..
[문제] programmers.co.kr/learn/courses/30/lessons/49994# 코딩테스트 연습 - 방문 길이 programmers.co.kr [풀이] 입력으로 움직이는 방향이 주어지고 이에 알맞게 움직이면 된다. 걸어간 길의 길이를 출력하면 된다. 단, 이미 지나왔던 경로는 포함하지 않는다. 또한 범위를 벗어나는 경우 움직이지 않는다. 따라서 좌표와 방향을 가지고 visited 배열을 사용해 이미 방문한 길은 포함하지 않도록 하였다. 문제에서 범위가 -5부터 5까지인데 배열은 index가 0부터 가능하므로 (0,0) ~ (10, 10)으로 변경했다. [코드] #include #define MAX 11 using namespace std; int solution(string dirs) ..
[문제] www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net [풀이] DP를 사용해서 2부터 N까지의 1을 만들 때 필요한 연산의 최소 횟수를 구했다. bottom-up 방식을 사용해 2부터 N까지의 최솟 값을 구했다. 연산은 아래와 같이 3가지 연산이 있다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 따라서 1을 빼는 연산은 모든 숫자에 대해 가능하므로 구하고 X가 2로 나눠지는 경우, 3으로 나눠지는 경우에는 이에 대한 경우도 구해서 최솟 값을 구했다. [코드] 시간 : 4ms #include #define MAX..
[문제] www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net [풀이] N,M이 주어지고 길이가 N인 배열에서 구간합이 M인 경우의 수를 찾아서 출력하는 문제 구간합 문제길래 이중 for문을 사용해서 풀려고 했다. 하지만 시간 제한이 0.5초인데 M의 범위가 1부터 3억이라서 이중 for문을 사용하면 시간초과가 발생한다. 따라서 구간합 구하는 알고리즘인 투 포인터 알고리즘을 사용해서 풀었다. start , end 를 배열의 첫번째 ind..
[문제] www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net [풀이] 시뮬레이션 문제로 문제 조건 잘 지켜가면서 풀었다. 하나의 turn 마다 1번 말부터 순서대로 움직인다. 한 칸에 여러 말이 쌓여 있을 수 있고 이동하려는 말 위에 다른 말이 존재한다면 같이 움직인다. 한 칸에 말이 4마리 이상 쌓일 경우 게임이 종료된다. 이동하려는 칸이 흰색인 경우 이동하려는 말의 위에 있는 말부터 쌓이기 시작한다. 이동하려는 칸이 빨간색일 경우 이동하려는 말부터 쌓이..
[문제] www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net [풀이] 시뮬레이션 문제로 조건별로 함수 구현해서 풀었다. 먼저 원판의 크기와 상태가 입력으로 주어지고 x,d,k가 입력으로 주어진다. x의 배수인 원판을 d ( 0이면 시계, 1이면 반시계) 방향으로 k만큼 회전한다. 1. 회전 2. 인접하면서 같은 수 0으로 바꿔주기 3. 인접하면서 같은 수가 하나도 없다면 원판 전체 평균 구해서 평균 보다 작은 값은 +1, 큰 값은 -1 따라서 r..