백준 온라인 저지(BOJ) 2565번 전깃줄 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 2개의 전봇대에 연결되는 전깃줄의 위치 번호가 주어질 때 남아있는 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력 2. 풀이 LIS(Longest Increasing Subsequence)로 풀 수 있는 문제입니다. 백준 LIS 문제 설명 및 풀이는 아래 링크 참고하시면 됩니다. http..
백준 온라인 저지(BOJ) 11054번 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 증가하다가 감소하는 수열을 바이토닉 수열이라고 할 때, 주어진 수열 A의 부분 수열 중 가장 긴 바이토닉 부분 수열의 길이를 출력 2. 풀이 백준 단계 별로 풀어보기의 직전 문제인 가장 긴 증가하는 부분 수열 문제를 풀어봤다면 약간의 아이디어만 더해서 쉽게 풀 수 있는 문제입니다. https://rightb..
백준 온라인 저지(BOJ) 11053번 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 주어진 수열에 대해서 가장 긴 증가하는 부분 수열의 길이를 출력 2. 풀이 Dynamic Programming으로 푸는 대표적인 문제로 LIS(Longest Increasing Subsequence)라고 부릅니..
백준 온라인 저지(BOJ) 2156번 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net* 사용언어 : C언어, C++ 1. 문제일렬로 놓여진 포도주 N잔을 최대로 마실 수 있는 포도주의 양 출력 단, 연속으로 놓여진 3잔을 모두 마실 수 없음 2. 풀이단계 별로 풀어보기 > 동적 계획법를 순서대로 풀던 중에서 가장 난항을 겪었던 문제입니다. DP가 어느정도 익숙해졌다고 생각했는데 아직 갈 길이 먼 것 같습니다. DP 배열을 2차원이나 3차..
백준 온라인 저지(BOJ) 10844번 쉬운 계단수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 인접한 모든 자리의 차이가 1인 수를 계단 수라고 할 때, 길이가 N인 모든 계단 수의 개수를 출력 (ex. 45656) 2. 풀이 전형적인 Dynamic Programming 문제로 메모이제이션 용도로 2차원 dp 배열을 선언했습니다. 2차원 배열 중 첫 번째 차원의 index는 숫자의 자리 수(숫자의 위치)를 의미하고, 두 번째 차원의 index는 각 자리에 들어올 수 있는 숫자를 의미합니다. 예를 들어 dp[2]..
백준 온라인 저지(BOJ) 1463번 1로 만들기 https://www.acmicpc.net/problem/1463 * 사용언어 : C언어, C++ 1. 문제 정수 X에 가할 수 있는 연산은 3가지(3으로 나누기, 2로 나누기, 1 빼기) 3가지 연산을 활용하여 X를 1로 만들 때 연산을 사용하는 최소값 출력 2. 풀이 Dynamic Programming의 Bottom-Up 방식을 활용하여 O(N)의 시간 복잡도로 풀 수 있는 문제입니다. i번째의 dp 값을 구하는 규칙은 상당히 간단한데, 아래 3개의 값 중 최소값을 골라서 저장하면 됩니다. 1) dp[i / 3] + 1 (i가 3으로 나누어지는 경우) 2) dp[i / 2] + 1 (i가 2로 나누어 지는 경우) 3) dp[i - 1] + 1 저는 i..
백준 온라인 저지(BOJ) 2579번 계단 오르기 https://www.acmicpc.net/problem/2579 * 사용언어 : C언어, C++ 1. 문제 점수가 쓰여진 300개 이하의 계단을 한 계단 or 두 계단 씩 오를 때 지나온 계단의 총 점수의 최대값을 출력 (단, 연속된 세 개의 계단을 밟을 수 없고, 마지막 계단은 반드시 밟아야 함) 2. 풀이 bottom-up 방식으로 풀기 위해서 크기가 N * 2인 2차원 배열을 선언했습니다. 배열의 i번(1차원) index에 있는 2개의 값은 각각 [① i번 계단에 도착하기 직전에 한 계단을 올라왔을 때의 최대값]과 [② 두 계단 올라왔을 때의 최대값]을 구해서 저장합니다. 그리고 마지막에 dp[N - 1][0]과 dp[N - 1][1] 중 큰 값을..
백준 온라인 저지(BOJ) 1932번 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 크기가 N인 정삼각형에 각 숫자가 채워져 있음 맨 위층부터 대각선 왼쪽, 오른쪽 둘 중 하나를 선택해서 내려올 때 합이 최대가 되는 경로에 있는 수의 합을 출력 2. 풀이 규칙이 명확하게 주어진 문제이기 때문에 bottom-up 방식으로 구현하였습니다. 우선 정사각형을 주어진 그대로 2차원 배열로 입력을 받습니다. 그리고 각 위치의 숫자에 왼쪽 위(x - 1) dp 값과 오른쪽..
백준 온라인 저지(BOJ) 1149번 RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 N개의 집을 R, G, B 중 하나의 색으로 칠해야 함 각각의 집을 색칠하는 비용이 주어질 때, 인접한 집의 색이 다르도록 모든 집을 칠하는 비용의 최소값을 출력 2. 풀이 N번 집을 Red로 색칠할 때의 총 비용은 [N번 집 Red 색칠 비용] + min([N - 1번 집 Green ..
백준 온라인 저지(BOJ) 9461번 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 아래 그림과 같이 삼각형들이 나선 모양(시계 방향)으로 놓여져 있음 P(N)은 나선 중 N번째 정삼각형의 변의 길이일 때 P(N)을 출력 2. 풀이 수열의 규칙을 찾아 bottom-up 방식으로 구현하여 풀면 됩니다. 초반 삼각형들을 살펴보면 규칙이 잘 안 보이는데 오히려 그림에서 큰 삼각형(7, 9, 12 등..
- Total
- Today
- Yesterday
- 호암의마지막꿈
- 긴 자리 곱셈
- 나는늘잘해야한다고생각한다
- 나의첫죽음학수업
- 정세현의통찰
- 지루함의심리학
- 동탄에듀센터2
- 역사의쓸모
- 긴 자리 덧셈 뺄셈
- 인간본성불패의법칙
- AdSendse
- 당신도느리게나이들수있습니다
- 자동차보험
- 자이언트임팩트
- JUNGOL
- 원서잡아먹는영작문
- 센터독서클럽
- 정올
- 내가틀릴수도있습니다
- 문현공
- 삼성전자
- 여가포인트
- 동탄에듀센터
- 최재천의공부
- 세상을 읽는 새로운 언어 빅데이터
- 안전운전특약
- 독서감상평
- 쿠프마케팅
- 영화감상평
- 독서 감상평
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |