본문 바로가기

백준107

[백준] 3273번 두 수의 합 (투포인터 문제) 사용 언어 - Python3 문제 - 3273번 두 수의 합 투포인터 : 가능성을 지워주는 방법 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i 시간 복잡도 문제 ! 투포인터 알고리즘 활용 arr 정렬 후, s .. 2023. 11. 2.
[백준] 9251번 LCS (LIS 문제) 사용 언어 - Python3 문제 - 9251번 LCS LIS/LCS 문제 : 가장 긴 증가하는 부분 수열 LIS (Longest Incresing Subsequence) LCS (Longest Common Subsequence) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 정답 해당 위치 기준 나보다 작은 숫자가 있으면 추가해주기 dp[i] = max(dp[i], dp[j]+1) 완전탐색 방법).. 2023. 11. 1.
[백준] 2565번 전깃줄 (LIS 문제) 사용 언어 - Python3 문제 - 2565번 전깃줄 LIS/LCS 문제 : 가장 긴 증가하는 부분 수열 LIS (Longest Incresing Subsequence) LCS (Longest Common Subsequence) https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 정답 전체 n개에서 LIS 빼주기 dp[i] = max(dp[i], dp[j]+1) 전봇대에 겹친다 = A 전봇대 값이 작은 값 중에서, B전봇대 값이 더 크다. 안겹친다 = .. 2023. 11. 1.
[백준] 11053번 가장 긴 증가하는 부분 수열 (LIS문제) 사용 언어 - Python3 문제 - 11053번 가장 긴 증가하는 부분 수열 LIS/LCS 문제 : 가장 긴 증가하는 부분 수열 LIS (Longest Incresing Subsequence) LCS (Longest Common Subsequence) 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 정답 해당 위치 기준 나보다 작은 숫자가 있으면 추가해주기 dp[i.. 2023. 11. 1.
[백준] 1520번 내리막 길 사용 언어 - Python3 문제 - 1520번 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 정답 2차원 그래프의 DP # 모든 점을 방문 # 방문한 뒤 이동할 수 있는 모든 경우의 수를 재귀로 구현한다 # 재귀로 구현한 뒤 DP로 바꾼다. 현재 위치 graph[y][x] / 상하좌우 이동 dy,dx / 이동위치 ey, ex ey = y + dy, ex = x + ex 조건1) ex,ey가 m*n 그래프 안에 있어야함 조건2) .. 2023. 11. 1.
[백준] 19947번 욕심쟁이 판다 사용 언어 - Python3 문제 - 19947번 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 정답 2차원 그래프의 DP # 모든 점을 방문 # 방문한 뒤 이동할 수 있는 모든 경우의 수를 재귀로 구현한다 # 재귀로 구현한 뒤 DP로 바꾼다. 현재 위치 graph[y][x] / 상하좌우 이동 dy,dx / 이동위치 ey, ex ey = y + dy, ex = x + ex 조건1) n*n 그래프 안에 있어야함 0 조건.. 2023. 11. 1.
[백준] 1149번 RGB거리 사용 언어 - Python3 문제 - 1149번 RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 정답 바텀업 DP 손코딩, 아이큐 테스트, 규칙 찾기 문제 빨/초/파는 같은 rgb를 가진 집과 이웃하면 안되므로, 각 색깔을 기준으로 비용을 업데이트해준다. 빨 - 이전의 초 or 파 중 최솟값 + 현재의 빨 값 초 - 이전의 빨 or 파 중 최솟값 + 현재의 초 값 파 - 이전의 빨 or 초 중 최솟값 + 현재의 .. 2023. 10. 31.
[백준] 11726번 2xn 타일링 사용 언어 - Python3 문제 - 11726번 2xn 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 정답 피보나치 타일링 - 바텀업 DP 손코딩, 아이큐 테스트, 규칙 찾기 문제 # 규칙이 보여야만 풀수 있는 문제 => 많이 풀다보면 규칙이 보이는 문제이다. # 피보나치를 그림으로 만든 문제 0,1,1,2,3,5,8 dp[i] = dp[i-2] + dp[i-1] n dp 1 1 2 2 3 3 4 5 5 8 9 55 import sys input = sy.. 2023. 10. 31.
[백준] 12865번 평범한 배낭 (냅색 문제) 사용 언어 - Python3 문제 - 12865번 평범한 배낭 냅색 Knapsack 문제 : 여러 물건이 있을 때, 특정 조건을 만족하는 조합 구하기 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 정답 1. 완전 탐색적 재귀함수 => 시간 초과 def recur(idx, w, v) def recur(idx,w,v): global answer if w > k: # 버틸 수 있는 .. 2023. 10. 30.
[백준] 14501번 퇴사 사용 언어 - Python3 문제 - 14501번 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 정답 1. 완전 탐색적 재귀함수 def recur(day, total) recur(상담받는 날짜, 수익합) day = 0일부터 n-1일까지 반복 day가 n-1보다 크고, n보다 크면 무시 아니라면, total,answer 중 더 큰 수익값으로 업데이트 - 상담 하는 경우, 날짜+날짜만큼 더하기, 수익+수익만큼 더하기 - 상담 안하는 경우, 날짜+1, 수익 그대로 print(answer) def recur(day,total): global answer if day > n-1: #.. 2023. 10. 30.

티스토리툴바