우노

문제 링크 https://www.acmicpc.net/problem/11047 풀이 동전 배열을 마지막 idx 부터 역순으로 탐색 남은 금액이 해당 idx 의 동전보다 크거나 같다면, 남은 금액에서 해당 idx 금액 만큼을 차감하고 동전 개수 + 1 마지막으로 탐색한 idx 부터 1~2번을 반복하며, 남은 금액이 없을 때까지 무한 루프 코드 #include #include using namespace std; vector coin_list; // 목표 금액까지 몇 개의 동전이 필요한지 출력해주는 함수 int greedy(int remain_cost){ // 목표 금액까지 필요한 동전 개수 int count = 0; // 동전 배열을 끝에서부터 탐색하기 위한 idx int idx = coin_list.si..

문제 링크 https://www.acmicpc.net/problem/2583 주요 변수 grid_paper 모눈종이 adj_queue 어떤 영역과 인접한 영역들을 가지고 있는 Queue 풀이 전체 모눈종이에서 "직사각형에 포함된 영역은 1, 포함되지 않은 영역은 0" 으로 지정한다. 모눈종이를 0,0 영역부터 M-1,N-1 영역까지 탐색하며, 분리된 영역을 모두 탐색할 때까지 진행한다. 해당 영역이 직사각형에 포함되지 않은 영역(==0) 이라면 해당 영역은 방문헀으므로 2 로 수정한다. 해당 영역과 상하좌우로 인접한, 직사각형에 포함되지 않은 영역(==0)을 전부 탐색한 뒤, adj_queue 에 삽입한다. adj_queue 에서 가장 먼저 추가된 영역을 하나씩 제거하며, 제거한 영역과 상하좌우로 인접하..

문제 링크 https://www.acmicpc.net/problem/1012 사용 변수 cabbage_field 배추밭 adj_queue 어떤 배추와 인접한 배추들의 위치 풀이 모든 배추의 위치를 입력 받아 cabbage_field 에 저장 cabbage_field 의 모든 배추 위치를 확인할 때까지 배추흰지렁이 탐색 해당 배추 위치를 방문한 적이 없다면 (==1) 해당 배추는 방문헀으므로 0 으로 수정한다. 해당 배추와 인접한 모든 배추들을 탐색해, adj_queue 에 삽입한 뒤, adj_queue 에서 가장 먼저 추가된 배추를 하나씩 제거하며, 해당 배추와 상하좌우로 인접하고, 방문하지 않은(==1) 배추는 추가로 adj_queue 에 삽입한다. 인접한 배추는 방문했으므로 0으로 수정한다. 이는 a..

문제 링크 https://www.acmicpc.net/problem/1260 풀이 DFS 는 한 노드에서 인접한 노드를 발견하면, 그 즉시 발견한 노드에 대해 DFS 함수를 실행하는 방법으로 구현했습니다. BFS 는 재귀가 아닌, Queue 를 이용한 반복문으로 구현했습니다. Queue 의 front 노드를 출력한 뒤, front 노드와 인접한 노드 중 아직 방문되지 않은 노드를 Queue 에 새롭게 추가하고, front 노드를 삭제합니다. Queue 안에 노드가 없을때까지 반복합니다. 코드 #include #include #define N 1001 using namespace std; // N : 정점의 개수, M : 간선의 개수, V : 탐색 시작 정점 int n, m, v; // f_node : 연..

문제 링크 https://www.acmicpc.net/problem/1987 풀이 이미 방문한 위치를 제외하고, 상하좌우로 최대한 얼마만큼 갈 수 있는지에 대한 문제이다. 방문 여부는 'alphabet' 1차원 배열을 사용해 저장했다. 알파벳은 'A' 부터 'Z' 까지의 문자로 이루어져있으며, 각 문자를 int형으로 변환하면, 10진수 65 ~ 90 의 값으로 이루어져있다. 따라서, 'A' 의 경우 int형 변환 후, 65를 빼면 0 이기 때문에, 0번째 index 를 'A'의 위치로 설정하고 'Z' 는 65 를 빼면 25 이기 때문에, 25번째 index 를 'Z'의 위치로 설정했다. 그리고 dfs 함수..

문제 링크 https://www.acmicpc.net/problem/1199 오일러 경로 및 오일러 회로 공통점 무향이나 유향 그래프가 있을 때, 그래프에 존재하는 모든 간선을 정확히 1번 씩만 방문하는 연속된 경로 차이점 시작점과 도착점이 다르면 오일러 경로 시작점과 도착점이 같으면 오일러 회로 오일러 경로 및 회로의 존재 여부 판단 무향(or 양방향) 그래프의 경우 차수가 홀수인 정점이 2개일 때, 오일러 경로 존재 즉, 시작점과 도착점의 차수만 홀수일 때 차수가 홀수인 정점이 0개일 때, 오일러 회로 존재 즉, 모든 정점의 차수가 짝수일 때 무향 그래프이기 때문에, 시작점과 끝점을 제외하고서는, 들어오는 간선이 있다면 반드시 나가는 간선이 하나 더 있어야한다. 따라서, 차수는 항상 2의 배수꼴을 가..

문제 링크 https://www.acmicpc.net/problem/9663 풀이 N-Queen 문제는, 크기가 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없도록 놓는 경우의 수를 구하는 문제이다. 퀸이 서로 공격할 수 없는 조건은 다음과 같다. 퀸이 놓였을 때 퀸 자신을 기준으로 일직선상(가로 및 세로)과 대각선 방향에는 아무것도 놓여있으면 안 된다. N-Queen 문제는 백트래킹의 가장 대표적인 예제로서, 퀸의 특성상 체스판 한 행당 한 개의 퀸만 존재할 수 있다는 것을 전제로 깔아두고 시작하는 것이 좋다. 또한, 이 문제는 N*N짜리 배열을 직접 만들 필요 없이, 크기가 N인 일차원 배열을 만든 후, 각 행의 몇 번째 열에 퀸이 있는지를 저장하는 방식으로 풀 수 있다. 예를 들어 N = 4일때..

개요 PageRank 개요 PageRank 란? 하이퍼링크 네트워크란? PageRank 의 응용 PageRank 의 핵심 아이디어 Random Walk Interpretation PageRank 심플버전 PageRank 심플버전 설명 Power Iteration PageRank 오리지널 PageRank Score 심플 버전의 문제점 Random Teleport PageRank 오리지널 버전 설명 PageRank 란? Google 검색 엔진의 기반 알고리즘이다. 하이퍼링크를 이용해 웹 페이지 중요도를 측정한다. 하이퍼링크 네트워크란? Web 을 Directed graph 로 보는 형태이다. Node : 웹페이지 Edge : 하이퍼링크 PageRank 의 응용 모든 그래프에서, 노드의 중요도 측정에 사용한다..