본문 바로가기

전체 글62

이분탐색+백준 2805 C++ 이분탐색이란?정렬된 배열이나 범위에서 원하는 값을 빠르게 찾기 위한 탐색 알고리즘입니다.전체를 한 번에 다 보지 않고, 중간을 기준으로 반씩 줄여가며 탐색합니다.정렬된 데이터에서만 사용 가능중간값(mid)을 기준으로 왼쪽 or 오른쪽 중 한쪽만 계속 탐색시간복잡도: O(log N) (매우 빠름!) 알고리즘 문제에서 구현이 너무 쉽다면 이분탐색을 꼭 꼭 꼭 생각해보자!!! 이렇게 계속 반으로 쪼갠다.🔧 기본 구조 (코드 예시 - C++)int binarySearch(vector& arr, int target) { int left = 0; int right = arr.size() - 1; while (left 어떻게 동작하나?예: [1, 3, 5, 7, 9, 11] 에서 7을 찾는다고 할.. 2025. 5. 8.
깃 Git index.lock 에러 클론하다가 컴퓨터가 꺼져서 오류가 생겼는데 Git이 커밋 작업을 마무리하기 전에 중단되어서 잠금 파일이 남아서 그런 것이다.파일 경로 따라가서 index.lock 파일 지워주면 해결된다. 근데 나는 파일이 안 보여서 cmd에서 지웠다 2025. 5. 1.
백준 1003 피보나치 함수 DP 점화식 만드는게 중요하다.f[n] = f[n-1] + f[n-2]#include #include #include #include using namespace std;vector>v;//first = 0 sencond = 1int main() { v.resize(41); int n; int temp = 0; cin >> n; v[0].first = 1; v[0].second = 0; v[1].first = 0; v[1].second = 1; for (int i = 2; i > temp; cout 2025. 2. 17.
2178 미로찾기 bfs c++ 선언을 전역변수로 하고 main에서 resize를 하니 코드가 깔끔해진 것 같다#include #include #include #include using namespace std;int n, m;vector> maze; // 미로 정보를 저장vector> distan; // 최단 거리vector> visited; // 방문 여부int dx[4] = { 0, 1, 0, -1 }; // 상, 하, 좌, 우int dy[4] = { 1, 0, -1, 0 };void bfs() { queue> q; // 시작점 초기화 q.push({ 0, 0 }); distan[0][0] = 1; visited[0][0] = true; while (!q.empty()) { .. 2025. 1. 7.
백준 1620 포켓몬 마스터 c++ https://www.acmicpc.net/problem/1620 처음에는 그냥 넣고 선형탐색으로 해서 시간초가 나왔는데 해시맵으로 index번호와 함께 저장하면 바로 찾을 수 있어서 탐색이 필요 없다.#include#include#include#include#includeusing namespace std;vector > v;int main() { int n, m; cin >> n >> m; vector v1(n); vector v2(m); for (int i = 0; i > v1[i]; } for (int i = 0; i > temp; if (temp[0] 2025. 1. 3.
MST 알고리즘(크루스칼, 프림) 최소비용 신장트리 (Minimum Spanning Tree, MST)MST의 특징신장트리: 그래프의 모든 정점을 포함하며, 사이클이 없는 트리입니다.최소 비용: 간선 가중치의 합이 최소가 되는 트리입니다.유일성: 모든 간선의 가중치가 서로 다르면 MST는 유일합니다. 즉 여러 경로가 나올 수 없다는 것이다.MST 알고리즘MST를 구하는 알고리즘은 다음과 같은 두 가지 주요 방법이 있다.1. 크루스칼 알고리즘 (Kruskal’s Algorithm)방법: 간단하게 생각하면 sort하고 sort순서대로 간선연결하고 cycle이 발생하는지 검증만 하면 끝이다.그래프의 모든 간선을 가중치 기준으로 오름차순 정렬합니다.최소 가중치의 간선부터 하나씩 추가합니다.사이클이 발생하지 않는 경우에만 간선을 추가합니다.모든 .. 2024. 12. 7.

티스토리툴바