SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 대학교 1학년 때 한창 애먹었던 회문(palindrome) 문제다. 글자판 크기는 8 X 8로 고정이고, 매 테스트 케이스마다 찾아야하는 회문의 길이가 주어진다. 8 X 8 글자판을 순회하되, 안쪽 반복문은 8에서 찾아야하는 회문의 길이를 빼준만큼만 순회했다. 마지막으로 회문인지 검사하는 반복문은 회문의 길이 절반만큼만 순회하며 양끝에서 가운데로 가도록 검사했다. 위쪽이 가로로 회문을 찾는 반복문, 아래쪽이 세로로 회문을 찾는 반복문이다. 코드 #include char board[8][8]; int find_palindrome(int len) { int ans =..
분류 전체보기
17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 미세먼지 확산 과정을 이해하지 못한 점과 DFS + 시뮬레이션이라 생각한 것 때문에 푸는데 오래 걸렸다. 어찌어찌 DFS + 시뮬레이션을 통해 아주 느린 속도로 통과를 한 후, 다른 블로그를 찾아보니 단순 구현 + 시뮬레이션이었고, 문제 분류도 그랬다. 미세먼지 확산은 모두 "동시"에 일어난다. 이를 구현하기 위해 각 칸이 받는 영향(먼지를 퍼트려 먼지가 줄어들거나, 옆 칸의 먼지가 확산되어 먼지가 늘어나거나)을 기록할 배열이 따로 있어야 한다. 각 칸의 증감량..
17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 대각선으로 이동할 때 3칸을 고려해야한다는 걸 뒤늦게 알아 해결한 문제 BFS로 풀었는데, 대부분 DFS로 풀었고 DP로 푼 경우도 있는 것 같다. 풀고서 다시 생각해보니 DP도 좋은 풀이인 것 같다. BFS로 풀 경우 조건을 많이 걸어 경우의 수를 좀 많이 제외시켜줘야 할 것 같다. 파이프의 앞 쪽 좌표와 놓인 방향을 큐에 넣어 BFS를 수행했다. 집의 벽(문제에서 1로 표현한 벽 말고)에 닿도록 가로, 세로로 놓이게 된다면 그 곳이 (..
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨집을 선택하기 위한 백트래킹이 주요한 문제였다. 입력을 받을 때, pair 배열 house와 chicken에 가정집과 치킨집 각각의 좌표를 저장하며 개수를 카운트 했다. 이후 각 집에서 모든 치킨 집까지의 거리를 2차원 배열 dist에 저장 (row는 가정집 좌표 배열 house의 인덱스, column은 치킨집 좌표 배열 chicken의 인덱스) 백트래킹으로 치킨집 m개를 선택 후, 각 집에서부터 선택된 치킨집들을 대상으로 치킨 거리 계산..
