1. 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 2. 풀이 그리디 알고리즘과 정렬 알고리즘으로 분류되어 있는 문제이다. 처음에는 회의 시작 시간과 회의시간(종료시간 - 시작시간)을 클래스로 만들고 회의 시작 시간으로 정렬한 후 회의 시간이 가장 적은 것부터 개수를 세려고 했는데 잘못된 방법이었다. 이 문제의 핵심은 회의 종료시간을 기준으로 정렬한다는 것이다. 이해를 돕기 위해 한 블로그 분의 정리된 글에서 사진을 인용하였다. 이 사진은 입력으로 주어진 회의 시간을 종료 시간에 맞춰 오름차순으로 정렬한 것이다. 단!! 이 예제에서는 종료 시간이 같은..
1. 문제 https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 2. 풀이 간단한 문자열 문제이다. 첫 번째 줄 입력을 input으로 받고 두 번째 줄 입력을 search로 받는다. 그 후 input안에 search가 있으면 replace 함수를 이용하여 다른 문자로 교체한다. 이때 문제에서 주어졌듯이 입력으로는 알파벳 소문자와 공백이 주어지므로 이를 제외한 문자 아무거나로 교체한다. 그리고 input을 인덱스 하나씩 탐색하면서 교체한 문자가 있으면 cn..
1. 문제 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 2. 풀이 시뮬레이션 문제이므로 문제에서 주어지는 시나리오 대로 문제를 해결하면 된다. 문제를 처음에 보고 큐와 비슷하다고 생각했다. 그런데 처음엔 큐를 사용하지 않고 List를 사용하여서 문제를 해결하려 했는데 시간초과가 발생했다. 탐색을 여러 번 해야 하고, 불필요한 반복의 호출이 많아서 발생했다고 추측한다. 시간 초과 발생 후 다시 ..
1. 문제 https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 2. 풀이 시뮬레이션 문제로 시나리오 그대로 코드를 작성하면 된다. 우선 예제 입력 1에서 3번째 줄을 살펴보자. 3번째 줄 입력은 추천 받은 학생을 나타내는 번호가 빈칸을 사이에 두고 있다. 그렇다면 사진틀을 하나의 객체 참조 변수로 본다면 안에 들어가는 인스턴스는 어떻게 될까? 바로 추천 받은 학생, 추천수이다. 그래서 static class로 추천 받은 학생의 이름과 추천..
1. 문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 2. 풀이 백준 알고리즘 분류에 다이나믹 프로그래밍(DP)로 분류되어 있는 문제이다. 이 문제에서는 N이라는 크기가 주어질 때 "00" 타일과 "1" 타일로 만들 수 있는 경우의 수를 구하는 문제이므로 dp[N] = 만들 수 있는 경우의 수로 설정했다. (1) N = 1 - "00"은 최소 크기가 2이므로 사용할 수 없고 "1" 하나만 사용할 수 있다. - dp[1] = 1 (2) N = 2..
1. 문제 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 2. 풀이 DFS로 문제를 해결하였다. 주어진 1과 0을 2차원 배열에 넣었다고 가정한다면 문제에서 말하는 가장 바깥쪽은 배열의 첫번째 행, 가장 안쪽은 배열의 마지막 행이된다. DFS를 돌릴 때 Main 함수에서 배열의 첫 번째 행을 반복으로 돌리면서 DFS를 탐색해주고 DFS 함수 안에서 탐색을 진행하던 도중 인자로 받은 x 값이 마지막 행에 도착..
1. 문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 2. 풀이 이분탐색을 활용한 골드V 문제이다. 문제를 풀면서 이분탐색의 Upper_bound, Lower_bound가 정확히 기억이 나지 않아 글을 찾아보면서 문제를 해결했다. https://blog.naver.com/bestmaker0290/220820005454 알고리즘 기초 - Lower Bound & Upper Bound Low..
1. 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 2. 풀이 백 트래킹 및 탐색을 이용하여 푸는 문제이다. 백 트래킹에 대한 내용이 기억이 나지 않아서 잘 정리된 블로그 포스팅을 참고하였고 다른분의 풀이를 참고하였다. https://iseunghan.tistory.com/241 알고리즘 - 백트래킹(Back-Tracking) 백트래킹 이란? 백트래킹은 모든 조합의 수를 살펴보지만, 조건이 만족할 때만 살펴보기 때문..
