Algorithms

큐빙링크: https://www.acmicpc.net/problem/5373문제문제 접근문제 자체의 이해가 그다지 어렵지는 않았다.큐브의 각 면이 w(white), y(yellow), r(red), o(orange), g(green), b(blue)로 주어져있다.각 테스트 케이스 별로 면을 돌린 뒤에 top의 큐브가 어떤 패턴인지 출력하는 문제이다.큐브의 각 면을 저장할 배열과 적절하게 시계방향 또는 반시계 방향으로 돌리는 함수만 만들면 된다. 너무 간단하다!라고 생각했다.풀이 힌트큐브의 각 면 저장각 면은 2차원 배열 char side[3][4]로 표현할 수 있다. 문자열(char 배열)이기 때문에 null 자리 포함각 면을 회전시키는 함수각 면의 돌리는 방향은 + 또는 -으로 주어진다.시계방향의 경..

히스토그램에서 가장 큰 직사각형링크: https://www.acmicpc.net/problem/6549문제히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.문제 접근예제에서 주어진 요소를 하나씩 보며 높이별로 구해야 하는 최댓값을 살펴보자.높이가 1인 직사각형: 가장 작은 값은 1으로 7개의 요소가 모두 공유하기 때문에 길이가 7까지 증가한다.높이가 2인 직사각형: 2 다음 1이 옴으로써 길이가 1인 직사각형을 구할 수 있다. ..

자두나무링크: https://www.acmicpc.net/problem/2240문제자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 ..

퇴사링크: https://www.acmicpc.net/problem/15486문제상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일 4일5일6일7일T[i]3511242P[i]1020102015402001일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이..

가장 긴 증가하는 부분 수열링크: https://www.acmicpc.net/problem/11053문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.문제 접근처음에는 문제 자체를 이해하지 못했다. 이유는 부분수열의 정의를 모르고 있었기 때문이다.부분 수열의 정의: 주어진 항을 원래 순서대로 나열하여 얻을 수 있는 수열DP로 풀 수 있는 알고리즘 중 LIS(Longgist Increasing Subsequence)을 사용하는 문제이다.자, LIS를 먼저 간단히 알아보도록 하자.LIS(..

이친수링크: https://www.acmicpc.net/problem/2193문제 접근DP 문제집을 통해 접근한 것이 아니었다면 백트래킹인가? 했을 것이다.적절한 알고리즘을 선택할 수 있는 안목을 길러야겠다.1로 시작해야 한다는 조건과 연속된 1이 나올 수 없다는 조건을 만족하는 방법의 개수를 세는 문제이다.풀이 힌트table 정의와 점화식, 초기값을 발견하기 위해 값을 직접 대입해보았다.첫째 자리가 1로 시작하면 앞에 두 자리는 1과 0으로 고정이 된다는 사실을 발견했다.아래 그림을 보자.규칙성을 발견했는가?피보나치 수열이었다.앞의 2자리 수는 1 0 으로 고정되어있기 때문에 앞의 2자리를 제외한 자리의 경우의 수가 중요하다.7개까지 끄적이며 찾아보다가 피보나치 수열이 확실하다고 생각하여 바로 제출하고..

오아시스 재결합링크: http://www.acmicpc.net/problem/3015 문제오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.문제 접근A와 B 사이에는 같거나 작은 값들만 존재해야 한다.2 4 1 2 2 5 1의 경우 총 10개의 쌍이 존재한다.(2,4), (4,1), (4,2), (4,2), (4,5), (1,2), (2,2), (2,5), (2,5), (5,1)풀이..

옥상 정원 꾸미기https://www.acmicpc.net/problem/6198 문제도시에는 N개의 빌딩이 있다.빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우 = = = = - = = = = -> 관리인이 보는 방향 = - =..