알고리즘 문제 썸네일형 리스트형 BOJ2546(경비원) 풀이 - 거리 차이를 구하는 것이기 때문에, 한점을 기준으로 절대 거리를 구해서 빼주면 된다. from sys import stdin x,y = map(int, stdin.readline().split()) n = int(stdin.readline()) def dist_cal(idx, pos): if idx == 1: #북 return pos elif idx == 2: #남 return x + y + x - pos elif idx == 3: #서 return 2 * (x + y) - pos else : return x + pos pos = [] for _ in range(n + 1): idx, p = map(int, stdin.readline().split()) pos.append(dist_cal(idx.. 더보기 BOJ 9205(맥주 마시면서 걸어가기) 풀이(BFS) - 플로이드 와샬 혹은 BFS 문제이다. - 이웃한 점을 기준으로 서로간에 이동이 가능하면, 그래프를 정의해주는 것이 핵심이다. 즉, 아래와 같이 조건을 만족할 경우 그래프를 그려준다. point = [ list(map(int, input().split())) for _ in range(n + 2) ] edges = [[] for _ in range(N + 2)] #adjM = [[0] * (n + 2) for _ in range(n + 2)] for i in range(N + 2): for j in range(N + 2): if i == j: continue if abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) 더보기 A* 알고리즘(A Star Algorithm) 1. 개념 2. 시각화 3. 코드 1. 개념 최단경로를 찾는 그래프 탐색 알고리즘 중 하나입니다. 다익스트라 알고리즘과 유사하나 차이점은 각 꼭지점 x에 대해 그 꼭지점을 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값" h(x)를 매기는 방법을 이용한다는 점에서 차이가 있습니다. (h(x) 값을 정확하게 구할 수 없어도 괜찮습니다) 시작노드와 목적지 노드를 분명하게 정해 놓고, 이 두 노드간의 최단 경로를 파악합니다. 휴리스틱 추정값을 어떤 방식으로 제공하느냐에 따라 최단경로 파악 성능이 결정됩니다. A* 알고리즘은 출발 꼭지점으로 부터 목표 꼭지점까지의 최적 경로를 탐색하기 위한 것입니다. 이를 위해서는 각각의 꼭지점에 대한 평가 함수 f(n)를 정의해야 합니다. $ f(x) = g(x) .. 더보기 최소비용 신장트리(Minimum Cost Spanning Tree) 학습 목표 - 신장트리(Spanning Tree) 개념과 특징을 이해할 수 있다 - 최소비용 신장트리(Minimum Cost Spanning Tree) 개념과 특징을 이해할 수 있다 - 최소비용 신장트리 사용 사례 - 구현 방법 신장 트리 개념과 특징 무향방 연결 그래프 $G=(V,E)$ 가 주어질때 모든 노드를 포함하고 연결되어 있으면서, 간선 비용의 합이 최소인 트리 - 하나의 그래프에서 많은 신장 트리가 존재할 수 있다 - 모든 정점이 연결되어 있어야 하고, 사이클이 존재해선 안된다. - n개의 정점을 n-1개 간선으로 연결한다. 최소비용 신장트리 개념과 특징 신장 트리 중에서 가중치 합이 최소인 트리 최소비용 신장트리 사용 사례 1. 군집 분석(Cluster Analysis) 2. 필기 인식(Ha.. 더보기 이분 그래프 & 최대 이분 매칭 (Bipartite Graph & Maximum Bipartite Matching) 1. 이분 그래프(Bipartite Graph)란 "In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets Uand V such that every edge connects a vertex in U to one in V" 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프 (그림 상으로 파란색, 초록색으로 인접 노드가 분할이 가능하다) 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 의미 위의 세가지 모두 이분 그래프를 .. 더보기 BOJ 2578 코드 설명 빙고 판에서 3번 이상 줄이 그어지는 경우 "빙고"이며, 숫자를 없앤 카운트 수를 반환한다. 총평 단순 배열 문제라고 생각하였지만, '선이 세 개 이상 그어지는 순간 "빙고"라고 외친다' 조건 때문에 생각을 조금 더 해야 한다. #include #include using namespace std; int bingo[5][5]; int bin_total = 0; int check_row(int y, int x) { int bin = 1; for (int i = 0; i < 5; i++) { if (bingo[y][i] != -1) { bin = 0; break; } } return bin; } int check_col(int y, int x) { int bin = 1; for (int i = 0.. 더보기 BOJ 3055 시뮬레이터 문제이다. 어디서 참고한 코드 같지만, 출처는 기억이 나지 않는다. 문제를 풀기 위하여 bfs()를 한번만 돌릴 수도 있지만, 시뮬레이터 재현을 위해 '물'과 '고슴도치'의 이동을 한번씩 하게 하였다. 여기서 핵심은 moveWater(), moveHedge() 함수의 while(qsize--) 이렇게 하면, 시간 순서상으로 한번씩 Stage 각각 넘어갈 수 있게 된다. bfs 혹은 큐를 이용한 문제에서 사용할 수 있는 좋은 테크닉이라 기록에 남긴다. #include #include using namespace std; int r, c; const int HEDGE = 0; const int WATER = 1; char Map[50][50]; bool visit[50][50][2]; // 상하좌.. 더보기 이전 1 2 다음
