본문 바로가기

알고리즘72

BOJ 20165 - 인내의 도미노 장인 호석(C++) https://www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 풀이 라운드만큼 반복, 한 라운드에 공격과 수비 순으로 동작 원래 상태 복구를 위해 원본 배열 보관 originp[][] 라운드가 지속되면서 변경되는 배열 map[][]을 갱신하며 진행 1. 공격 1-1. y, x, dir이 주어짐, cnt=map[y][x]-1, res=1 1-2. cnt가 0보다 큰 동안 반복 1-3. dir에 따라 y, x값 변경(한 칸 이동) -> y, x값이.. 2021. 10. 28.
BOJ 1655 - 가운데를 말해요(C++) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 우선순위 큐와 구역을 나누는 것으로 해결가능 - 중간 값과 더 작은 값들을 저장하는 오름차순 우선 순위 큐 : little_pq, - 중간 값보다 쿤 값들을 저장하는 내림차순 우선순위 큐 : big_pq 1. 상황에 따라 하나의 우선 순위 큐에 값을 저장 두개의 큐에 값이 없는 초기 상태거나 큐의 사이즈가 같다면 little_pq에 저장 외친 수(현재까지의 수)가 짝수라면 중.. 2021. 10. 22.
Programmers - 행렬 테두리 회전하기 https://programmers.co.kr/learn/courses/30/lessons/77485?language=cpp 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 풀이 주어진 문제에서는 행이 x좌표, 열이 y좌표이지만, 나는 (y, x)의 형식이 편해서 변경하여 품 진행 방향의 역순으로 변경 1. arr[y1][x1]의 값을 따로 저장 2. 진행 방향의 역순 : (y2, x1) -> (y1, x1), (y2, x2)->(y2, x1), (y1, x2)->(y2, x2), (y1, .. 2021. 10. 21.
BOJ 8090 - 택배(C++) https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 풀이 입력 값에 대한 정렬이 필요 1. 도착지 오름차순, 2. 출발지 오름차순 해당 지역을 거치는 택배의 총 개수를 저장하는 배열이 필요 -> int capacity[] * 단 트럭의 용량을 초과할 수는 없음 1. 정렬된 배송정보에 대한 탐색 2. 출발지 ~ 도착지중 지역을 거쳐가는 최대의 갯수 max_cnt를 저장 3. 현재 배송지에 대해 가져갈수 있는 택배의 개수를 구함 -.. 2021. 10. 19.
BOJ 14888 - 연산자 끼워넣기(C++) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 연산자마다 가능한 수가 정해져있음 -> 해당 연산자 개수와 숫자 개수(N)의 모든 경우의 수 탐색(브루트 포스) 1. 연산 순서 백터의 크기가 N-1보다 작으면 현재 사용가능한 연산자중에서 하나를 연산순서에 push, 연산 순서 백터의 크기가 N-1과 같다면 2로 이동 * 계산할 수가 N개라면 연산자의 개수는 N-1 2. 해당 연산자 순.. 2021. 10. 16.
BOJ 2110 - 공유기 설치(C++) https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 두 공유기 사이의 거리에 대해 이분탐색을 이용 초기 값 -> left = 1, right = 공유기의 최대 좌표 1. mid = (left + right)/2 mid)로 했었는데 테스트 결과가 실패했음 문제에서의 거리는 공유기가 설치된 좌표까지 포함하는 거 였음 if(arr[i] - before >= mid) ex) 1, 3, 4 이고 거리.. 2021. 10. 14.
BOJ 2615 - 오목(C++) https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 풀이 자표와 방향성에 대해 탐색했는지 확인을 위한 bool 3차원 배열 visit 사용 오목판의 현재 위치에 대해 8방향을 탐색해야하지만 2중 for문을 이용해 왼쪽에서 오른쪽, 위에서 아래로 탐색하기 때문에 4방향으로만(동, 남동, 남, 남서) 제한하여 탐색 위의 방향으로 탐색할 경우 (1, 1)을 시작으로 연속되었는지 확인 한 후 (2, 2)에서 (1, 1)로 연속성을 확인 비효율적이고 vis.. 2021. 10. 5.
BOJ 14889 - 스타트와 링크(C++) https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 1. 스타팀에 누가 포함될지 N/2명을 뽑는 경우의 수에 대해 탐색 - bool 자료형의 1차원 배열 visit을 이용하여 스타트 팀에 포함되었는지 여부를 확인 - 배열의 값이 true면 스타트 팀, false면 링크 팀 2. 스타트 팀, 링크 팀에 대해 각각 점수 계산 - 2중 for문을 이용하여 i와 j가 같은 팀일때의 해당 팀의 점수를 더함 - visit[i] && visit[j] 이면 스타트 팀, !vis.. 2021. 10. 5.
BOJ 1912 - 연속합(C++) https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 연속된 수에 대한 최대값이기 때문에 2가지만 고려함 1. 연속하지 않을 때 - 이전 값과 연속할 때 현재 값보다 작은 경우, 자기 자신을 가지고 감 - dp[i] > (dp[i-1] + dp[i]) 2. 연속할 때 - 이전 값과 연속할 때 현재 값보다 큰 경우, 연속합을 가지고 감 - dp[i] < (dp[i-1] + dp[i]) 순서대로 탐색하며 1, 2를 적용하고 최대값을 갱신 #include #i.. 2021. 10. 5.

티스토리툴바