본문 바로가기

📊알고리즘112

[BOJ 1941] 소문난 칠공주 https://www.acmicpc.net/problem/1941 2차원 배열에서 연속된 것을 구한다는 점에서 bfs나 dfs로 구할 수 있을 것같다. 그러나 BFS와 DFS는 뻗어나가는 형식이기 때문에 이런 규칙이 적용되지 않는 경우는 찾기 힘들다. 그래서 이번 문제는 단순히 이차원 배열에서 인접한 것만 찾는 방법 대신 S가 Y보다 큰 조합을 뽑은 다음, 서로 인접해있는지 체크하는 방법을 사용해야한다. 따라서 이중 for문을 통해 이차원 탐색을 하는 대신, 일차원 배열에서 가능성있는지 탐구한다.예를 들어, 1번째 사람이 올 수 있는지 -> 2번째 사람이 올 수 있는지 -> ... -> 25번째 사람이 올 수 있는지이 과정에서 백트래킹을 이용해 여러 조합들을 뽑을 수 있다. 그렇기 때문에 아래와 같이 일.. 2023. 3. 28.
[연결리스트 ADT] 추가 기능 구현 2가지 방법 1. Head & Tail 사용하기 Head와 Tail을 사용하면 경우를 생각하지 않아도 된다. 왜냐하면, Tail의 존재로 인해 NULLPOINT가 생길 수 없다. 따라서, Head부터 순회를 하면서 IDX가 0이 되면, 그자리의 노드를 밀어내고 그자리에 새로운 노드를 넣으면 된다. 더보기 void Add(List* list,int r, char c) { Node* NewNode = (Node*)malloc(sizeof(Node)); NewNode->data = c; NewNode->next = NULL; NewNode->prev = NULL; Node* cur = list->Head; if (cur->next == list->Tail) { cur->next = NewNode; list->Tail->p.. 2023. 3. 26.
배열 채우기 알고리즘 지그재그 배열 https://codeup.kr/problem.php?id=1503 [ 출력 ] 1 2 3 4 5 10 9 8 7 6 11 12 13 14 15 20 19 18 17 16 21 22 23 24 25 배열 사용 안하기 더보기 #include int main() { int n,idx = 1; scanf("%d", &n); int i=0; int chk = 1; while (idx = idx; i--) { printf("%d ", i); } idx += n; } chk++; printf("\n"); } return 0; } 지그재그 배열2 [ 출력 ] 1 6 7 2 5 8 3 4 9 더보기 #include int main() { int n, m, idx = 1; int arr[101][101] .. 2023. 3. 11.
시간 복잡도 ✅본 강의는 쉬운코드의 시간복잡도 강의 영상을 정리한 글입니다! 강의 보러가기 실행 시간이란? : 함수/알고리즘 수행에 필요한 스텝(step) 수 ( 각 라인을 수행하기 위해 필요한 step수는 상수라고 가정 ) 각 라인의 cost * time한 값들을 더한다. 💡 T(N) = c1 + c2*(N+1) + c3*N + 1 = (c2 + c3)*N + c1 + c2 + 1 = a*N + b * N = size of inputs 여기서 N이 무한으로 갈 때의 시간이 궁금하다. N이 커질수록 덜 중요한 것은 제거하자. 따라서, 최고차항만 의미가 있다. ( 최고차항의 계수[a]와 b는 의미가 없음) a*N + b = O(N) 이를 점근적 분석이라고 한다. : 임의의 함수가 N→∞ 일 때 어떤 함수 형태에 근접해.. 2023. 1. 6.
BOJ 9184] 신나는 함수 실행 [ 다이나믹 프로그래밍 이란? ] - 이미 구한 값은 다시 구하지 않고 재사용! { DP에서의 가정 } 1. 큰 문제를 작은 문제로 나눌 수 있어야한다. 2. 작은 문제에서의 정답은 그 문제를 포함한 큰 문제에서도 동일해야한다. [ 접근법 ] 피보나치 수열 문제와 비슷하게 연산을 저장할 배열은 준비한다. 기존 코드 if (a 200){ returns w(20, 20, 20); } if (a < b && b < c){ return w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c); } else { return w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1); } 위 코드에서 우리는 연산을 저장해야 한다. -.. 2022. 12. 27.
BOJ 1021] 회전하는 큐 문제 바로가기 [ 접근 법 ] - 앞, 뒤로 push, pop이 가능하다는 점에서 deque를 사용하면 쉽게 접근할 수 있다. - 문제의 핵심은 언제 2번 혹은 3번을 진행하는지 판단해야한다는 것이다. {2번 혹은 3번 중 파악하기} - 먼저, 구하려는 수가 deque에서 몇 번째에 위치하는 지 파악해야한다. (deque에서 원하는 숫자를 pop하게 되면 길이가 바뀌기 때문) - for문을 통해 구하려는 값이 몇번에 있는지 구한다. - 만약 ( deque의 size - 구하려는 수의 위치 > 구하려는 수의 위치 )이면 3번보다 2번이 효율적이다. - 반대로 ( deque의 size - 구하려는 수의 위치 > n >> m; for (int i = 0; i > tmp; seq... 2022. 12. 23.

티스토리툴바