알고리즘 풀이/수학
-
백준 2505번 두 번 뒤집기 :: 마이구미알고리즘 풀이/수학 2018. 2. 5. 18:55
이 글은 백준 알고리즘 문제 2505번 "두 번 뒤집기" 를 풀이한다.정올 출제 문제로써, 문제 이해를 통한 구현으로 해결할 수 있다.문제 링크 - https://www.acmicpc.net/problem/2505 1부터 N까지의 숫자가 각 칸에 차례대로 들어있는 놀이판이 있다. 예를 들어 10 칸을 가진 놀이판의 초기 상태는 다음과 같다. 12345678910구간[i,j]는 놀이판의 왼쪽 i번째 칸부터 j번째칸 사이에 있는 모든 숫자를 말한다. 단 구간[i,j]에서 항상 라고 가정한다. 우리는 이 놀이판의 한 구간을 잡아서 그 구간을 완전히 뒤집을 수 있다. 만일 초기상태에서 구간[3,8]을 뒤집으면 놀이판은 다음과 같이 변한다.12876543910이어 이 상태에서 구간[1,5]를 다시 뒤집으면 놀이판..
-
백준 2564번 경비원 :: 마이구미알고리즘 풀이/수학 2018. 1. 29. 14:09
이 글은 백준 알고리즘 문제 2564번 "경비원" 을 풀이한다.정올 출제 문제로써, 풀이 방법은 문제 이해를 통한 단순한 구현이다.문제 링크 - https://www.acmicpc.net/problem/2564 동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 경비차를 몰고 그 곳으로 달려가야 한다. 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다.예를 들어 가로의 길이가 10, 세로의 길이가 5인 블록의 경계에 무인 경비를 의뢰한 3개의 상점이 있다고 하자. 과 같이 이들은 1, 2, 3으로 표시되어 있고, 동근이는 X로 표시한 위치에 있다.1번 상점에서 호출이 들어 왔을 때..
-
백준 11332번 시간초과 :: 마이구미알고리즘 풀이/수학 2018. 1. 28. 16:40
이 글은 백준 알고리즘 문제 11332번 "시간 초과" 를 풀이한다.정답 비율이 낮지만, 어려운 알고리즘을 요구하진 않는다.제목처럼 항상 시간초과를 고려했다면, 쉽게 문제를 해결할 수 있다.문제 링크 - https://www.acmicpc.net/problem/11332 유빈이는 코딩을 하다가 시간 초과가 났다. 그래서 시간 복잡도를 계산하기로 했다.채점 시스템은 1초에 100000000(108)가지 동작을 할 수 있다.여러분들은 유빈이를 도와 시간초과가 나는지 확인하는 프로그램을 작성하라. 입력의 첫 번째 줄에는 테스트 케이스들의 수 C가 주어진다.그 다음 C개의 줄에는 시간 복잡도를 나타내는 문자열 S, 각 테스트 케이스마다 입력의 최대 범위 N, 테스트 케이스의 수를 나타내는 T랑 제한시간(초 단위..
-
백준 2477번 참외밭 :: 마이구미알고리즘 풀이/수학 2017. 12. 28. 00:44
이 글은 백준 알고리즘 문제 2744번 "참외밭" 풀이한다.정올 초등부, 중등부 문제에 출제된 문제이다.풀이는 수학적 사고를 요구하는 문제가 된다.문제 링크 - https://www.acmicpc.net/problem/2477 1m^2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다. 밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다.예를 들어 참외밭이 위 그림과 같은 모양이라고 하자. 그림에서 오른쪽은 동쪽, 왼쪽은 서쪽, 아래쪽은 남쪽, 위쪽은 북쪽이다. 이 그..
-
백준 10800번 컬러볼 :: 마이구미알고리즘 풀이/수학 2017. 12. 21. 00:05
이 글은 백준 알고리즘 문제 10800번 "컬러볼" 을 풀이한다. 정올 초등부, 고등부에서 출제된 적이 있다. 본인의 푼 방식은 다른 풀이보다 속도면에서는 떨어진다. 문제 링크 - https://www.acmicpc.net/problem/10800 2019.10.10 수정 완료 지훈이가 최근에 즐기는 컴퓨터 게임이 있다. 이 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조종하여 게임에 참여한다. 각 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것이다. 그리고 다른 공을 사로잡은 이후에도 본인의 공의 색과 크기는 변하지 않는다. 다음 예제는 네 개의 공이 있다. 편의상 색은 숫자로 표현한다. 공 번호색크기 ..
-
백준 2980번 도로와 신호등 :: 마이구미알고리즘 풀이/수학 2017. 12. 17. 12:59
이 글은 백준 알고리즘 문제 2890번 "도로와 신호등" 을 풀이한다.시뮬레이션 문제로써, 시나리오를 정확히 이해한 후 그대로 구현하면 된다.문제 링크 - https://www.acmicpc.net/problem/2980 상근이는 트럭을 가지고 긴 일직선 도로를 운전하고 있다. 도로에는 신호등이 설치되어 있다. 상근이는 각 신호등에 대해서 빨간 불이 지속되는 시간과 초록 불이 지속되는 시간을 미리 구해왔다. (빨강색과 초록색 불빛은 무한히 반복된다)상근이의 트럭이 도로에 진입했을 때, 모든 신호등의 색상은 빨간색이고, 사이클이 막 시작한 상태이다. 상근이는 1초에 1미터를 움직인다. 신호등의 색상이 빨간색인 경우에는 그 자리에서 멈추고 초록색으로 바뀔때 까지 기다린다.상근이가 도로의 끝까지 이동하는데 걸..
-
백준 2512번 예산 :: 마이구미알고리즘 풀이/수학 2017. 12. 17. 11:58
이 글은 백준 알고리즘 문제 2512번 "예산" 을 풀이한다.시뮬레이션 문제로써, 시나리오를 정확히 이해한 후, 그대로 구현하면 된다.문제 링크 - https://www.acmicpc.net/problem/2512 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그..
-
백준 5623번 수열의 합 :: 마이구미알고리즘 풀이/수학 2017. 12. 5. 21:03
이 글은 백준 알고리즘 문제 5623번 "수열의 합" 을 풀이한다.방법으로는 수학을 이용한 풀이가 된다.문제 링크 - https://www.acmicpc.net/problem/5623 양의 정수 N개로 이루어진 수열 A가 있다. 상근이는 수열 A의 모든 두 수의 합을 알고 있다. 이 때, 수열 A를 구하는 프로그램을 작성하시오. 다음 N개 줄에는 100,000보다 작거나 같은 양의 정수가 N개씩 주어진다. 이 숫자들은 S를 이루는 숫자이며, S(i,j) = A[i] + A[j] (i≠j), S(i,j) = 0 (i=j) 이다. S(i,j)는 i번째 줄, j번째 숫자를 의미하며, A[i]는 A의 i번째 수이다. S(i,j) = A[i] + B[j] 이 부분만 이해하면 쉽게 문제를 해결 할 수 있다. 4 0..