전체 글

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 사용하여 최단 거리를 구하는 문제다. 이전에 BFS를 이용하여 풀어보아서 DFS로 시도하였다. 그러나 DFS로 가지치기를 잘 하지 않는이상 input데이터 범위가 10만이여서 시간초과가 날수밖에없다. DFS로 계속시도하였는데 가지치기를 잘한 DFS풀이를 보고 그냥 최단거리는 BFS를 사용하는것이 정신건강에 이롭다는 것을 느꼈다. BFS풀이를 할 때에도..

문제 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 조합으로 궁수의 위치를 뽑고 시뮬레이션을 하였다. 다른 풀이를 보면 BFS를 사용해 궁수부터 적 위치까지 탐색을 한 풀이들이 많은데 본인은 그렇게 하지않고 왼쪽 하단 부터 오른쪽 상단까지 열 순서가 아닌 행 순서로 탐색하였다.(좌 하->상 ... 우 하->상) 그리고 탐색하면서 시간마다 적이 성벽에 닿으면 사라진다. 배열을 N+1, M 크기만큼 구현하여 N+1 위치에 성벽 위치를 지정하였다. 그리..

문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 0,0 좌표부터 시작하여 중복되지 않은 알파벳을 탐색하여 가장 긴 길이를 구하는 문제이다. 처음에는 단순하게 DFS 탐색을 하며 탐색했던 알파벳을 List에 넣어서 새로운 좌표를 탐색할 때마다 List에 알파벳이 중복되는지 검사하였다. 그런데 이렇게 하면 시간초과가 발생하여 통과하지 못한다. 그렇다면 어떻게 접근하면 좋을까? 내 생각은 List에 넣고서 contain 사용해 있는..

문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 좌측 열에서부터 우측 열까지 놓을 수 있는 파이프의 최대 갯수를 구하여야 한다. DFS를 사용하여 한칸씩 우측열로 이동할 때마다 우측 상단, 우측, 우측 하단 순으로 파이프를 놓을 수 있는지 없는지 탐색하였다. 좌측 열 처음부터 우측 열 끝까지 도달하면 파이프를 놓을 수 있는 갯수를 추가하였는데 이 때 파이프가 우측 열 끝가지 도달하던(경로탐색 성공), 도달하지 않던(경로탐색 실패) 이전에 탐색한 경로..

문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 먼저 맵의 CCTV 좌표(x,y), 타입 정보를 저장하였다. 1번 카메라는 한쪽 방향만 감시할 수 있다. 2번 카메라는 (좌, 우), (상, 하) 방향을 감시할 수 있다. 3번 카메라는 (상, 우), (우, 하), (하, 좌), (좌, 상) 방향을 감시할 수 있다 4번 카메라는 (좌, 상, 우), (상, 우, 하), (우, 하, 좌), (하, 좌, 상) 방향을 감시할 수 있다..

문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 풀이 분할정복을 이용하는 전형적인 문제 처음에 좌표 r, c 의 순서를 구할 때 좌표 r,c 가 속해있는 사분면까지 순서를 모두 구했는데 시간 초과가 발생하였다. 이 문제는 구하려는 좌표가 1,2,3,4 분면 어느곳에 위치한지 먼저 파악한 후에 사분면 1개의 크기가 1이 될때까지 좌표 r,c의 사분면을 구하면서 이전 사분면들의 크기를 모두 더하면 된다. 재귀를 이용하여 각 사분면을 ..

문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 트리 구조를 만들고 노드를 삽입하여 전위, 중위, 후위 탐색하여 출력하는 문제다. 전위 : 루트 -> 왼쪽 -> 오른쪽 중위 : 왼쪽 -> 루트 -> 오른쪽 후위 : 왼쪽-> 오른쪽- > 루트 순으로 탐색한다. 이를 코드로 구현하면 다음과 같다. (트리의 탐색은 추후 링크로 대체 예정) import java.io.BufferedReader; import java.io.Buff..

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 도시의 지도 데이터를 입력받으면서 치킨집 좌표와 집 좌표를 list자료형에 입력하였다. 문제에서는 치킨집 개수 M개 일 때 치킨집 거리와 집 거리의 합들이 최소가 될 때 그 길이를 구하는 것을 요구한다. 처음에 치킨집의 좌표를 조합으로 출력하여 각 치킨집이 해당 위치에 있을 때 BFS탐색을 통해 집까지의 거리를 구하려고 했다. 그러나 이렇게 하면 너무 오래 걸릴 뿐..

문제 문제링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 문제를 잘 읽어보지 않아 시간이 오래 걸린 문제... 문제에서 예제로 재료가 4개일 때 선택된 재료 2개와 선택되지 않은 재료 2개의 시너지를 각각 비교하여 두음식간의 맛의 차이가 가장 작은 것을 구하는 것으로 예시를 들었다. 그래서 조합으로 N개의 재료중에서 2개를 뽑아서 시너지를 구하려고 하였다. 그런데 음식 재료가 4개가 아닌 값이 N개의 재료가 들어왔을 때 N/2 의 재료를 사용하여 선택되지 않은 나머지 재료를 N/2와 비교하는 문제였다. 즉, N_C_N/2 경우의 수에서 시너지를 구하는 문제다.. 코드는 다음과 같다. import ja..

문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 다른 사람은 어떻게 느꼈을지 모르겠지만 본인에게는 어려웠던 문제 특히 "배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다." 라는 조건을 어떻게 해야할지 감이 잡히지 않았음. 우선순위 큐를 생성하면서 비교 조건을 절대값이 같을 때 음수 -> 양수 로..