https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net [풀이] BFS 유형의 문제입니다. BFS를 기본적으로 연습할 수 있는 문제라고 생각합니다. 시작 위치와 도착 위치를 배열에 받아 도착 위치에 가기까지 횟수를 더합니다. 도착 위치의 x,y 좌표값이 동일하다면, bfs 메소드가 종료되고 count 변수를 출력합니다. [코드] import java.io.BufferedReader; import java.io.IOException; import java..
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net [풀이] 정렬을 이용한 문제였습니다. 기존 배열은 정렬 시킬 경우, 이후 기존 배열의 각 값의 위치를 알 수 없으므로 clone() 메소드를 통해 깊은 복사를 합니다. Map의 key는 좌표값을, value는 좌표값에 대한 최소 인덱스를 저장합니다. 만약, Map에 이미 있는 값이라면 무시하고, 없는 값이라면 좌표값과 인덱스를 저장하며 하나 증가시..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net [풀이] 먼저! 아직 못풀었습니다..ㅠ 문제 풀이를 두가지로 풀어봤는데 시간초과로 틀렸습니다.. 그래서! 일단 다른 블로그 참고를 해서 다시 한번 풀어볼려고 실패한 사례만 남기겠습니다. 문제는 자료구조를 이용하는 유형입니다. 처음에는 StringBuffer를 이용해서 풀었습니다. deleteCharAt() 메소드와 insert() 메소드를 이용해서 index를 옮기며 풀어봤는데 60%를 조금 넘기면..
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 완전탐색 유형의 문제입니다. solve 메소드를 통해 재귀적으로 탐색합니다. 여기서 check 메소드를 통해 현재 위치에 놓을 수 있는지 없는지를 판단합니다. 현재 행의 위치에 놓을 수 없는지, 대각선에 이미 있는지 등을 확인해서 값을 반환합니다. 열의 차와 행의 차가 같을 경우가 대각선에 놓여 있는 경우입니다. [코드] import java.io.BufferedReader; import java.io...
https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net [풀이] 구현 및 규칙과 관련한 문제였습니다. 입력받는 수가 어떠한 범위에 있는지를 토대로 몇층에 있는지 계산하여야 합니다. 1이 입력되면 1개의 방을 지난다고 출력해야 합니다. 2부터 7까지는 2층에 있으며 2층에는 총 6개의 벌집이 있습니다. 8부터 19까지는 3층에 있으며 3층에는 총 12개의 벌집이 있습니다. 20부터 37까지는 4층에 있으며 4층에는 총 18개의 벌집이 있습니다. 38부터 61까지..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [풀이] dfs 메소드는 벽을 3개 세우는 것을 재귀적으로 구현한 부분입니다. bfs 메소드는 바이러스가 퍼지는 것을 구현한 부분입니다. check 메소드는 안전한 영역의 최대값을 구현한 부분입니다. 벽을 3개 세우고 바이러스가 퍼졌을 때 안전한 영역의 개수를 구하므로 dfs 메소드내에 bfs 메소드, bfs 메소드 내에 check 메소드가 위치합니다. 즉, dfs 메소드에서 벽을 다 세웠을 경우, bfs 메..
