Coding

    [백준][C] 1197-최소 스패닝 트리/Kruskal/MST/크루스칼
    Coding/BOJ[C]

    [백준][C] 1197-최소 스패닝 트리/Kruskal/MST/크루스칼

    https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 🍕 느낀점 별다른 어려움 없이 크루스칼 뼈대코드만 잘 작성하면 쉬운 문제! 계속 틀렸습니다가 떠서 시간을 많이 잡아먹었었는데 알고보니까 qsort함수의 두번째 매개변수로 edge의 배열 개수가 아닌 vertex의 정점 개수를 넣어서 제대로 sorting이 안됐던거였다. 이런 실수는 그만....! 🍔 코드 [C언어]

    [C/C++] 완전탐색 Brute Force 개념 정리
    Coding/Algorithm

    [C/C++] 완전탐색 Brute Force 개념 정리

    완전탐색(Brute Force) 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하며 답을 찾는 방법 Brute Force 라고도 부르는데, 뜻은 무식하게 푼다! 완전탐색은 알고리즘이 아닌, 문제를 푸는 방법이라고 할 수 있다. 완전 탐색 기법 1. 단순 Brute Force if문이나 for문을 사용해 모든 case를 탐색하는 방법 2. Bit-mask 모든 경우의 수가 각각의 원소에 포함되거나 포함되지 않는 두 가지 선택으로 구성되는 경우 용이하다. 이를 통해 집합을 정수로 나타내거나 집합의 모든 부분집합을 정수로 표현할 수 있다. {1, 2, 3, 4, 5} -> 1 1 1 1 1 -> 31 {1, 2, 3, 4} -> 1 1 1 1 0 {2, 3, 5} -> 0 1 1 0 1 {..

    [백준][C] 1062-가르침/Brute Force/브루트 포스/비트 마스킹/조합/재귀/백트래킹/DFS
    Coding/BOJ[C]

    [백준][C] 1062-가르침/Brute Force/브루트 포스/비트 마스킹/조합/재귀/백트래킹/DFS

    https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 🗺 시도 브루트포스와 관련된 문제를 연습하기위해 1062번 문제를 풀어보았다. abc를 알던, bca를 알던 읽을 수 있는 단어는 같기 때문에 조합을 사용해야겠다는 생각이 들었다. 더보기 //조합 Combination #include int n = 4, r = 3; //4개 중에서 3개 뽑기 (순서상관없이) int check[4]; int result[3]; //결과를 담을 배열 int a..

    [C/C++] DFS/BFS 개념정리
    Coding/Algorithm

    [C/C++] DFS/BFS 개념정리

    BFS/DFS ⭐DFS 깊이 우선 탐색 정의 : 한 경로의 끝까지 최대한 깊숙히 탐색하다가 그 다음 경로로 이동한다. 장점 : 현재 경로의 노드만 기억하면 됨 -> 저장공간이 많이 필요하지않다. 단점 : 목표 노드까지 도달한 경로가 최단 경로라는 보장이 없다. 해가 없는 경로인 경우 : 끝까지 탐색하기 때문에 미리 정해둔 임의의 깊이까지만 탐색하고 해를 발견하지 못하면 가장 최근의 부모 노드로 돌아가는 백트래킹(Back Tracking) 을 이용해 다른 경로를 선택하여 진행한다. 구현 : 재귀 / 스택(stack) 의사 코드 Dfs(G, v): 스택 s를 생성한다. s.push(v) while (not is_empty(s)) do v = s.pop() if(v가 방문되지 않았으면) v를 방문되었다고 표시..

    [백준][C] 1260-DFS와 BFS/인접리스트/그래프/깊이우선탐색/넓이우선탐색
    Coding/BOJ[C]

    [백준][C] 1260-DFS와 BFS/인접리스트/그래프/깊이우선탐색/넓이우선탐색

    [1260-DFS와 BFS] https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 👀문제풀이 시 유의해야 할 점 정점 번호가 작은 것부터 방문한다 -> 인접리스트에 정접을 삽입할 때 오름차순으로 정렬하며 삽입해야 한다! 💻코드 //1260-DFS와 BFS #include #include #define MAX_VERTICES 1001 #define TRUE 1; #define FALSE 0; int visited[..

    [백준][C] 1158-요세푸스/연결리스트/이중연결리스트/LinkedList
    Coding/BOJ[C]

    [백준][C] 1158-요세푸스/연결리스트/이중연결리스트/LinkedList

    [1158] : 요세푸스 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 🤢고난과 역경 나는 연결 리스트를 복습하기 위해 이 문제를 시도해보았다. 처음에는 원형리스트로 구현해보았지만, 너무 코드가 복잡해져 반례가 계속 계속 나타났고... 굉장히 비효율적인 코드 때문에 시간 초과까지 나왔다. 심지어 내 코드는 나도 못 알아볼 정도로 복잡하고 쓰레기였다..! 그래서 이중연결리스트로 바꿔보았고 이 문제에서는 시작 지점이 매번 바뀌어야 하니 head와 tail을 전역 변수로 두고 시작 위치를 head에 저장하며 delete 함수를 작성했다. ..

티스토리툴바