본문 바로가기
반응형

알고리즘80

[Python] Baekjoon - 11055. 가장 큰 증가 부분 수열 백준 11055번 가장 큰 증가 부분 수열은 수열의 증가 부분 수열 중 원소들의 합의 최댓값을 구하는 문제다. 다이나믹 프로그래밍 기법을 통해 해결할 수 있으며 난이도는 실버 2이다. 백준 11055번 가장 큰 증가 부분 수열 문제 정보 알고리즘 분류 다이나믹 프로그래밍 난이도 실버 2 가장 큰 증가 부분 수열 문제 요약 수열의 증가 부분 수열 중 원소들의 합의 최댓값 구하기 부분 증가수열은 [1,1,3,2,4]에서 [1,3,4]처럼 원소가 증가하는 부분 수열(같은 원소 X) 문제 풀이 방법 과정 증가 부분 수열이 크거나 '같으면'되는 줄 알고 풀었다가 계속 틀려서 한참 헤맸다.. 다이나믹 프로그래밍을 이용해서, i번째 수를 포함하는 증가 부분 수열 중 원소 합의 최댓값을 저장하는 배열 S를 만들어 사용.. 2021. 9. 12.
[Python] Baekjoon - 1103. 게임 백준 1103번 게임은 숫자 또는 구멍으로 채워진 게임판에서 구멍에 빠지지 않고 최대로 움직일 수 있는 횟수를 구하는 문제다. 그래프 탐색 또는 다이나믹 프로그래밍 기법으로 해결할 수 있으며 난이도는 골드 2이다. 백준 1103번 게임 문제 정보 알고리즘 분류 그래프 탐색 다이나믹 프로그래밍 난이도 골드 2 게임 문제 요약 N * M 크기의 게임판의 각 칸에는 숫자 또는 H(구멍)이 표시되어 있음 숫자 칸은 그 칸에 적혀있는 수만큼 상/하/좌/우로 이동 가능 구멍에 빠지거나 게임판을 벗어나면 게임 종료 왼쪽 맨 위칸에서 출발할 때, 최대로 움직일 수 있는 횟수 구하기(처음 놓는 횟수 포함) 문제 풀이 방법 과정 BFS에 visited를 사용하다가 사이클 판별이 어렵다는 걸 깨닫고 DFS로 변경 현재 경로.. 2021. 9. 12.
[Python] Baekjoon - 1700. 멀티탭 스케줄링 백준 1700번 멀티탭 스케줄링 문제는 N구의 콘센트와 K개의 제품 사용 순서가 주어졌을 때 콘센트를 뽑는 최소 횟수를 구하는 문제다. 그리디 알고리즘을 사용해 해결할 수 있으며 난이도는 골드 1이다. 백준 1700번 멀티탭 스케줄링 문제 정보 알고리즘 분류 - 그리디 알고리즘 난이도 - 골드 1 멀티탭 스케줄링 문제 요약 N구 콘센트와 제품 사용 순서(K개)가 주어졌을 때, 콘센트를 뽑는 최소 횟수 구하기 문제 풀이 방법 과정 매 순서마다, 콘센트가 모자라면 꼽혀있는 제품 중 뽑을 거 하나 골라야 함 앞으로 남은 리스트를 보고, 꼽혀있는 것 중 가장 나중에 필요한 제품의 콘센트 뽑기 (그리디) 풀이 onPlug: 현재 콘센트에 꼽혀있는 제품 set rest: 각 제품별 남은 순서를 저장하는 dictio.. 2021. 9. 12.
[Python] Baekjoon - 1080. 행렬 백준 1080번 행렬 문제는 0과 1로만 이루어진 두 개의 3x3 행렬을 최소 몇 번의 뒤집는 연산으로 같게 만드는지 최소 횟수를 구하는 문제다. 그리디 알고리즘을 이용해 해결할 수 있으며 난이도는 실버 2이다. 백준 1080번 행렬 문제 정보 알고리즘 분류 그리디 알고리즘 난이도 실버 2 행렬 문제 요약 0과 1로만 이루어진 MxN 행렬 A와 B 연산: 행렬의 3x3만큼을 뒤집는 것 (0은 1로, 1은 0으로) A를 B로 만들기 위한 최소 연산 횟수 구하기 문제 풀이 방법 과정 뒤집기 연산이기 때문에 연산의 '순서'는 상관없으며, 같은 곳을 두 번 이상 뒤집을 필요 없음 따라서 각 칸에대해 연산을 수행할지 말지 정하면 됨 왼쪽 위부터 순서대로 연산 필요 여부를 판단한다면, 3x3중 왼쪽 위칸만 확인하고.. 2021. 9. 11.
반응형

티스토리툴바