목록Computer/Coding Test (70)
Machineboy空
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제요약 1칸 좌우 이동, 2배 이동이 가능할 때, 도착점으로 가는 최단 시간과 경우의 수 구하기. 난이도 Gold 4 풀이 포인트 bfs 응용 방문한 적 없다면 이동 시간 누적 cnt 배열 경로의 수는 지금까지의 경로의 수에 누적해주는 방식 방문한 적 없다면 현재 위치까지의 경우의 수 + 다음 정점의 경우의 수 방문한 적 있고, 현재 노드에서 간 적 있는 ..
https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 문제요약 괄호를 추가하여 식의 최댓값 구하기 난이도 Gold 3 풀이 포인트 숫자와 기호 나누어 생각하기 재귀의 반복 동작 파악 REVIEW 우선 괄호를 친다는 것이 실제로 string 사이에 실물 괄호를 쳐주는 것이 아닌, 먼저 연산을 하면 된다는 것을 파악하고, stack에 쌓으며 pop을 해줄까 하는 아이디어를 떠올렸다. 다음으로는, string 수식을 어떻게 사칙연산으로 바꾸..
https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 문제요약 hp가 0이 될 때까지 공격 최소 횟수 난이도 Gold 4 풀이 포인트 Struct 사용법 // 세 개 부터는 튜플인데, 귀찮으니 struct struct A{ int a,b,c; }; queueq; 그래프로 치환하여 생각하기 음수 막아주는 코드 int na = max(0, a - _a[i][0]); int nb = max(0, b - _a[i][1]); int nc = max(0, c - _..
https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 문제요약 상하좌우로 이동하는 불, 지훈이는 미로에서 탈출가능한 지 난이도 Gold 4 풀이 포인트 BFS REVIEW 우선, 불이 여러 군데서 발생할 수 있다는 것과 발생하지 않을 수 있다는 것을 간과했다. 문제를 제대로 읽자. 그리고 아직 bfs와 dfs의 용도를 완벽하게 파악하지 못했나보다. 불은 dfs로 퍼져나가고, 지훈이는 bfs로 최단 거리 내에 이동해야한다고 생각했다...
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제요약 조건에 따라 인구 이동이 일어나는 횟수 난이도 Gold 4 풀이 포인트 DFS, connected componet 문제임을 파악하기 REVIEW 우선, 2차원 좌표를 1차원으로 묶어서 생각하는 법을 생각하다가 어후 너무 복잡해져서 풀이를 관두었다.. 정말 간단하게 생각하면 된다. 기존 DFS을 돌릴 때 육지라면 ( a[ny][nx] ==1 ) 이면 이동했던 것을 문제의 조..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 문제요약 최단거리가 가장 먼 육지의 두 곳에 보물심기 난이도 Gold 5 풀이 포인트 BFS를 실행하면, 한 칸씩 움직일 때마다 최단거리가 갱신됨 즉, 도착 지점 과 출발지점 쌍이 계속 나오기 때문에 2쌍을 뽑아서 돌릴 필요가 없다. BFS void bfs(int y, int x) { memset(visited, 0, sizeof(visited)); visited[y][x] = 1; queue q;..
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제요약 트리 구조에서 한 노드를 지웠을 때 리프노드의 개수를 구하라. 난이도 Gold 5 //내 코드 #include using namespace std; int n, a[52], k, ret; vector adj[52]; bool b[52]; void cut(int node) { b[node] = false; for (int s : adj[node]) { cut(s); } } int ma..
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제요약 가장 효율적인 치킨 집의 개수와, 치킨 집까지의 최소 거리의 합 난이도 Gold 5 풀이 포인트 조합 void combi(int start, vector v) { if (v.size() == m) { chickenList.push_back(v); return; } for (int i = start + 1; i < chicken.size(); i++) { v.push..