계단 오르기 2: 최대 동전 획득하기문제 링크 : https://www.codetree.ai/missions/2/problems/climbing-stairs-2/description계단을 오르면서 얻을 수 있는 동전의 최대 개수를 구하는 문제를 해결해보겠습니다. 이 문제는 다이나믹 프로그래밍(Dynamic Programming) 기법을 사용하여 해결할 수 있습니다.문제 설명남우는 n층 높이의 계단을 오르려고 합니다. 남우가 계단을 오르는 방식에는 몇 가지 제한이 있습니다:한 번에 1계단 혹은 2계단을 올라갈 수 있습니다.남우는 1계단 오르는 것을 좋아하지 않아서, 최대 3번까지만 1계단 오르는 행동을 할 수 있습니다.남우가 각 층을 밟을 때마다 해당 층에 있는 동전을 획득할 수 있습니다.계단의 마지막 층..

https://www.codetree.ai/training-field/frequent-problems/problems/battle-ground/description?page=3&pageSize=20%2F3340%2F3340 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 최고의 알고리즘 전문가들이 체계적인 코딩테스트 문제 유형 분류와 학습 커리큘럼을 제시합니다. 알고리즘 학습의 A to Z를 경험해보세요! www.codetree.ai 삼성의 대표적인 시뮬레이션 문제이다. 실수없이 주어진 요구사항에 맞추어 구현하면 되는 문제이다. 해당문제는 총의 정보를 계속해서 업데이트 해야하고, 각 칸마다 총이 여러개가 들어갈 수 있으므로 3차원 배열을 사용하여야 문제를 쉽게 풀수있다. 자세한 코드는 주석참고 n, m..

2023 삼성 코테를 보고와서 복기겸 다시 한번 풀어보았다. 문제는 코드트리에서 확인 가능하다. https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/description?page=3&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 최고의 알고리즘 전문가들이 체계적인 코딩테스트 문제 유형 분류와 학습 커리큘럼을 제시합니다. 알고리즘 학습의 A to Z를 경험해보세요! www.codetree.ai 해당 문제에서 주의해서 풀어야 하는점은 다음과 같다. 1. 공격자 포탑과 타겟 포탑을 선정하는 과정 해결방법 : sort를 이용하여 해결 2. 레이저 공격 과정 이부분이 시험장에서 조금 말썽을..

DFS : Depth First Search (깊이 우선 탐색) 시작 노드부터 시작하여 다음 Branch로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 모든 노드를 방문 하고자 하는 경우에 사용한다. 재귀함수를 이용하여 구현한다. 여기서 주의해야 할 점은 방문 여부를 반드시 검사해야 한다. 이러한 무방향 그래프를 1부터 시작해서 DFS로 탐색하겠다. #include #include using namespace std; bool visit[9]; vector node[9]; void dfs(int start_node) { visit[start_node] = true; cout

Queue Queue란? 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식이다. C++ 헤더파일 #include를 추가해준다. Queue 기본함수에는 push, pop, front, back, empty, swap이 있다. #include #include using namespace std; int main() { // queue 변수명으로 큐를 선언한다. queue q; // push를 하여 queue의 데이터를 추가한다. q.push(1); q.push(2); q.push(3); q.push(4); q.push(5); queue second_q; second_q.push(6); second_q.push(7);..

퀵 정렬은 분할 정복 알고리즘의 하나이다. 평균적으로 다른 정렬에 수행 속도가 빠른편이다. 분할정복 알고리즘은 문제를 2개로 분리하고 각각 해결한 후 그 해결 결과값을 모아서 원래의 문제를 해결하는 방식이다. 퀵 정렬의 과정은 다음과 같다. 리스트에서 임의의 원소를 고른다. 이 원소를 pivot이라 칭한다. pivot을 기준으로 좌측은 pivot보다 작은 수, 우측은 pivot 보다 큰 수가 오도록 서로 교환한다. 분할된 두 개의 리스트에 대해 재귀적으로 반복한다. '5,2,4,6,7,1,3' 를 퀵정렬 했을때 가장 좌측 5를 pivot으로 설정하고, 2을 left, 3을 right로 설정 left는 => 방향으로 이동하며 pivot보다 큰값 찾기, right는

선택정렬 (Selection sort)은 데이터 전체에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환하는 방식으로 정렬한다. 버블정렬은 인덱스를 이동하면서 교환이 필요하면 즉시 교환했다. 하지만 선택정렬은 두항을 비교하고 작은 값이 저장된 요소값이 아닌 그 배열의 인덱스를 따로 저장한다. 그리고 단계가 끝마칠때 단 한번만 교환한다. 5,1,3,4,2 선택정렬 (오름차순)으로 정렬하기! 1단계 5 [0] 1 [1] 3 [2] 4 [3] 2 [4] 선택된 항 = 0번째 인덱스 (현재 기준점 [0] ) 0번째 1번째항 비교, 값은 그대로 두고 기준점만 변경 현재 기준점이 ( [1] )로 변경됨 이후 기준점 [1] 을 기준으로 나머지 2,3,4번째 항을 비교함 이후 마지막으로 최초 기준인덱스였던 0번째 인..

버블 정렬(Bubble Sort)은 서로 연접한 두 항으 계속해 비교하는 방식이다. n번째 항이 있다고 가정할때 0번째 항과 1번째 항 비교, 1번 항 2번 항 비교, 2번 항 3번 항 비교해서 마지막 두항 n-1번 항 n 번항을 비교후 마지막 항의 정보가 결정된다. 오름차순으로 정렬할 경우 가장 큰값을 먼저 결정하는 특징이 있다. `3, 4 ,1 ,5 ,2` 를 버블정렬 해보겠다. 1단계 0번항 1번항 비교 (유지) 3 4 1 5 2 1번항과 2번항 비교 (교환) 3 1 4 5 2 2번항과 3번항 비교(유지) 3 1 4 5 2 3번항과 4번항 비교(교환) 3 1 4 2 5 1단계 완료 2단계 다시 0번항 1번항 비교 (교환) 3 1 4 2 5 1번항과 2번항 비교 (유지) 1 3 4 2 5 2번항과 3..