개발자 지망생의 끄적끄적 개발기록

백준 12865 : 평범한 배낭 등급 : Gold V 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 사용 알고리즘 : Dynamic Programming 사용 자료구조 : Vector 고전적인 다이나믹 프로그래밍 문제, 0-1 배낭(Knapsack) 문제이다. 배낭 하나에 가치가 최대가 되도록 물건을 넣는 문제. 배열에 물건의 무게와 가치를 저장하고, 그에 따른 DP테이블을 생성한다. 0번 인..

백준 1083 : 소트 등급 : Gold IV 1083번: 소트 (acmicpc.net) 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전 www.acmicpc.net 사용 알고리즘 : Greedy 사용 자료구조 : Vector 버블 소트(Bubble Sort)의 원리와, 이를 그리디적으로 활용하는 문제였다. 위와 같은 배열에 17번까지 SWAP이 가능하다고 해 보자. 이때, 17번 안에 10을 버블 소트로 가장 앞까지 가져올 수 있으므로 이를 진행해준다. 진행 하면서 버블 소트는 총 9번이 일어났으며, 1이 있던 위치에 10이 들어간..

백준 16946 : 벽 부수고 이동하기 4 등급 : Gold II 16946번: 벽 부수고 이동하기 4 (acmicpc.net) 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 사용 알고리즘 : DFS 사용 자료구조 : Vector 벽의 위치에서 벽을 부수고 이동할 수 있는 공간을 구하는 문제. 주어진 그래프가 있을 때, 영역 별 크기의 합을 미리 구하고, 벽과 인접한 영역들의 값을 더해주는 방법으로 풀이 가능. 이때 인접한 곳은 상하좌우로 확인하는데, 그림과 같이 중복되는 경우에 두 번 ..

백준 9252 : LCS 2 등급 : Gold IV 9252번: LCS 2 (acmicpc.net) 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 사용 알고리즘 : Dynamic Programming 사용 자료구조 : - 다이나믹 프로그래밍으로 풀 수 있는 고전적인 문제이다. 배열의 가장 첫 부분을 비우고, 두 글자가 같은 부분이 나오면, 이전까지 같은 부분이 있었는지 확인해 + 1을 해준다. → str1[i] == str2[j]이면, dp[i][j] = dp..

백준 1806 : 부분합 등급 : Gold IV 1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 사용 알고리즘 : Two Pointer 사용 자료구조 : Vector 정렬되지 않은 배열에서의 합의 길이가 최소가 되는 길이를 구하는 문제이다. Sum이 Target보다 크거나 같으면 Left를 늘려주고, Sum이 Target보다 작으면 Right를 늘려주는 방식으로 풀 수 있다. 1. n값과 s값, n에 따른 배열 값을 입력받음. 2. left, righ..