티스토리

AndroidTeacher

검색하기

블로그 홈

AndroidTeacher

hongcoding.tistory.com/m

안드선생 님의 블로그입니다.

구독자: 31

방명록 방문하기

주요 글 목록

[백준] 11660 구간 합 구하기 5 (Python 파이썬) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 설명 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하.. 공감수 1 댓글수 0 2022. 8. 12.
[백준] 2565 전깃줄 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 자세한 문제 설명은 위 링크를 참고하시길 바랍니다. 풀이 과정 이 문제는 DP(다이나믹 프로그래밍)을 이용해 최대 증가 수열을 찾는 문제라고 할 수 있다. 전깃줄이 교차하지 않도록 하려면 어떻게 해야할지에 대해 먼저 생각해보자. 먼저, 위 그림에서 A의 1번과 B의 8번만 연결되어 있다고 가정해보자. 그리고 이 때, 아래의 ①번 상황과 ②번 상황을 각각 생각해보자. ① A의 2번과 B의 2번이.. 공감수 0 댓글수 0 2022. 5. 14.
[백준] 1912 연속합 (Python 파이썬) https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 설명 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 풀이 과정 이 문제는 DP(다이나믹 프로그래밍)을 이용해 .. 공감수 0 댓글수 0 2022. 4. 28.
[백준]11054 가장 긴 바이토닉 부분 수열 (Kotlin) 문제 설명 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} .. 공감수 0 댓글수 0 2021. 11. 29.
[백준] 10844 쉬운 계단 수 (Kotlin 코틀린) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명 5656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 풀이 과정 이 문제는 단계마다의 규칙을 찾아 점화식을 세워 구현하는 DP 문제이다. 길이 1짜리 계단을 생각해보면, 1 2 3 4 5 6 7 8 9 총 9개의 계단이 있다. 길이 2짜리 계단을 생각해보면, 10 12 21 23 32 34 43 45 ... 87 89 98 로 총 17개가 있다. .. 공감수 0 댓글수 0 2021. 11. 28.
[백준] 2579 계단 오르기 (Python 파이썬) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 설명 위 링크에 주어진 문제 설명처럼, 계단을 오르는 문제이다. 단, 3번 연속된 계단을 이어서 오를 수는 없으며 마지막 계단은 무조건 밟아야 한다. 풀이 과정 이 문제는 DP(다이나믹 프로그래밍)을 이용해 앞에서 부터 최대값을 저장해 나가야 한다. 현재 계단을 밟는다면, 이전과 이이전을 연속해서 밟으면 안된다. 따라서, 현재 계단의 최댓값은 현재 + 이전 + 이이이전 or 현재 + 이이전 중에 선택을 .. 공감수 0 댓글수 0 2021. 11. 6.
[백준] 1932 정수 삼각형 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 주어진 그림처럼 삼각형 모양으로 숫자가 주어진다. 맨 위부터 시작해 제일 아래쪽으로 탐색을 하게되는데, 현재 지점에서 다음 지점(아래 지점)으로 이동할 때는, 왼쪽대각선과 오른쪽 대각선으로만 갈 수 있다. 이 방법으로 탐색했을 때, 탐색경로에 있는 숫자들을 모두 더했을 때의 최대가 되는 경로를 구하는 문제이다. 풀이 과정 이 문제는 DP(다이나믹 프로그래밍)을 이용해 앞에서부터 최댓값을 저장해나가며 푸는 문제이다. 가장 첫번째 열에 있는 숫자(7, 3, 8,.. 공감수 0 댓글수 0 2021. 11. 6.
[백준] 1149 RGB거리 (Python 파이썬) https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 설명 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-.. 공감수 0 댓글수 0 2021. 10. 8.
[백준] 1904 01타일 (Python 파이썬) https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 설명 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었.. 공감수 0 댓글수 0 2021. 10. 8.
[백준] 9184 신나는 함수 실행 (Python 파이썬) https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 설명 if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1.. 공감수 1 댓글수 0 2021. 10. 8.
[백준] 10164 격자상의 경로 (Python 파이썬) https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 문제 설명 격자 맵과 한 지점이 주어졌을 때, 시작점 부터 그 지점을 거쳐 종료점까지 만들 수 있는 경로의 개수를 구하는 문제이다. 풀이 과정 경우의 수와 DP를 활용하는 문제이다. 초등학교 때 길 찾기 경우의 수를 배울 때 이러한 방법을 사용했을 것이다. 1 1 1 1 1 2 3 4 1 3 6 10 위 표처럼 가장 첫 칸과 첫 행을 1로 채우고 다음칸부터 왼.. 공감수 0 댓글수 0 2021. 10. 6.
[백준] 9465 스티커 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사.. 공감수 0 댓글수 0 2021. 10. 5.
[백준] 2133 타일 채우기 (Python 파이썬) https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 설명 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 풀이 과정 먼저, 벽을 체울 수 있는 경우의 수를 구해보자. 벽의 가로길이가 홀수라면 벽을 가득 체울 수 없다. 예를 들어, N = 1 이라면 아래 한 칸이 남기 때문에 벽을 체울 수 없다. (타일은 2x1과 1x2만 존재하기 때문에) N = 2 일때는 다음과 같이 3가지 경우의 수가 존재한다. N = 4 일 때는 가로를 반으로 나눠 N = 2가 2개 있다고 생각할 수 있다. 그래서 앞의 3가지 x 뒤의 3가지 = 9.. 공감수 1 댓글수 0 2021. 9. 14.
[백준] 2098 외판원 순회 (Python 파이썬) https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 설명 자세한 문제 설명은 위 링크를 참조해 주세요 1번부터 N번까지의 도시가 있고, 어느 한 도시를 출발하여 모든 도시를 찍고 다시 출발지점으로 돌아오는데 드는 최소 비용을 구하는 문제이다. 풀이 과정 이 문제는 비트마스킹 + DP + DFS 를 모두 활용하는 문제로 난이도가 있는 문제이다. 각 도시를 방문했는지의 여부는 비트마스킹( 0001, 0002 .. 공감수 5 댓글수 3 2021. 9. 14.
[백준] 12865 평범한 배낭(Python 파이썬) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 설명 이 문제는 아주 평범한 배낭에 관한 문제이다. 흔히, 냅색(Knapsack) 알고리즘이라고 불리는 문제이다. 배낭의 용량이 정해져 있을 때, 최대한의 가치를 가지도록 배낭을 싸야 한다. 주어진 물건들의 용량과 가치를 고려하여 주워담을지 말지 정하는 문제이다. 풀이 과정 먼저, 내 배낭이 버틸 수 있는 용량이 7이라고 하자.. 공감수 11 댓글수 0 2021. 4. 21.
[백준] 2252 합분해 (Python 파이썬) www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 풀이 과정 이 문제는 코드는 간단해보일지 몰라도, 아이디어를 떠올리는 과정이 굉장히 까다로웠다. 나는 DP와 순열과조합의 개념을 조합하여 아이디어를 떠올렸다. 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 d[N][K]에 저장한다고 하자. N = 2, K = 1 일 경우 0부터 2까지.. 공감수 0 댓글수 0 2021. 4. 21.
[백준] 2156 포도주 시식 (Python 파이썬) www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 설명 포도주가 ( a, b, c, d, e, f ) 식으로 일렬로 나열되어 있다. a, b, c, d...는 포도주의 용량을 뜻한다. 연속으로 3잔 이상을 마실 수 없을 때, 최대로 마실 수 있는 포도주의 용량을 구하면 된다. 풀이 과정 6잔의 포도주 ( 6, 10, 13, 9, 8, 1 ) 가 있다고 생각해보자. 마지막 포도주를 마실지 말지를 결정하는 상황이라고 할 때, 내가 9와 8을 이미 마셨다면 1은.. 공감수 5 댓글수 0 2021. 4. 20.
[백준] 1003번 피보나치 함수 (Python 파이썬) www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 설명 자세한 문제 설명은 위의 링크에 나와있습니다! 피보나치 함수란, N번째 수의 값이 N-1 + N-2 의 값이 되는 함수입니다. fibonacci(N) 을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 문제입니다. 풀이 과정 이 문제를 문제에서 주어진 C++코드를 그대로 이용해 0과 1의 횟수를 구하려고 하면 시간초과가 난다. 왜냐하면 f(10)을 호출했다고 가정할 때, f(10) = f(9) + f(8)이 되기 때문에 f(9)와 f(8)을 한번씩 호출하게 되는데, f(9) = f(8)+f.. 공감수 0 댓글수 0 2021. 4. 19.
[백준] 1463번 1로 만들기 (Python 파이썬) www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 과정 이 문제는, 전의 결과를 다음 결과에 이용하게 되는. 점화식을 활용한 DP 문제이다. X = 10인 경우, 10 -> 9 -> 3 -> 1 과정을 거쳐 1이 되게 되는데 9의 경우에는 또, 9 -> 3 -> 1의.. 공감수 6 댓글수 0 2021. 4. 19.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.