본문 바로가기

OJ 문제풀이/BOJ5

BOJ #11053 가장 긴 증가하는 부분 수열 문제 원본 : 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 풀이법은 다음과 같습니다. 두 개의 값을 저장할 배열을 선언합니다. 하나는 입력받는 숫자를 저장하는 배열, 다른 하나는 정답을 저장할 배열입니다. 배열에 저장된 값들을 차례대로 탐색하면서 자신보다 작은 값을 찾았다면 그 지점에서의 수열의 길이를 불러옵니다. 단, 불러올 때에 지금까지 가지고 있던 길이보다 더 긴 경우에만 값을 가져옵니다. 위와 같은 공정.. 2019. 10. 7.
BOJ #1976 여행 가자 문제 원본 : 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 www.acmicpc.net 풀이법은 다음과 같습니다. Union-Find 알고리즘을 사용하여 도시와 도시 사이 연결정보를 저장합니다. 모든 길에 대한 입력을 받고 연결 정보를 배열에 저장합니다. (본문에서 int형.. 2019. 9. 24.
BOJ #10026 적록색약 문제 원본 : 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 www.acmicpc.net 출처 : USACO(미국정보올림피아드) 2013-2014 Season USACO March 2014 Contest Bronze 3번 풀이법은 다음과 같습니다. 먼저 적당한 배열을 선언하여 .. 2019. 9. 23.
BOJ #1932 정수 삼각형 문제 원본 : 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 www.acmicpc.net 출처 : 1994 IOI(국제정보올림피아드) 1번 풀이법은 다음과 같습니다. 먼저 적당한 배열을 설정하여 삼각형을 입력 받습니다. (본문에서는 int형 배열 t) 정답과 연산과정이 저장될.. 2019. 9. 23.
BOJ #6198 옥상 정원 꾸미기 문제 원본 : https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다. 그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다. 예) N=6, H = {10, 3, 7, www.acmicpc.net 출처 : USACO 2006 November 2006 Contest Silver 1번 풀이법은 다음과 같습니다. .. 2019. 9. 22.