알고리즘 💻/요약정리

[Python] 2차원 배열 돌리기

2차원 배열 돌리기는 직접 구현하거나, zip을 이용하여 간편하게 바꾸는 2가지 방법이 있습니다. 1. 직접 구현하기 [[1, 2, 3], [4, 5, 6], [7, 8, 9]] 와 같은 배열을 한 번 돌리면, [[7, 4, 1], [8, 5, 2], [9, 6, 3]] 와 같은 결과를 얻을 수 있습니다. 180, 270도 회전을 원하면 rotate 함수를 여러 번 호출하면 됩니다. def rotate(graph): n = len(graph) m = len(graph[0]) result = [[0]* n for _ in range(m)] for i in range(n): for j in range(m): result[i][j] = graph[n-1-j][i] return result # [[7, 4, 1..

[백트래킹] 조합, 순열, 중복조합, 중복순열 (재귀이용)

목차 조합 순열 중복조합 중복순열 들어가며 백준에서 백트래킹 문제를 풀 때, 문제보고 대충 이런 식이면 되겠지 하고 문제들을 풀다 보니 헷갈리는 부분이 있었습니다. 그동안 머릿속에 정리된 내용 없이 중구난방으로 문제를 풀었는데, 정리된 내용이 없나 하고 찾아보다가 얍문님의 블로그 포스팅을 보고 이거다 싶어서 하나로 정리해두려고 합니다. 조합 조합이란? 서로 다른 n개의 원소를 가지는 어떤 집합에서 순서에 상관없이 r개의 원소를 선택하는 것을 의미합니다. 가장 중요한 것은 순서가 상관없다는 점입니다. 예를 들어 {1, 2, 3, 4, 5}로 이루어진 집합이 있을 때, 3개를 선택한다고 해봅시다. 이때 {1, 2, 3}과 {3, 2, 1}은 같은 부분집합입니다. 즉, {1, 2, 3} , {1, 2, 4},..

정렬 알고리즘 요약정리

정렬 알고리즘의 분류 - 정렬 방식으로 분류 Comparison 방식은 숫자끼리 비교하고, Distribution 방식은 자기가 자리를 알고 들어간다. Comparison (숫자끼리 비교) : 퀵 정렬, 삽입 정렬, 버블 정렬, 선택 정렬, 합병 정렬, 힙 정렬, 쉘 정렬 Distribution (자기가 자리를 알고 들어감) : 카운팅 정렬, 버킷 정렬, 기수 정렬 - Stable or Non-stable 순서가 유지되는지 여부에 따라 분류 Stable : 버블 정렬, 삽입 정렬, 합병 정렬, 카운팅 정렬 Non-stable : 교환 정렬, 퀵 정렬, 선택 정렬, 힙 정렬 - 제자리 정렬 or 다른 공간을 이용해서 정렬 In-place : not in-place : 카운팅 정렬, 기수 정렬, 버킷 정렬,..

[Algorithm] 백트래킹(Backtracking)

백트래킹이란 ? 백트래킹은 모든 경우의 수를 고려하는 알고리즘을 의미합니다. 트리 형태의 상태공간이 있을 때, DFS와 같은 완전탐색 알고리즘을 사용하여 모든 지점을 탐색하게 됩니다. DFS는 현재 지점에서 방문할 곳이 있으면 재귀를 호출하여 계속해서 이동하는 특징이 있습니다. 하지만, DFS는 모든 곳을 방문하기 때문에 비효율적인 측면이 있습니다. 따라서 목표지점이 될 가능성이 있는지를 검사한 후 그 지점들만 방문하는 것을 백트래킹 알고리즘이라 합니다. 즉, 백트래킹은 DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 효율적으로 찾는 알고리즘 입니다. 백트래킹과 DFS의 차이점? 백트래킹과 DFS의 차이점을 많이 헷갈려하시는데, ..

[Algorithm] 벡터(Vector)

1. 벡터 선언 //원소 1개 벡터 선언 vector v1; //원소 2개 벡터 선언 vector v2; //원소 3개 벡터 선언 vector v3; v1.push_back(2); v2.push_back(pair(3000,"김밥")); v.push_back(pair(6000,pair("돈가스",1))); //출력할 때 cout

[Algorithm] 맵(Map)

Map은 자동으로 정렬되며, 중복을 허용하지 않는 자료구조이다. 1. Map 선언 #include map m; 2. Map 삽입 //1번 방법 m.insert(pair(9,"hello")); //2번 방법 m.insert({9,"hello"}); //대입하는 방법 m[9]="hello"; 3. Key값을 이용해 Value값 찾기 //map의 key값으로 접근 coutfirst; } }