본문 바로가기

공부-코딩테스트72

DP 동적계획법 메모리 공간은 더 쓰지만 연산 속도 향상에 쓸 수 있는 기법 이미 계산된 결과를 메모리에 저장, 다시 계산하지 않도록 한다. 큰 문제를 해결하는데 작은문제를 먼저 해결하고 이러한 결과가 모여 문제를 해결해야 할 때 다른 경우의 수에서도 이전에 사용한 결과를 활용해야 할 때 DP는 구현하는데 사용하는 코드가 어렵다기 보다는 개념이 어려운 문제라고 생각한다. DP문제를 풀면서 실수했던 것이나 접근법 등을 정리해서 되새기는 것이 중요하다고 생각했다. 실수했던 문제 12865 평범한 배낭 무게가 W일 때 for문에서 W부터 시작한다면 W*2가 최대 무게보다 작다면 중복으로 계산하게 된다. 최대무게에서부터 먼저 접근하고 감소하는 형태로 구현해야 중복되는 경우가 없다. 해결한 코드 2023. 1. 17.
heapq import heapq heapq.heappush(리스트,값) heapq.heappop(리스트) 기본적으로 최솟값이 리스트[0]에 위치해 있는 자료구조이다. 완전이진트리를 구성하며 삽입, 삭제 모두 시간복잡도가 log(N)을 따르는 엄청난 성능을 자랑한다. push를 통해 값을 넣은 다음 pop을 하면 리스트 내의 가장 작은 값이 나오게 된다. 여러 값들 중에서 최소, 최대 값을 제거해야 하는 기능이 필요할 때 사용할 수 있을 것이다. 관련 문제 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 2022. 12. 12.
LIS문제 -DP LIS문제: 최장 증가 부분 수열 배열의 일부분을 순서대로 추출했을 때 크기가 커지는 배열들의 집합 중에서 가장 길이가 긴 수열 찾기 문제의 답은 여러개가 될 수 있다. [8, 2, 6, 5, 4, 9, 2, 7, 5, 1] 배열이 있다면 [2, 4, 9] 배열은 정답 후보에 있을 수 있다. 생각해보면 커지는 것을 발견하면 선택하는 식으로 해결한다면? [1,2,9, ~~~] 에서 9를 선택했는데 ~~~부분이 3,4,5,6,7 이렇게 더 긴 조합을 생성할 수 있으므로 유의해야 한다. DP [8, 2, 6, 5, 4, 9, 2, 7, 5, 1] 8이 배열의 마지막인 배열들 중 가장 길이가 긴 것은 [8] 하나밖에 없다. [8, 2, 6, 5, 4, 9, 2, 7, 5, 1] 2가 배열의 마지막인 부분배열들 .. 2022. 10. 6.
BFS DFS 자바코드 가장 기초적인 BFS,DFS 알고리즘이 빠져있었다. 오랜만에 봤는데 기억이 잘 안나서 설명보단 코드를 기재한다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; public class BFS_DFS { static int[][] map; static boolean[] visit; static int N = 7; static int[] edge(int a,int b) { int[] re = {a,b}; return re; } public static void main(String[] args) { map = new int[7][7]; ArrayList edge = new ArrayList(); edge.add(.. 2022. 9. 30.
벨만 포드, 다익스트라, 프로이드 워샬 알고리즘 벨만 포드 알고리즘 다익스트라 문제처럼 한 지점에서 다른 지점까지의 최단 경로들을 구할 때 사용하는 알고리즘 다익스트라와 차이점은 가중치에 음수가 있는 경우에는 다익스트라를 쓰면 안되므로 벨만 포드 알고리즘을 쓴다. 다익스트라보다 구현은 훨씬 쉽다. 단순하게 (노드수-1)번만큼 반복하는데 반복하는 일은 다음과 같다. 방문한 노드에서 뻗어나오는 간선들을 통해서 최단경로가 갱신되는지 연산 시작하는 노드는 방문한 노드라고 처음에 설정하고 시작한다. 모든 간선을 확인할 필요는 없고 방문했던 노드와 연관된 간선들만 확인하면 되긴 하다. 벨만 포드 알고리즘 자체라고 생각하는 문제는 백준의 타임머신 문제이다. 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ .. 2022. 9. 28.
19238. 스타트 택시 (백준, 자바) 문제 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 1. 단순히 테이블 상에서 가장 가까운 손님을 찾는다. 2. 손님의 목적지까지 데려다준다. 손님을 다 태워줄때까지 반복하면 되는 문제이다. BFS를 사용해서 가까운 손님(거리가 같으면 행,열 조건에 맞게 행렬 비교)을 찾고, 목적지까지 태워주는 대신 연료량을 체크하면 되는 문제 조건은 간단하나 두가지 문제가 있어 시간이 많이 걸리게 되었다. 시간초과 손님을 목적지까지 바래다 주자마자 다음 손님이 위치해 있는 경우 .. 2022. 9. 18.

티스토리툴바