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

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)
  • 방명록

다이나믹프로그래밍 (7)
[백준 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
[백준 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
[백준 1463] 알고리즘 43일차 : 1로 만들기

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적계획법 C++ 문제는 위에 사진 참고 (설명 매우 귀찮다 딱히 요약할 것도 없응께) N의 범위는 1부터 10^6 까지 접근방법 n개의 정수 배열을 사용한다. 배열에는 해당 수가 1이 되는데에 필요한 연산의 최소 횟수가 저장된다. 1: 0회, 2: 1회, 3: 1회까지 미리 저장해두고 4부터는 [ 1을 뺀 수의 연산 최소횟수 + 1 , 3으로 나눈 값의 연산 최소횟수 + 1 (3으로 나누어질때만), 2로 나눈 값의 연산 최소횟수 + 1 (2로 나누어질때만) ] 이 중 가장 작은 값을 해당 인덱스의 배열에 저장..

알고리즘 문제풀이 2020. 8. 13. 14:56
[백준 2579] 알고리즘 42일차 : 계단 오르기

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 동적계획법 C++ 연속으로 세칸을 오를 수 없고 / 그림처럼 한 칸 혹은 두 칸씩 오를 수 있다. 각 계단 마다 점수가 배정돼있고 위의 규칙을 지키면서 그 점수의 합이 최대가 되는 경우 최댓값을 출력하기 접근방법 이 문제도 작은 부분에서의 최댓값을 구해가면서 풀었다. 각 칸에서의 최댓값을 저장하면서 갱신해갔다. 해당 칸에서 그 전칸의 최댓값, 그 전전칸의 최댓값을 비교해가면서 저장해간다. 너무 추상적으로 썼는..

알고리즘 문제풀이 2020. 8. 12. 21:38
[백준 1932] 알고리즘 41일차 : 정수 삼각형

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 동적계획법 C++ 숫자 트리에서 숫자들의 합이 최대가 되는 경로 구하기(최댓값 출력) 접근방법 전형적인 DP 상향식 풀이로 풀었다. 가장 밑 행부터 모든 숫자에 대해 해당 자리까지의 최댓값을 저장해가면서 값을 갱신한다. 예를들어 위의 사진에서 4번째 행 첫번째 자리 2에서 최댓값을 가지려면 4,5중 5를 선택해야하니까 원래 2가 있던 자리에 2+5 = 7을 저장한..

알고리즘 문제풀이 2020. 8. 11. 15:35
[백준 11051] 알고리즘 35일차 : 이항 계수 2

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 수학3, 동적계획법 C++ 이항계수를 동적계획법으로 푸는 문제 (간략) 작년 알고리즘 수업에서 배우고 또 비슷한 손코딩 문제가 시험에도 나왔었던 문제 이항계수였는지는 기억안남 DP에서 피보나치와 함께 배운 기억이 난다. 두 문제 모두 재귀를 배울때 나오는 개념들이지만 사실 시간복잡도면에서 보면 배열을 사용해서 반복문을 쓰는게 훨씬 효율적이다. (이걸 동적계획법 부분에서 배움 매번 이런식이지 비효율적인거 실컷 가르쳐놓고 효율적인 방법 나중에 알려주기 교수님 : 하지만 ..

알고리즘 문제풀이 2020. 7. 31. 20:44
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • [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
  • 최소힙
  • 정렬
  • c++
  • 트리
  • 가장 큰 수 Swift
  • 투포인터
  • 자바
  • 동적계획법
  • 브루트포스
  • 웹크롤링
  • 최단경로
  • 백트래킹
  • 파이썬
  • 이분탐색
  • 다이나믹프로그래밍
  • Swift
  • 스택
  • 그리디알고리즘
  • 토마토
  • 최대힙
  • 알고리즘
  • 수학
  • 프로그래머스
  • dp
  • 우선순위큐
  • dfs
  • 가장 큰 수 프로그래머스
  • BFS
  • 게임이론
  • 백준
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

티스토리툴바