본문 바로가기 메뉴 바로가기

SiO2whocodes

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

SiO2whocodes

검색하기 폼
  • 분류 전체보기 (205)
    • 알고리즘 문제풀이 (168)
    • iOS (12)
      • swift (1)
    • Spring (2)
    • Research Paper (4)
    • coding() (10)
      • Git (4)
    • 책 (2)
    • PHOKI (1)
    • Culture Cabinet (1)
    • 기타 (0)
  • 방명록

동적계획법 (17)
[백준 11066] 알고리즘 94일차 : 파일 합치기

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 동적계획법 핵심 로직 dp[i][j] = dp[i][mid]+dp[mid+1][j] + 누적합(최상위 노드값) 3중 for문을 도는데 첫번째 반복문은 gap 그러니까 범위다 start~end 범위 크기를 1부터 chapter수인 K-1개까지 반복한다. (그럼 마지막 반복문을 돌면 0~K-1까지를 구할 수 있음) 두번째 반복문은 start~end범위 내에서 start의 위치를 한칸씩 뒤로 ..

알고리즘 문제풀이 2021. 6. 28. 17:41
[백준 12865] 알고리즘 53일차 : 평범한 배낭

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 동적계획법 C++ 2020 하계 방학 알고리즘 스터디의 마지막을 장식할 DP 문제 knapsack 문제다!!! 문제는 설명하기 입아프니 위 사진을 참고하도록 하시고 이번 여름방학 스터디 마지막 문제로 knapsack 문제를 정석으로 코드를 짜보려고 이 문제를 골랐다. 접근방법 상향식 접근, 최적의 원리 등의 접근으로 풀이하는 대표적..

알고리즘 문제풀이 2020. 8. 28. 16:13
[백준 11057] 알고리즘 52일차 : 오르막 수

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 동적계획법 C++ 오르막수 구하기 문제 접근 방법 자리수 별로 오르막수를 저장하는 배열을 사용한다. 소스코드 #include using namespace std; int main(){ int n; cin >> n; int dp[1000][10]={0}; for(int i = 0 ; i < 10 ; i++) dp[0][i] = 1; for(int i = 1 ; ..

알고리즘 문제풀이 2020. 8. 27. 21:48
[백준 11054] 알고리즘 51일차 : 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 동적계획법 C++ 가장 긴 바이토닉 부분 수열 문제 접근 방법 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열이 중첩된 문제 0부터 i 까지의 가장 긴 증가하는 부분 수열을 구하고, i 부터 n까지 감소하는 부분 수열을 구하여 합한 값으로 구한다. 증가하는 부분 수열은 차이가 없지만, 감소하는 부분 수열은 원래는 i까지 감소하는 부분수열을 구했었는데 여기선 i부터 n까지 감소하는 부분 수열을 구한다는 점이..

알고리즘 문제풀이 2020. 8. 26. 23:49
[백준 9095] 알고리즘 50일차 : 1,2,3더하기

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net 동적계획법 C++ n이 1,2,3의 합으로 구성되는 경우의 수를 구하는 문제 (조합아님) 접근 방법 n을 1,2,3의 합으로 나타내는 경우의 수는 ( n-1의 경우 + n-2의 경우 + n-3의 경우) 이다. 순서가 상관있는 문제기때문에 n-1의 경우에 +1 을 한 경우들, n-2의 경우에 +2를 한 경우들, n-3의 경우에 ..

알고리즘 문제풀이 2020. 8. 25. 22:47
[백준 11722] 알고리즘 48일차 : 가장 긴 감소하는 부분 수열

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} � www.acmicpc.net 동적계획법 C++ 이번엔 감소하는 부분 수열이다. 접근 방법 가장 긴 증가하는 부분수열에서 감소하는 부분수열로 바뀌었을 뿐이다. 비교할때 이 점을 유의해서 비교하면 된다. 소스코드 #include using namespace std; int main(){ int n; cin >> n ; int num[n]; int le..

