백준 문제풀이 (31) 썸네일형 리스트형 [백준(BOJ)/C++] 10211번: Maximum Subarray - 코딩밥상 https://www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 접근 방법, 논리 흐름(알고리즘) 이 문제의 키워드는 "연속한" 부분 배열이라고 생각했다. 각 인덱스에서의 최댓값을 dp에 저장하는데, 만약 그 전 인덱스들의 합이 양수이면 전 배열들의 합과 해당하는 수의 합이 그 인덱스의 최댓값일 것이고, 전 인덱스들의 합이 음수이면 그냥 해당 인덱스의 값이 최댓값이 될 테니까 그대로 dp에 저장해준다. 풀.. [백준(BOJ)/C++] 11726번: 2xn 타일링 - 코딩밥상 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 접근 방법, 논리 흐름(알고리즘) 문제를 보고 일단 빈 종이에 n값이 변할 때의 경우들을 그려보았다. 여기서 찾을 수 있는 규칙은 n이 1씩 증가하는데, n이 3이상일 때 2가지의 경우만 고려하면 된다. 1. n이 증가하면서 끝자리에 2x1의 막대가 추가되는 경우(세로 막대) 2. n이 증가하면서 끝의 두자리에 2x2의 막대가 추가되는경우 (가로막대 2층) 첫번째의 경우는 그 전 단계에 끝에 세로막대만 추가하면 되기때.. [백준(BOJ)/C++] 18111번: 마인크래프트 - 코딩밥상 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 접근 방법, 논리 흐름(알고리즘) 전에 풀었던 브루트포스 문제들과 다른점은 순열이나 조합을 사용하지 않고 말 그대로 완전탐색을 통해 모든 경우를 확인해 보았다. 2차원 배열로 땅을 입력 받고 처음에는 칸 하나하나를 기준점으로 두고 완전탐색을 했는데 시간초과가 나서, 문제를 자세히 읽어보니 높이의 최대값이 256인 것을 알고 높이(0~256)를 기준으로 잡고 탐색하였다. 여기서 까다로웠던 점은 여.. [백준(BOJ)/C++] 14888번: 연산자 끼워넣기 - 코딩밥상 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 접근 방법, 논리 흐름(알고리즘) 문제에서 요구하는 것은 문제에서 주어진 연산자를 사용하여 계산 결과의 최댓값과 최솟값이다. 단 숫자의 순서는 유지하고 연산자의 우선순위 또한 고려하지 않고 순서대로 계산하면 되는 문제이다. 시간 제한도 넉넉하고 연산자의 갯수가 최대 10개라서 완전탐색을 하면 되겠다. 연산자의 순서에 따라 결과값이 달라지기 때.. [백준(BOJ)/C++] 24891: 단어 마방진 - 코딩밥상 https://www.acmicpc.net/problem/24891 24891번: 단어 마방진 단어 마방진을 출력한다. 만들 수 있는 단어 마방진이 여러 개인 경우, 사전 순으로 가장 빠른 단어 마방진을 출력한다. 어떤 경우에도 단어 마방진을 만들 수 없는 경우 "NONE"을 따옴표를 제외하 www.acmicpc.net 접근 방법, 논리 흐름(알고리즘) 문제를 보면 길이가 L인 N개의 단어가 주어지는데, 조건을 만족하는 L개의 문자열 배열이 답이 될 수 있는 후보이다. 즉 길이가 L인 L개의 문자열의 배열(L x L)이 후보이다. 여기서 생각한것이, N개의 문자열 중 L개를 뽑아 순서를 바꿔가며 조건을 만족하는 배열을 찾으면 되겠구나 생각했다. 즉 문자열 L개를 순열 방식으로 모든 경우를 돌려(부르트포스.. [백준(BOJ)/C++] 6603: 로또 - 코딩밥상 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 접근 방법 이 문제는 저번에 stl을 이용하여 조합을 구현하는 방법으로 풀었던 문제인데, 이번에는 이번주 스터디 브루트포스 중에서도 백트래킹을 이용하여 다른 풀이로 풀어보았다. 방법은 dfs라고 할 수 있는데, 로또 번호가 6개 필요하기 때문에 첫번째 수 부터 6번째 수 까지의 가능한 후보군을 만들고 dfs로 출력하면 된다. 논리 흐름(알고리즘) 사전순으로 수들이 주어지기 때문에 sor.. [백준(BOJ)/C++] 3049번: 다각형의 대각선 - 코딩밥상 https://www.acmicpc.net/problem/3049 3049번: 다각형의 대각선 세 대각선이 한 점에서 만나지 않는 볼록 N각형이 주어졌을 때, 대각선의 교차점의 개수를 세는 프로그램을 작성하시오. 아래 그림은 위의 조건을 만족하는 한 육각형의 교차점 그림이다. 모든 www.acmicpc.net 접근 방법 도형의 구성 요소의 개수를 세는 문제는 보통 서로간의 연관성에서 얻을 수 있다. 이는 보통 중학교 수학에서 배웠던 내용들이라 큰 어려움은 없을것이다. 다음 문제에서는 n각형 즉 꼭지점의 개수를 알려주었기 때문에 꼭지점과 문제에서 요구하는 답을 연관지어 생각하면 될것이다. 논리 흐름(알고리즘) 문제에서 요구하는 답은 꼭지점을 이어 만든 대각선들이 만나 생기는 교차점의 개수이다. 이를 연관지.. [백준(BOJ)/C++] 2217번: 로프 - 코딩밥상 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 접근 방법 모든 줄에 중량이 w/k만큼 걸린다는 말은 최소로 들 수 있는 줄의 중량값이 모든 줄에 걸린다는 뜻이다. 즉 (가장 약한 줄에 걸린 중량)*(관여한 줄의 수)가 들아올릴 수 있는 물체의 중량이다. 처음에는 줄의 최솟값을 구하고 n값을 곱한것이 답이라 생각하고 너무 쉽다 룰루랄라 했지만, 문제를 잘 읽어보면 "임의로 몇개의 로프를 골라서 사용해도 된다" 라고 나와있다. 이 문장이.. 이전 1 2 3 4 다음
