'자료구조와 알고리즘/알고리즘' 카테고리의 글 목록

소수 빠르게 찾기, sqrt (), 에라토스테네스의 체 + pow()

2022.01.09

공략법 : TargetNum이 소수인지 아닌지 확인하고 싶다면, (1) TargetNum의 sqrt ()로 제곱근을 구하여 약수를 2부터 루트TargetNum까지만 검토한다. (2) 에라토스테네스의 체 개념을 이용하여 for문을 돌면서 특정 i의 배수를 전부 지워나간다. (1) 제곱근까지 약수 범위를 줄인 경우 -> 정상적으로 소수가 출력됨 #include #include using namespace std; bool isPrimeNumber(int x) { int end = (int)sqrt(x); for (int i = 2; i

자료구조와 알고리즘/알고리즘

이진탐색 핵심코드

2022.01.04

재귀를 활용한 이진탐색의 핵심 개념이 되는 코드 def Search(start,end,target): if start==end: //~~ return mid = (start+end)/2 if nums[mid]

자료구조와 알고리즘/알고리즘

BFS 코드

2021.12.27

bfs 함수에서는 (1) push()하자마자 check=true로 만들어주고 (2) 큐가 비어있지 않는 한 계속 반복할때마다 front()를 pop() 해주는 것이 꽤나 중요해보인다. 그러다보니 첫노드는 그야말로 큐에 들어가자마자(push) 빠져나오게(pop)게 된다. main 함수에서는 차분하게 인접리스트를 구현해야한다. #include #include #include using namespace std; vector numbers[7]; int check[7]; void bfs(int start) { queue que; que.push(start); check[start] = true; while (!que.empty()) { int x =que.front(); que.pop(); cout

자료구조와 알고리즘/알고리즘

배열 회전, 정적 배열 내에서 특정 원소를 선택한 위치로 이동하고 싶을 때

2021.12.15

배열 정보와 인덱스 정보가 두개가 필요하다. 특정 원소의 원래 인덱스와 원소를 보내고 싶은 위치의 인덱스이다. 그리고 두 인덱스 사이를 for문으로 돌면서 배열을 한칸씩 당겨줘야하는 다소 번거로운 작업이 필요하다. 아래 코드는 8번째 숫자를 2번째 위치로 보내고 싶다고 가정하고 작성한 것이다. #include #include using namespace std; void ratate(array& arr, int wantPos, int target) { int last = arr[t]; for (int i = t; i > s; i--) { arr[i] = arr[i-1]; } arr[s] = last; } int main() { array arr = {1,2,3,4,5,6,7,8,9,10}; ratate(..

자료구조와 알고리즘/알고리즘

[c++] 삽입 정렬

2021.09.21

삽입 정렬이란 숫자를 원하는 위치를 찾아가서 삽입하는 정렬이다. 필요한 만큼만 움직여서 시간 복잡도는 n의 제곱이라는 점에서 동일할지라도 연산수가 적으므로 버블 정렬이나 선택 정렬보다 빠르다. 2 6 4 9 8 1 3 5 7 라는 9개의 숫자를 한 배열에 담고 삽입 정렬을 활용해 오름차순으로 바꾸는 시뮬레이션을 해보자. 제일 앞 숫자를 0번째 인덱스, 마지막 숫자를 8번째 인덱스라 가정한다. 2 6 4 9 8 1 3 5 7 //2 6 -> 4->2 모두 반복문으로 비교하다가 맨 앞 정착 ) 1 2 4 6 8 9 3 5 7 //현재 상황(불완전하지만 정렬이 차츰 되고 있음) 1 2 _ 4 6 8 9 '3' 5 7 //3을 4 앞에 넣자. (9-> 8-> 6-> 4 모두 반복문으로 비교하다가 4 앞 정착) ..

자료구조와 알고리즘/알고리즘

[c++] 버블정렬

2021.09.21

버블 정렬이랑 옆에 있는 값과 비교해서 위치를 바꿔주는 정렬 방법이다. 선택 정렬은 제일 작은 값을 찾아서 앞에 가져다 놓는 식으로 전개된다면, (선택 정렬 설명 링크: c++ 선택 정렬 활용해서 배열 속 숫자들을 오름차순으로 바꾸기 (tistory.com)) 버블 정렬은 제일 큰 값을 점차 뒤로 유배보내는 식으로 전개된다. 왜냐하면 첫 배열값부터 일관되게 바로 옆(뒤)에 있는 배열값과 비교해서 큰 값은 뒤로 물러나도록 스위치를 반복하기 때문이다. 2 6 4 9 8 1 3 5 7 라는 9개의 숫자를 한 배열에 담고 버블 정렬을 활용해 오름차순으로 바꾸는 시뮬레이션을 해보자. 제일 앞 숫자를 0번째 인덱스, 마지막 숫자를 8번째 인덱스라 가정한다. 2 6 4 9 8 1 3 5 7 //2와 6을 비교한다. ..

