■ 알고리즘 문제 풀이 (74) 썸네일형 리스트형 [BOJ] 백준 17144. 미세먼지 안녕! ▶문제설명[BOJ] 백준 17144. 미세먼지 안녕! https://www.acmicpc.net/problem/17144 ▶Hint시뮬레이션 문제이다. 1. vector에 모든 미세먼지에 대한 정보를 저장하고, 공기 청정기의 위치 정보를 저장한다. 2. 모든 미세먼지를 확산시킨다. 3. 공기청정기 상단은 반시계 방향, 하단은 시계 방향으로 공기를 한 칸씩 필터링한다.공기 청정기 상단은 방향을 상/우/하/좌로 바꾸면서 미세먼지를 순회하며 한 칸씩 당겨주었고 공기 청정기 하단은 방향을 하/우/상/좌로 바꾸면서 미세먼지를 순회하며 한 칸씩 당겨주었다. 4. 2~3을 T번 반복한다. 5. 모든 미세먼지의 양을 답으로 출력한다. ▶Solution [BOJ] 백준 1018. 체스판 다시 칠하기 ▶문제설명[BOJ] 백준 1018. 체스판 다시 칠하기 https://www.acmicpc.net/problem/1018 ▶Hint브루트 포스 문제이다. 1. 2차원 배열로 W로 시작하는 8x8 체스판과 B로 시작하는 8x8 체스판을 미리 만든다. 2. 입력으로 주어진 판을 8x8로 자르는 모든 경우에 대해서 다시 칠해야 하는 격자의 개수를 구한다. (이미 만들어 둔 체스판과 비교했을 때 색깔이 다른 격자의 개수가 다시 칠해야 하는 격자의 개수임) 3. 가장 작은 경우를 답으로 출력한다. ▶Solution [BOJ] 백준 14889. 스타트와 링크 ▶문제설명[BOJ] 백준 14889. 스타트와 링크 https://www.acmicpc.net/problem/14889 ▶Hint브루트 포스 문제이다. 두 팀으로 나눌 수 있는 모든 경우에 대해서 두 팀 간의 능력치 차이를 구하고, 최소 값을 찾아 출력한다. 함수 next_permutation()를 사용해서 순열을 생성하여 팀을 나누는 모든 경우를 구하고, n명중 2명을 선택하는 모든 경우를 선택하는 조합 알고리즘으로 팀의 능력치를 계산할 수 있다. ▶Solution [BOJ] 백준 14890. 경사로 ▶문제설명[BOJ] 백준 14890. 경사로 https://www.acmicpc.net/problem/14890 ▶Hint브루트 포스 문제이다. 높이 차이가 1보다 크거나 길이 L의 경사로를 설치할 공간이 부족한 경우 경사로 설치가 불가능하다. 모든 행과 열에 대해, 경사로를 설치하여 길을 완성할 수 있는지 확인하여 완성된 길의 개수를 답으로 출력하면 된다. 내리막 길 && 높이 차이가 1인 경우 경사로가 설치된 위치를 체크하는 것이 핵심이다. (1차원 배열 사용) 오르막 길 && 높이 차이가 1인 경우 내리막 길 경사로와 겹치지 않는지 확인하면 된다. ▶Solution [BOJ] 백준 17135. 캐슬 디펜스 ▶문제설명[BOJ] 백준 17135. 캐슬 디펜스 https://www.acmicpc.net/problem/17135 ▶HintBFS & 브루트 포스 & 시뮬레이션 문제이다. 궁수 3명이 만들 수 있는 모든 배치를 고려해야하고, 사정거리에 들어있는 적을 탐색하는 과정에 BFS를 수행하며, 모든 적군이 성으로 들어오기까지 몇 명의 적을 사살할 수 있는지 시뮬레이션 해봐야 답을 도출할 수 있다. 1. 궁수 3명을 배치한다. 2. 궁수들이 적군들 중 타겟을 정한다. (사정 거리 내에 있는 적군들 중 거리가 짧은 적군을 우선하고, 거리가 같은 적군이 여러 명일 경우 가장 왼쪽에 있는 적군을 타겟으로 한다.) 3. 타겟을 제거한다. 4. 모든 적군이 한 칸 앞으로 몰려온다. 5. 2~4 과정을 모든 적군이 성으로.. [BOJ] 백준 14888. 연산자 끼워넣기 ▶문제설명[BOJ] 백준 14888. 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 ▶Hint브루트 포스 문제이다. 모든 연산자 순열을 만들고, 만들어진 순서대로 식을 계산하면 되는 간단한 문제다. 모든 경우의 계산 결과들 중 최대 값과, 최소 값을 답으로 출력한다. ▶Solution [SWEA-D3] 1244. 최대 상금 ▶문제설명[SWEA] 1244. 최대 상금 https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD ▶HintDFS & 브루트 포스 문제이다. 2중 for문으로 숫자를 교환하는 모든 경우에 대해 DFS를 수행한다. 재귀 호출 시 현재 교환 횟수+1을 인자로 넘겨준다. 단, 불필요한 연산을 줄이기 위해서 같은 교환 횟수로 이전과 같은 상금이 나온 적이 있는 경우에는 중복되므로 재귀 호출을 하지 않도록 한다. bool visited[상금][교환 횟수] 배열을 만들어 관리하면 중복되는 연산을 막을 수 있다. ▶Solution [BOJ] 백준 13460. 구슬 탈출 2 ▶문제설명[BOJ] 백준 13460. 구슬 탈출 2 https://www.acmicpc.net/problem/13460 ▶HintBFS & 브루트 포스 문제이다. 판을 상/하/좌/우로 기울여서 빨간 구슬과 파란 구슬을 이동시킨다. 빨간 구슬과 파란 구슬이 각각의 위치에서 기울이는 방향으로 움직여야한다. 두 구슬은 겹칠 수 없으므로 겹칠 수 있다고 가정하고 구슬을 벽까지 이동시키면서 이동한 거리를 측정하여 거리가 더 길게 측정된 구슬을 기울였던 방향의 반대 방향으로 한 칸 이동시키는 방법으로 구현했다. 상/하/좌/우 모든 방향에 대해 BFS를 수행하면서 빨간 구슬만 'O'위치에 도달한 경우 그 때의 기울인 횟수를 정답으로 출력하되, 기울인 횟수가 10번을 초과하면 -1을 출력한다. ▶Solution 이전 1 ··· 3 4 5 6 7 8 9 10 다음