백준

https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 사용한 알고리즘 : LIS, 이진탐색 풀이 전략 위 문제에서 주어진 예제를 그대로 사용할 때, 앞 A 전봇대를 오름차순으로 정렬하고 B 전봇대를 기준으로 LIS를 구하면 [3,6,7,9,10] 이라는 결과가 나옵니다. 따라서 (처음 입력받은 전깃줄의 개수) - (LIS로 구한 배열의 크기)를 구해 제거해야 할 전깃줄의 개수를 구할 수 있습니다. 하지만 문제에서 제거해야할 전깃줄의 개수와 전깃줄..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net [문제 유형 : 구현] 📌구현할 기능 목록📌 1. 지도의 크기(N)와 경사로의 길이(L)를 입력받는다. 2. 지도의 각 위치별 높낮이를 입력받고 2차원 배열에 저장한다. 3. 지도에서의 한 열을 1차원 배열로 변환시켜줄 수 있는 메서드를 작성한다. 4. 매개변수로 전해받은 1차원 배열에 대해서 경사로를 사용해 지나갈 수 있는지 검사하는 메서드를 작성한다. - 아래의 3가지 경우를 생각하여 구현 로직을 달리한다. 1) 이..

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 📌구현할 기능 목록📌 1. 파이어볼 객체를 구현할 클래스를 작성한다. - 행 위치, 열 위치, 질량, 속도, 이동방향 값을 저장할 필드를 가진다. 2. 각 위치를 나타내는 격자를 N x N 크기의 삼중 ArrayList로 생성한다. - ArrayList map = new ArrayList(); - 마지막 ArrayList에서 Fireball 객체를 저장하면서..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 사용한 알고리즘 : 백트래킹, DFS를 통해 구현한 조합, 구현 풀이전략 문제에서 핵심은 기존의 모든 치킨집들 중에서 M개의 치킨집만 남겼을 때, 가장 최소의 치킨 거리를 구하는 것이다. (치킨 거리란 모든 가정집에서 남김 특정 치킨집까지의 최소 거리 합을 뜻한다.) 1. 조합을 사용해 모든 치킨집들 중 M개의 치킨집을 선정한다. 2. 각 가정집에서 조합으로 구한 M개의 치킨..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 사용한 알고리즘 : DP 풀이전략 DP 문제를 풀 때, 보통 맨 처음 입력으로 주어진 값을 시작으로 반복성을 찾아낸다 하지만, 이 문제에서는 입력의 맨 뒤부터 반복성을 찾아야 풀 수 있는 문제이다. 위 표는 문제에서 주어진 1번 예제 입력을 대입했을 경우, 얻을 수 있는 최대 수익을 나태는 표이다. d[i]는 i~N일 사이에 얻을 수 있는 최대 수익을 뜻한다. (예로 d[3]은 3~7일 사이에 얻을 수 있는 최대 수익을 뜻함) 이 문제는 입력의 맨 뒤부터 시작하여 반복성을 찾아야 한다고 했는데, 아래와 같은 반복성을 띈다. 7일 : ..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 사용한 알고리즘 : DFS, 백트래킹, 시뮬레이션(구현) 풀이전략 문제 풀이 핵심 키워드는 아래 2가지다. 1. DFS를 통해 모든 경우의 수를 중북 순열로 완전 탐색을 진행한다. 2. 상하좌우 이동 시, 변경된 상태를 나타내는 2차원 배열을 원래 블록판 상태를 나타낸 2차원 배열의 내부 값 변경을 통해 구하면 시간 초과가 발생한다. 따라서 별도의 배열을 생성하고, 생..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 사용한 알고리즘 : 위상정렬(Topological_Sort) 풀이전략 문제는 연출자들이 정한 가수의 출연 순서를 모두 만족시키는 공연 순서를 출력하는 것이 목표로 대표적인 위상정렬 알고리즘을 통해 해결이 가능한 문제이다. 위상정렬 : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 위와 같은 방향 그래프가 주어졌을 때 이를 위상 정렬로 나..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 사용한 알고리즘 : 분리 집합, DFS 풀이 전략 문제에서는 회원들이 발판을 따라 움직인다고 할 때, 회원들이 반복되는 싸이클로 인해 계속해서 발판을 움직이며 돌지않고 중간에 멈출 수 있도록 SAFE ZONE을 만드려고 한다. 이 때 이를 만족시킬 수 있는 SAFE ZONE의 최소 개수를 구하는 것이 목표이다. 풀이 방법이 여러가지 있겠지만, 나는 분리 집합과 ..

https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 사용한 알고리즘 : MST(최소 스패닝 트리) 풀이 전략 전형적인 최소 스패닝 트리를 사용한 문제이다. 그래프의 모든 간선들 중에서 비용이 가장 적은 간선을 하나씩 더해간다. 단, 더해가는 과정에서 싸이클이 발생하지 않아야하며 최종적으로는 모든 정점들이 이어져야 한다. 문제에서 주어진 예제 입력2를 그림을 통해 설명해보겠다. 위 예제에서는 작은 순서 그대로 추가해도 싸이클이 생기는 문제가 없었다...

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 사용한 알고리즘 : 자료 구조(List) - 구현 문제 풀이전략 이 문제에서 가장 신경써야할 부분은 명령어로 'R'이 주어졌을 경우 배열을 뒤집느냐 뒤집지 않느냐이다. 만약 'R' 명령이 들어올 때마다 배열 뒤집기를 실행한다면 최악의 경우 시간 복잡도는 아래와 같다. 배열에 들어갈 수 있는 수는 최대 100,000개이고 명령어의 길이 또한 최대 100,000번이 가능하다. 배열 내부의 수가 100,000개 일 때, 'R'로 인해 뒤집기 연산을 수행하면 ..