전체 글

https://school.programmers.co.kr/learn/courses/30/lessons/131704# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 컨테이너 벨트는 순차적으로 흘러가며, 임시 컨테이너 벨트는 stack의 형태로 이루어져 있다.order 배열에 값은 택배 기사가 임의로 정하며컨테이너 벨트와 임시 컨테이너 벨트에서 order의 형태로 값을 뽑지 못한다면 택배 상자를 옮기지 않는다. 따라서 임시 컨테이너는 stack이나 vector를 사용해 구현한다.또한, 컨테이너는 순차적으로 흘러가므로 for문을 사용해 구현했다.i값이 order..

https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 이 문제는 queue를 사용하면 해결 할 수 있다. 큐 자료구조를 통해 현재 다리를 건너는 트럭들을 담아둔다.queue에는 현재 다리를 건너는 트럭의 무게와 다리를 건너는데 필요한 시간을 담는다.또한, 현재 다리를 건너고 있는 트럭들의 총 무게를 저장한다.queue> q; // 트력 무게, 시간q.push({truck_weights[0], bridge_length});answer = 1;now = t..

https://school.programmers.co.kr/learn/courses/30/lessons/77885 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 이 문제는 비트 연산의 특징을 사용한다.정수 x에 대해 f(x)의 결과가 x보다 크고 비트가 1~2개 다른 수 중 가장 작은 수를 찾아야한다. f(x) 함수의 특징은 홀수와 짝수인 경우 분리되어 나타난다. 먼저 짝수인 경우, 마지막 비트가 0인 수이다.따라서 짝수인 경우에 가장 작은 수는 마지막 비트를 1 올리면 된다. // 짝수의 경우 n + 1// 2 -> 3, 4 -> 5if(x % 2 == 0..

https://www.acmicpc.net/problem/9466 DFS를 사용해 순환하는 그래프인지 확인하는 것이다. 입력을 통해 다음 노드를 알 수 있고처음 DFS함수를 호출한 값으로 돌아가야 circle 형태가 된다. 따라서 next 값이 방문하지 않은 node인 경우 DFS를 수행하게 된다. 이미 이전에 방문한 노드인 경우사이클을 형성하였는지 확인해야한다. 사이클 형성을 확인하는 방법은 done배열을 사용한다.done값이 아직 false인 경우 사이클 확인 여부를 검사하지 않은 것이다.따라서 자기 자신을 포함해 이동할 수 있는 모든 노드의 개수를 구하면 사이클인 노드의 개수를 구할 수 있다. 방문한 노드들은 done 배열에 true로 체크하여 사이클 여부를 확인하지 않도록 한다. 따라서 1번노드에..

https://www.acmicpc.net/problem/12015 이 문제는 이진 탐색 알고리즘을 사용하여 해결하였다. 이진 탐색을 사용해야하는 이유는 N의 최대가 1000000이므로DP를 사용 시 2중 반복을 사용해야하기 때문에 10^12가 되므로 1초를 초과하게 된다. 따라서 이진 탐색을 사용해 부분 수열의 길이를 구해야한다. 초기 A[0]를 result 배열에 삽입한다.이후 1부터 N까지 반복을 진행한다.result 배열에 최근에 넣은 값과 A[i]와의 값 비교를 통해A[i]가 더 큰 경우 부분 수열의 후보군에 해당하므로 result 배열에 삽입한다.하지만 A[i]가 작거나 같은 경우 이진 탐색을 통해 A[i]가 들어갈 위치를 찾게된다.  아래는 알고리즘을 구할 때 도움이 된 블로그 글이다.htt..

https://www.acmicpc.net/problem/1520 이 문제는 DFS와 DP를 혼합하여 접근해야한다.DP를 사용해야하는 이유는 단순히 DFS만을 사용해 길을 찾게된다면(N, M)까지 가는 모든 경로를 탐색해야 하기 때문에 목적지에 갈 수 없는 경우 시간 초과가 발생할 수 있다. 따라서 DP를 사용해 목적지에서부터 (0, 0)까지 경로를 저장하면 시간 내에 구할 수 있다. 처음 (0, 0)에서 상, 하, 좌, 우로 움직이며이동할 칸의 값이 작다면 이동 가능한 칸으로 판단한다.이동이 가능하다면 dp[0][0]에 이동 가능한 칸에 대한 경로를 모두 저장하게 된다. 따라서 dp[0][0]이 반환하는 값은 (0, 0)에서 (N, M)까지 갈 수 있는 모든 경로의 수를 저장하게 된다. #include..

https://www.acmicpc.net/problem/11054 바이토닉 부분 수열은 DP를 사용해 구할 수 있다.바이토닉 부분 수열을 살펴보면 증가하는 수열 부분과 감소하는 수열 부분이 있다는 것을 알 수 있다.이는 A[i]까지 증가하는 부분 수열과 A[i]부터 감소하는 부분 수열을 구하면 된다는 것을 알 수 있다. A[i]까지 증가하는 부분 수열은 다음과 같이 구한다.// 증가하는 수열 중 가장 긴 것 for(int i = 0;i 초기 A[i]인 경우 부분 수열의 길이는 1이 되므로 dp[i]를 1로 초기화한다.이후 0번째 인덱스부터 i 번째 인덱스까지 A배열에 존재하는 값을 비교한다.A[i] 기준으로 이전에 존재하는 값들이 작고dp[i]의 값이 이전에 존재한는 값들의 dp보다 작은 경우dp..

https://www.acmicpc.net/problem/1806 투포인터를 사용하는 문제이다.초기 문제를 분석할 때 투포인터를 사용해야한다는 것을 알 수 있었다. 10 155 1 3 5 10 7 4 9 2 8 위 숫자가 주어질 때 15를 만들기 위해서는 5와 10을 사용하면 최소의 개수로 15라는 값을 만들 수 있다. 이는 투포인터를 사용해 0번째 인덱스부터 N-1 번째 인덱스까지 부분합을 구하면 알 수 있다.즉, 초기 0번째 인덱스의 값이 5이므로 15보다 작게된다. 그러면 1을 더한다.그후, 3 5, 10까지 더햇다면 24가 되므로 목표 값인 15를 초과하게 된다.그러면 24에서 5를 뺸 값을 확인한다. 확인 결과 목표 값을 초과하므로 1, 3을 순차적으로 뺸다.최종적으로 5 + 10을 통해 15를..