알고리즘/백준 (70) 썸네일형 리스트형 [백준] 10815번 숫자 카드 숫자 카드(https://www.acmicpc.net/problem/10815) 1. 이해하기 상근이가 가지고 있는 카드 중 특정 카드를 가지고 있는지 찾는 문제이다. 이분 탐색문제이다. 2. 구현하기 단순히 이분탐색을 구현하면 된다. binarySearch(key): 중간값이 key에 해당하는지 보면서 검색해나간다. bool binarySearch(int n) { long long left = 0, right = N-1; while(left = en) return; findMid(st,en); int pivot = sang[st]; int l = st, r = en; while(1) { while(l = sang[l]) l++; while(l = en) return; int mid = (st+en)/2.. [백준] 2873번 롤러코스터 롤러코스터(https://www.acmicpc.net/problem/2873) 1. 이해하기 가장 큰 기쁨을 주는 롤러코스터의 움직임을 출력하는 문제. 행 혹은 열이 홀수인 경우, 모든 지역 탐색이 가능하다. 행, 열이 모두 짝수인 경우에는 어느 한 지역을 가지 않아야 한다. 가지 않는 한 지역을 구하는 기준은 다음과 같다. (행+열)이 홀수인 지역 중 가장 행복 지수가 낮은 지역을 구한다. 이유는 (행+열)이 짝수인 지역을 가지 않을 경우 한 곳은 두번 이상을 거쳐야 가장 오른쪽 아래 칸에 도착을 할 수 있기 때문이다. 가지 않는 지역을 결정했으면 그 지역을 기준으로 출발지역과 끝지역에서 서로 만나는 코스를 만든다고 생각한다. 가지 않는 지역을 기준으로 출발지역에서는 아래로 2칸, 끝지역에서는 위로 2.. [백준] 2098번 외판원 순회 2098번 외판원 순회 1. 이해하기 비트마스크와 DP를 이용하는 문제이다. 비트마스크를 이용하여 방문한 지점을 체크하고 DP를 이용하여 특정 지점까지의 최소거리를 갱신한다. 2. 구현하기 TSP(current,visited)일때 방문한 지점은 visited & (1 [백준] 1967번 트리의 지름 1967번 트리의 지름 1. 이해하기 트리의 지름은 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다. 가중치가 있는 간선들로 주어진다. 2. 구현하기 dfs를 이용해 루트로부터 제일 멀리 떨어진 노드 하나를 먼저 찾는다. 그 이후 이 노드로부터 가장 멀리 떨어진 노드를 찾고 그 때의 길이를 구한다. void dfs(int here, int cost) { visited[here] = true; if(ans < cost) { ans = cost; endPoint = here; } for(int i = 0; i < adj[here].size(); i++) { INF there = adj[here][i]; if(visited[there.next]) continue; dfs(there.next,c.. [백준] 17822번 원판 돌리기 17822번 원판 돌리기 1. 이해하기 원판의 회전은 독립적으로 이루어진다. 원판을 회전시킬 때는 수의 위치를 기준으로 한다. 원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi,di,ki이다. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다. 인접하면서 수가 같은 것을 모두 찾는다. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다. 원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구하는 문제. 시뮬레이션 문제. 2. 구현하.. [백준] 17142번 연구소 3 17142번 연구소 3 1. 이해하기 현재 비활성인 바이러스 중 M개를 선택해서 활성 상태로 바꾼다. 바이러스는 상하좌우로 인접한 빈 칸으로 동시에 복제가 된다. 연구소는 빈 칸, 벽, 바이러스로 이뤄져있다. 바이러스는 벽을 통과하지 못한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다. 연구소의 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제. 모든 바이러스에 대해 구해보는 완전탐색 문제. 2. 구현하기 활성화 시킨 M개의 바이러스에 대해 퍼지는 시간을 구한다. void bfs(vector live_virus) { memset(virus_time,-1,sizeof(virus_time)); queue q; int size = live_virus.size.. [백준] 17140번 이차원 배열과 연산 17140번 이차원 배열과 연산 1. 이해하기 처음은 크기가 3x3인 배열로 시작한다. 1초가 지날때마다 배열에 연산이 적용된다. R 연산: 배열의 모든 행에 대해서 정렬을 수행한다. 행의 개수 >= 열의 개수인 경우에 적용된다. C 연산: 배열의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다. 정렬하는 방법은 다음과 같다. 각각의 수가 몇 번 나왔는지 센다. 수의 등장 횟수가 커지는 순으로, 이것이 여러가지면 수가 커지는 순으로 정렬한다. 배열에 정렬된 결과를 다시 넣어준다. 넣어줄때 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다. 행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다. (r,c)에 들어있는 값이 k가 되기 위한 .. [백준] 17143번 낚시왕 17143번 낚시왕 1. 이해하기 격자판의 각 칸에는 상어가 최대 한 마리 들어있을 수 있다. 1초 동안 일어나는 일은 다음과 같다. 낚시왕이 오른쪽으로 한 칸 이동한다. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다. 상어가 이동한다. 상어가 이동하려고 하는 칸이 격자판의 경계인 경우에는 방향을 반대로 바꿔서 이동한다. 상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 때, 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다. 2. 구현하기 이 문제의 핵심 포인트는 상어의 움직임이다. 상어가 움직여서 원래 있던 자리까지 오는데의 거리는 가로 방향으로 움직였다면 2(R-1), 세로 방향으로 움직였다면 2*(C-1)이다. .. 이전 1 2 3 4 5 6 ··· 9 다음