1. 문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 2. 풀이 생각보다 삽질을 많이 한 문제였다. 처음에는 '빗물의 높이를 모르는데 어떻게 구하지?'라고 생각했는데 문제를 다시 잘 읽어보니 '비의 양에 따른 모든 경우를 다 조사해보면'이라는 문구를 보고 브루트포스를 떠올렸고 탐색을 하며 최대 개수를 구하는 문제니 DFS나 BFS를 생각했다. 여기서는 DFS로 문제를 해결하였다. 브루트포스를 돌릴 때 주의해야할 점은 노트에 적혀있는대로 '아무 ..
1. 문제 https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 백준에서 구현으로 분류되어 있는 문제이다. 예제 입력으로 주어지는 수를 문자열로 받은 후 하나씩 갯수를 센다. 이때 6과 9는 같은 수로 처리되므로 반복문이 끝난 후 6과 9가 나온 횟수를 더한 후 2를 나누어 주었다. 이때 횟수를 저장할 변수나 배열 원소들을 실수형으로 선언해야 정확한 개수가 나온다. 예를 들어 저장할 변수나 배열 원소들을 정수형으로 선언했다면 6이 1번 9가 2번이 나왔을 경우 횟수를 더하고 나누면 "1 + 2 = 3, 3 / 2 = 1"이 된다. 실제..
1. 문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 2. 풀이 백준에서 시뮬레이션과 큐 알고리즘으로 분류되어 있는 문제이다. 처음 이 문제를 보았을 때 예제 입력을 제대로 보지 않고 우선순위 큐(PriorityQueue)를 이용하면 한번에 해결될 거 같다고 생각해서 그냥 바로 코드를 작성했다가 1 1 9 1 1 1 입력을 보고 다시 코드를 수정했다. 문제를 제대로 읽어야 한다는 것을 다시 한번 느끼게 해주었다. 이 문제는 단순히 값으로 비교..
1. 문제 https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 2. 풀이 이분탐색을 이용하는 문제이다. 각각의 테스트 케이스 별로 A 배열과 B 배열이 주어졌을 때 선택 당해지는 배열인 B 배열을 정렬한 후 이분탐색을 진행한다. 탐색의 대상은 B 배열의 인덱스인데 이때의 핵심은 탐색이 끝났을 때 결과인 index 값이 선택된 A의 값보다 작은 B 요소의 개수라는 것이다. 탐색이 끝났을 때 B[in..
1. 문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 2. 풀이 이분 탐색을 활용한 문제이다. 문제를 해결하면서 탐색을 해야할 대상을 어떻게 잡아야 할지 생각을 해도 모르겠어서 다른 분들의 풀이를 참고하였다. 이 문제에서 탐색해야 할 것은 블루레이의 크기이다. 입력 값이 예제 입력 1과 같고 블루레이의 크기가 10이라고 가정해보자. 앞에서부터 레슨을 더해본다면 1 + 2 + 3 + 4 = 10 다음에 5를 더하면 15가 되기 때문에 하나의 블루레..
1. 문제 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 2. 풀이 이분탐색을 활용한 문제이다. 오랜만에 풀어서인지 개념이 기억나지 않아 찾아보던 중 좋은 분의 글이 있어서 참고하였다. https://www.acmicpc.net/blog/view/109 이분 탐색(Binary Search) 헷갈리지 않게 구현하기 개요 이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다. 이분 탐색 문제를 풀다보면 탈출 조건으로 lo
1. 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 2. 풀이 깊이 우선 탐색(DFS)의 응용이다. 큰 응용이 아니라 정답 비율이 높은 것 같다. DFS의 기본적인 내용은 아래의 포스팅을 참고하면 많은 도움이 된다. https://velog.io/@songyw0517/DFS%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80 DFS란 무엇인가? 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 ..
