솧로그

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net https://olsohee.tistory.com/44 이 문제와 마찬가지로 bfs로 탐색하면서 이전 값에 + 1을 해주어 토마토가 익는데 걸리는 일수를 구하면 된다. 주의할 점은 우선 처음에 그래프 값을 입력받을 때 익은 토마토의 위치를 큐에 넣어주어야 한다. 그리고 큐에서 토마토의 위치를 빼서 해당 위치의 사방면을 탐색하고, 아직 익지 않은 토마토인 경우 이전 값 + 1을 저장..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 최소 거리를 구하는 문제이기 때문에 bfs를 사용하면 된다. 관건은 이동한 칸수를 계산하는 것인데, visited 배열에 1, 2, 3, ... 과 같이 이동한 칸수를 기록해주면 된다. 즉 visited 배열의 값이 0이면 아직 방문하지 않은 위치인 것이고, 시작 위치와 같이 한 번만에 방문하면 1, 그 다음으로 방문하면 2를 기록해주면 된다. 그리고 visited 배열의 값이 0이 아닌 경우, 즉 이미 방문한 경우에는 제외하기..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net bfs 문제를 몇 달만에 풀어서 다 까먹었을까봐 걱정했는데 아주 쉬운 문제라서 그런지 잘 풀었다! 오랜만에 bfs를 푸는 만큼 쉬운 문제더라도 꼼꼼히 보자. bfs와 dfs 문제의 시간 복잡도는 O(V + E)이다. 이때 V는 노드의 개수, E는 간선의 개수이다. 주의해야 할 점은 다음과 같다. 방문 후에는 방문 처리를 해주어야 한다. 따라서 그림이면서 방문하지 않았을 경우에만 bfs를 시작하고, 이때..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 이분 탐색으로 그냥 해당 값이 있는지 찾기만 하면 되는 게 아니라 몇 개 있는지를 찾아야 한다. 따라서 상한선과 하한선을 찾아서 몇 개인지 개수를 계산하면 된다. 입력 값을 배열에 저장하고 배열을 정렬한다. 상한선과 하한선을 찾고, (상한선 - 하한선)이 해당 값의 개수가 된다. 예를 들어 [1, 1, 2, 2, 2, 3]과 같이 배열이 있을 때, 값 2의 상한..

https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 어려운 문제는 아니고 그냥 구현 문제이다. 그런데 스티커 회전이라든지, map에 붙일 수 있는지 없는지 이차원 배열의 범위를 탐색한다든지 짜잘하게 신경써야 할 것이 많다. 그리고 그만큼 실수하기 쉬운 문제이다. 다행히 몇 번 디버깅하면서 맞출 수 있었는데, 그래도 다음에 다시 풀면서 꼼꼼히 생각하자는 의미로 기록한다. import java.io.BufferedReader; import java.io..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 그리디 문제로, 어떻게 하면 제일 큰 결과 값을 구할 수 있을지 아이디어만 잘 생각하면 된다. 음수의 경우 음수끼리 묶어서 곱해주어야 양수가 되어 결과 값이 커진다. 그리고 이때 절댓값이 큰 음수끼리 우선적으로 묶어주어야 결과가 더 크다. 따라서 음수를 minus 리스트에 모아서 minus 리스트를 오름차순하고 순차적으로 묶어준다. 만약 두개의 음수를 묶고 묶이지 않은 음수가 1개 남는다면, 이..

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 처음에는 입력 값을 배열에 넣은 뒤 배열의 앞에서부터 순차적으로 순회하니 조금 복잡해졌다. 그런데 배열의 뒤에서부터 순회하면 훨씬 깔끔하다. 배열의 뒤에서부터 순회해서 max와 arr[j]를 비교한다. max = arr[j]인 경우, answer에 max-arr[j] 값을 더해준다. (arr[j]를 max 값에 팔..

https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 우선 날짜를 다루는 방법은 3월 1일은 301, 11월 30일은 1130로 표현하면 된다. 처음에는 어떤 달은 30일까지 있고, 어떤 달은 31일, 28일까지 있으므로 앞서 언급한 방식으로 처리하면 안되는 게 아닌가? 생각했는데, 어차피 입력으로 주어진 날짜들로 합 계산을 하는 게 아니라 그저 대소 비교만 하기 때문에 상관없다. 주의할 점은 다음과 같다. 이전 꽃이 지는 날짜를..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이번 문제는 그리디 문제로, 회의 종료 시간이 빠른 순서대로 정렬한 뒤 차례대로 회의를 진행하면 된다. 그런데 주의할 점은, 만약 회의 종료 시간이 같다면 회의 시작 시간이 빠른 순으로 정렬해야 한다. 예를 들어, 다음과 같이 회의가 있다고 가정하자. 1 ~ 3 4 ~ 8 8 ~ 8 만약 회의 시작 시간이 빠른 순으로 정렬하는 것을 고려하지 않고 다음 순서로 진행한다면, 1 ~ 3 8 ~ 8 4 ~ 8 8 ~ 8 회의를 진행한 후 preMeetingEndTime 변수의 값은 8이 되어 4 ~8 회의를 진행할 수 ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 유형을 모르고 이 문제를 접했다면 그냥 완전탐색으로 풀었을 거 같다. 그러나 dp를 공부하다가 접한 문제이기 때문에 dp로 풀기 위한 방법을 고민했다. 그런데 아무리 생각해도 점화식이 생각나지 않았다.. 결국 다른 사람의 풀이를 살짝 참고했다. 포인트는 dp 배열을 뒤에서부터 채워주는 것이다! 앞에서부터 채우는 경우만 생각해서 적당한 풀이가 생각나지 않았는데, 뒤에서부터 채운다고 생각하니 금방 점화식을 생각할 수 있었다. (특정 날짜에 일을 시작하면, 그 일이 끝나는 날짜까지는 다른 일을 하지 못한다. 즉, 일이 끝나는 날짜가 중요하..