자료구조와 알고리즘/알고리즘

[c++] [선택 정렬] 활용해서 배열 속 숫자들을 오름차순으로 바꾸기

2021.09.20

선택 정렬 2 6 4 9 8 1 3 5 7 라는 숫자를 선택 정렬을 활용해 오름차순으로 바꾸면 다음과 같다. 제일 앞 숫자를 0번째 인덱스, 마지막 숫자를 8번째 인덱스라고 가정을 한다면, 2 6 4 9 8 1 3 5 7 //0번째 인텍스부터 끝까지 확인하고 (1발견) 1 2 6 4 9 8 3 5 7 //(1을 제일 앞으로) 1 2 6 4 9 8 3 5 7 //1번째 인텍스부터 끝까지 확인하고(2발견, 그대로) 1 2 6 4 9 8 3 5 7 //2번째 인텍스부터 끝까지 확인하고(3발견) 1 2 3 6 4 9 8 5 7 //(3을 앞으로) 1 2 3 6 4 9 8 5 7 //3번째 인텍스부터 끝까지 확인하고(4발견) 1 2 3 4 6 9 8 5 7 //(4를 앞으로) 1 2 3 4 6 9 8 5 7 //..

자료구조와 알고리즘/알고리즘

c++ 배열 오름차순 내림차순 구현

2021.09.20

배열 속에 여러 값이 뒤죽박죽 섞여 있을 때, 이것들이 오름차순(작은 값이 가장 앞에 오고 배열 뒷 인덱스로 갈수록 인덱스 값이 커짐)으로 정렬되도록 이중포문을 써서 직접 하드코딩으로 구현해보았다. 각종 정렬 기법을 배우고 나면 코드가 달라질 것이다. #include using namespace std; int main() { int num[10] = { 986,4,7,12,45,895,3,7,34,5 }; for (int i =0; i+1

자료구조와 알고리즘/알고리즘

2. [c++] 특정값 이하의 수 중에서 가장 큰 2의 거듭제곱만 반환하는 함수만들기

2021.09.18

*직접 짠 것임으로 목적에 보다 더 최적인 함수가 존재할 수 있습니다.* - 특정값 n을 자유롭게 입력하면, - n 이하의 수 중에서 가장 큰 2의 거듭제곱만을 반환하는 함수를 만들어보았다. 예시) 100입력시 64 출력 2입력시 2출력 1입력시 1출력 #include using namespace std; int func(int* n) { int max =1; for (int i = 1; i * 2 > n; while (n > n; } int* a = &n; n = func(a); cout

자료구조와 알고리즘/알고리즘

깊이 우선 탐색(DFS, Depth First Search), 너비 우선 탐색(BFS, Breadth First Search))

2021.05.16

BFS, DFS란 그래프의 탐색 기법으로 목적은 임의의 한 정점에서 시작하여 모든 정점을 방문하는 데 있다. 깊이 우선 탐색 - DFS(Depth-first search) 자식 노드를 우선적으로 탐색 즉, 아직 방문되지 않은 인접 노드(자식 노드)를 우선적으로 탐색 깊이 우선 탐색은 한쪽만 죽어라 파다가 더이상 팔 곳이 없으면 다시 돌아와서 다른 한쪽을 죽어라 파는 형식이다. 깊이 우선 탐색은 Stack을 통해 구현된다. 너비 우선 탐색 - BFS(Breadth-first search)=레벨 순회(level-order traversal) 코드링크 : BFS 코드 (tistory.com) 간선의 모든 가중치가 같을 때, 최단 거리를 구하는 알고리즘으로 시작 정점을 기준으로 가까운 정점을 먼저 방문한다. 방..

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

자료구조와 알고리즘/알고리즘

소수 빠르게 찾기, sqrt (), 에라토스테네스의 체 + pow()

이진탐색 핵심코드

BFS 코드

배열 회전, 정적 배열 내에서 특정 원소를 선택한 위치로 이동하고 싶을 때

[c++] 삽입 정렬

[c++] 버블정렬

[c++] [선택 정렬] 활용해서 배열 속 숫자들을 오름차순으로 바꾸기

c++ 배열 오름차순 내림차순 구현

2. [c++] 특정값 이하의 수 중에서 가장 큰 2의 거듭제곱만 반환하는 함수만들기

깊이 우선 탐색(DFS, Depth First Search), 너비 우선 탐색(BFS, Breadth First Search))

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역