알고리즘 문제풀이 2020. 8. 21. 18:57
[백준 11055] 알고리즘 47일차 : 가장 큰 증가 부분 수열

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 동적계획법 C++ 이번엔 가장 큰 증가하는 부분 수열의 합 구하기 접근 방법 지난번 풀었던 가장 긴 증가하는 부분 수열과 로직이 유사하다. 차이점은 우선 합을 저장해야한다는 점과 가장 긴 부분 수열의 경우 부분 수열이 성립할 경우 길이가 1만 증가했지만 이번엔 합이어서 본인의 수 만큼 증가하므로 비교할 때 이 부분을 주의해야 했다. 소스..

알고리즘 문제풀이 2020. 8. 20. 21:35
[백준 10844] 알고리즘 46일차 : 쉬운 계단 수

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 동적계획법 C++ 쉬운계단수 구하기 접근방법 1~8까지는 괜찮은데 0,9가 문제였다. 그래서 0,9 경우를 따로 계산하고 우선 기본적인 접근은 n번째 자리에 오는 0부터9까지의 숫자의 갯수를 저장하는 배열을 사용한다. 0의 개수는 이전 자리의 1의 개수 1~8(i)의 개수는 이전 자리의 i-1의 개수 + i+1의 개수 9의 개수는 이전 자리의 8의 개수 그리고 마지막에 n번째 자리에 오는 0~9의 개수를 모두 더한 값을 출력한다. 처음엔 마지막에 값을 더할때 나머지 계산을 안하고, 1~8의 경우를 저장할 때 i..

알고리즘 문제풀이 2020. 8. 18. 20:13
[백준 11053] 알고리즘 45일차 : 가장 긴 증가하는 부분 수열

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++ 가장 긴 증가하는 부분 수열을 구하는 문제 접근 방법 DP라서 뭔가 2중 for문은 안될 것 같다고 생각하다가 최대 N이 1000이고 제한시간이 1초면 2중 for문도 되겠다 싶어서 그렇게 구현했다. 이번에도 각 인덱스 까지의 최대길이를 갖고 있는 배열을 사용했다. 다만 2중 for문을 사용해야 했던 ..

알고리즘 문제풀이 2020. 8. 17. 20:11
[백준 2156] 알고리즘 44일차 : 포도주 시식

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 동적계획법 C++ 계단 오르기 문제와 로직이 동일해보여서 풀기 시작했는데 닮은듯 달랐다. 계단오르기와 차이점은 우선 두칸이상 건너뛸 수 있다. (근데 사실상 세칸이상 건너뛰는 경우는 없다. 가운데 하나를 먹어야 이득이니까) 그리고 꼭 마지막 주스를 먹어야할 필요가 없다. (최종 값을 출력할때 n-1칸과 n-2칸의 값을 비교해서 출력해야함) 차이점은 두갠데 그래서 많은 것이 추가됐다.. 접근방법은 계..

알고리즘 문제풀이 2020. 8. 14. 18:59
이전 1 2 다음
이전 다음
공지사항
최근에 올라온 글
  • [TSC-2021] A Missing QoS Pr⋯
  • [EdgeCom-2020] Green comput⋯
  • [FGCS-2018] An SVM-based co⋯
  • [IEEE TSC-2020] A Survey on⋯
최근에 달린 댓글
  • 그러네요! 지금 다시 0 예외 처리 해주지 않고 제출했⋯
  • 궁금한게 있는데요.. 입력에 N은 1000000보다 작⋯
  • 프로그램을 실행파일로 올려놓은 것이 문제가 됐던 것 같⋯
  • 확인이 늦어서 죄송합니다. 실행파일로 올려놓은 것이 문⋯
Total
7,437
Today
18
Yesterday
50
링크
TAG
  • 트리
  • 프로그래머스
  • 스택
  • 투포인터
  • 토마토
  • dfs
  • 최단경로
  • 가장 큰 수 Swift
  • dp
  • 정렬
  • 최대힙
  • 파이썬
  • BFS
  • 백트래킹
  • 알고리즘
  • Swift
  • 수학
  • 게임이론
  • 동적계획법
  • 백준
  • 이분탐색
  • 자바
  • 최소힙
  • c++
  • 브루트포스
  • 다이나믹프로그래밍
  • 우선순위큐
  • 그리디알고리즘
  • 웹크롤링
  • 가장 큰 수 프로그래머스
more
«   2023/02   »
일 월 화 수 목 금 토
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
글 보관함
  • 2023/01 (4)
  • 2022/06 (1)
  • 2022/04 (9)
  • 2022/03 (22)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바