전체 글

전체 글

    [백준][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를 방문되었다고 표시..

    Git : 버전관리의 시작
    Upgrade/GitHub

    Git : 버전관리의 시작

    1. Git 버전관리 👀 1) 버전관리의 시작 git init git을 시작한다. .git이라는 저장소가 생긴다. .git? : git repositorygit init . 현재 디렉토리를 깃에게 버전관리를 시킨다. 2) 버전 생성 git status working tree의 status working tree? : 버전이 만들어지기 전 단계로 파일이 생성되고 수정된 후 아무것도 하지않은 상태git add add to staging area staging area? : working tree 에 있는 파일들 중 repository에 넣을 것들을 staging area에 올려놓는다.git commit create version : 버전으로 만들어서 repository에 넣는다. git commit -m "..

    [백준][C] 2667-단지번호붙이기/인접리스트/그래프/깊이우선탐색/넓이우선탐색
    카테고리 없음

    [백준][C] 2667-단지번호붙이기/인접리스트/그래프/깊이우선탐색/넓이우선탐색

    2667 : 단지번호붙이기 2021-08-04 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 🏡 시도 처음엔 출력해야할 것이 뭔지 먼저 따져봤다. 단지 수와 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력해야했다. 단지 수 카운팅을 위한 house_cnt 변수를 선언했고, 각 단지에 속하는 집의 수를 카운팅하기위해 house_cnt 를 index로 사용하여 cnt[house_cnt] 배열에 카운팅했다. 이 문제는 DFS또는 BFS를 사용..

티스토리툴바