전체 글

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net BFS 문제다. 벽에서 갈 수 있는 칸들을 세는 문제다. 모든 벽에서 BFS를 돌리면 빈 칸을 여러 번 방문하기 때문에 시간초과가 날 것이다. 빈 칸의 영역을 찾아서 크기를 구한 뒤 배열에 저장해뒀다. 그 후 배열을 전체 탐색 하면서 벽인 경우 4방향을 검사해 갈 수 있는 영역의 크기를 더했다. 이 때 이어져 있는 영역이 존재할 수 있으므로, 영역을 찾을 때 영역의 번호를 부..

https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 비트마스킹을 이용한 BFS 문제다. 흔히 우리가 아는 2차원 배열에서 영역을 구하는 문제다. 그러나 인접한 모든 곳으로 지나갈 수 있는 것이 아니고 벽으로 막혀 있는 방의 영역을 구하는 문제다. 이 문제의 특징은 막힌 칸이 있는 것이 아니라 인접한 방 사이를 갈 수 없는 벽이 존재한다. 따라서 입력이 2차원 배열의 크기만큼 각 칸의 벽을 나타내는 정수가 들어온다. 좌1 상2 우4 하8로 2의..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 스택 자료구조 문제다. N자리 숫자에서 K개를 지워서 만들 수 있는 가장 큰 수를 찾는 문제다. 앞에서부터 순회해 스택에 숫자를 push한다. push 할 숫자가 stack에 들어있는 숫자보다 크다면 pop을 한다. 스택의 top보다 값이 작을 때까지 or k 범위 내에서 pop을 반복한다. 위 작업이 끝나면 스택에 남은 값들을 pop하면서 남은 문자열과 합쳐 답을 구한다. #include #include using namespace std; int n, m; int arr..

https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net DP와 Greedy 문제다. 제한된 성냥개비를 모두 이용하여 만들 수 있는 가장 작은 수와 가장 큰 수를 찾는 문제다. 자릿수가 커질 것이기 때문에 숫자가 아닌 문자열을 이용해 계산했다. 가장 큰 수의 경우 자릿수를 제일 크게 늘려야 한다. 1을 만들 때 2개가 필요하고 7을 만들 때 3개가 필요하므로 두 개만을 이용해 홀수 짝수인 경우를 고려했다. dp[2] = "1", dp[3] = "7" 만 초기값..

이전에 자바로 만들었던 notice 프로젝트를 이용했다. Domain Notice import lombok.Getter; import lombok.Setter; @Getter @Setter @Entity @Table(name = "notice") public class Notice { @Id @GeneratedValue(strategy = GenerationType.IDENTITY) @Column(name = "notice_id") private int id; @Column(name = "user_id") private String userID; private String title; private String content; private String write_date; } 위는 자바 코드다 자바에서..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net DP 문제다. 파일을 합치는 데는 두 파일의 무게의 합 만큼의 비용이 들고, 이 비용을 최소화 하는 문제다. 파일을 합칠 때는 연속한 두 개를 선택하여 합칠 수 있다. 처음 생각한 방법은 1차원 배열을 이용해 최소의 비용을 찾아나가는 것이다. 1번 파일부터 n-1번 파일까지 고려된 최소 비용에 n번 파일을 합치는 비용을 고려했다. 1 2 3 4 라는 파일이 있는 경우 3까지 계산이 됐다고..