포도밭 개발자

삽입정렬은 현재원소를 앞의 원소들과 비교해가며, 적절한 위치에 삽입하는 정렬기법입니다. for문과 while 문을 중첩하기에 O(N^2)의 시간복잡도를 가집니다. C++ 소스 코드 #include using namespace std; int main(){ int nums[] = {3,6,1,2,9,7,4,5,10,8}; for(int i=0;i=0 && nums[j]>nums[j+1]){ int temp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp; j--; } } for(int i=0;i nums[j+1] { let temp = nums[j] nums[j] = nums[j+1] nums[j+1] = temp j-=1 } } for num in nums { pr..

https://www.acmicpc.net/problem/2008 2008번: 사다리 게임 사다리 게임을 할 때 사용되는 사다리가 있다. 세로선은 N개가 있고, 가로선은 M개가 있다. 세로선은 맨 왼쪽 것부터 1, 2, …, N의 번호가, 가로선은 맨 위의 것부터 1, 2, …, M으로 번호가 붙어 있�� www.acmicpc.net C++ 소스 코드 #include #include using namespace std; int a[501]; //a[i] = 위에서 i 번째 높이에 있는 가로선 int d[501][501]; // d[i][j] = i번째 가로선까지 고려했을때, start에서 j까지 가는 최소비용 int main() { ios_base::sync_with_stdio(0); cin.tie(0)..

선택정렬은 원소의 갯수만큼 루프를 수행하면서, 제일 작은 수를 선택하여 해당 루프의 맨 앞으로 보내는 정렬기법입니다. for 루프를 두 번 중첩하기에 O(N^2)의 시간복잡도를 가집니다. C++ 소스 코드 #include using namespace std; int main(){ int nums[] = {3,6,1,2,9,7,4,5,10,8}; for(int i=0;i

programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 �� programmers.co.kr C++ 소스 코드 #include #include using namespace std; vector solution(vector progresses, vector speeds) { vector answer; vector days; for(int i=0;i

https://www.acmicpc.net/problem/12872 12872번: 플레이리스트 첫째 줄에 수빈이가 만들 수 있는 플레이리스트의 경우의 수를 출력한다. 경우의 수가 매우 커질 수 있기 때문에, 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 길이가 p인 플레이리스트를 만드는 경우의 수를 구하는 다이나믹 프로그래밍 문제입니다. X는 현재까지 플레이 리스트에 담긴 곡의 수, Y는 아직 플레이 리스트에 담기지 않은 곡의 수로, X+Y는 항상 N이기에 메모리제이션에는 현재 플레이리스트의 길이 p와 담은 곡의 수 x만 사용하였습니다. C++ 소스 코드 #include #include #define MOD 1000000007 using namespace std; lon..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 이전에 재귀를 이용해 풀었는데, 이번엔 조합을 이용해 풀어보았습니다. 치킨집을 저장한 벡터 자체를 사용하면 시간초과 문제가 있어서 check 벡터를 만들어 next_permutation에 사용하였습니다. #include #include #include #include using namespace std; int n,m,ans = 1e9; vector chi; //치킨집 위치 ..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 시작점에서 가중치가 0 또는 1인 방들을 지나면서 도착점에 도달하는 최소비용을 구하는 문제입니다. 한 점에서 다른 점으로 가는 최소 비용을 구하는 다익스트라 알고리즘을 사용하여 최소 비용을 갱신하여 풀이했습니다. C++ 소스 코드 #include #include #include #define INF 98765 using namespace std; int n,m; int dis..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net C++ 소스 코드 #include #include using namespace std; int n,m,h,len,ans = -1; int garo[100][100]; // 가로선 정보 저장 vector a; // 가로선 후보 위치 int start(int c){ // 출발점 c에서 c로 도착할 수 있는지 체크 int r = 1; while(r