Problem Solving

문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 먼저 맵의 CCTV 좌표(x,y), 타입 정보를 저장하였다. 1번 카메라는 한쪽 방향만 감시할 수 있다. 2번 카메라는 (좌, 우), (상, 하) 방향을 감시할 수 있다. 3번 카메라는 (상, 우), (우, 하), (하, 좌), (좌, 상) 방향을 감시할 수 있다 4번 카메라는 (좌, 상, 우), (상, 우, 하), (우, 하, 좌), (하, 좌, 상) 방향을 감시할 수 있다..

문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 풀이 분할정복을 이용하는 전형적인 문제 처음에 좌표 r, c 의 순서를 구할 때 좌표 r,c 가 속해있는 사분면까지 순서를 모두 구했는데 시간 초과가 발생하였다. 이 문제는 구하려는 좌표가 1,2,3,4 분면 어느곳에 위치한지 먼저 파악한 후에 사분면 1개의 크기가 1이 될때까지 좌표 r,c의 사분면을 구하면서 이전 사분면들의 크기를 모두 더하면 된다. 재귀를 이용하여 각 사분면을 ..

문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 트리 구조를 만들고 노드를 삽입하여 전위, 중위, 후위 탐색하여 출력하는 문제다. 전위 : 루트 -> 왼쪽 -> 오른쪽 중위 : 왼쪽 -> 루트 -> 오른쪽 후위 : 왼쪽-> 오른쪽- > 루트 순으로 탐색한다. 이를 코드로 구현하면 다음과 같다. (트리의 탐색은 추후 링크로 대체 예정) import java.io.BufferedReader; import java.io.Buff..

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 도시의 지도 데이터를 입력받으면서 치킨집 좌표와 집 좌표를 list자료형에 입력하였다. 문제에서는 치킨집 개수 M개 일 때 치킨집 거리와 집 거리의 합들이 최소가 될 때 그 길이를 구하는 것을 요구한다. 처음에 치킨집의 좌표를 조합으로 출력하여 각 치킨집이 해당 위치에 있을 때 BFS탐색을 통해 집까지의 거리를 구하려고 했다. 그러나 이렇게 하면 너무 오래 걸릴 뿐..

문제 문제링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 문제를 잘 읽어보지 않아 시간이 오래 걸린 문제... 문제에서 예제로 재료가 4개일 때 선택된 재료 2개와 선택되지 않은 재료 2개의 시너지를 각각 비교하여 두음식간의 맛의 차이가 가장 작은 것을 구하는 것으로 예시를 들었다. 그래서 조합으로 N개의 재료중에서 2개를 뽑아서 시너지를 구하려고 하였다. 그런데 음식 재료가 4개가 아닌 값이 N개의 재료가 들어왔을 때 N/2 의 재료를 사용하여 선택되지 않은 나머지 재료를 N/2와 비교하는 문제였다. 즉, N_C_N/2 경우의 수에서 시너지를 구하는 문제다.. 코드는 다음과 같다. import ja..

문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 다른 사람은 어떻게 느꼈을지 모르겠지만 본인에게는 어려웠던 문제 특히 "배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다." 라는 조건을 어떻게 해야할지 감이 잡히지 않았음. 우선순위 큐를 생성하면서 비교 조건을 절대값이 같을 때 음수 -> 양수 로..

문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 크게 두가지 방법으로 풀 수 있다. 하나는 반복문과 재귀를 사용하여 나머지 하나는 DP를 사용하여 풀었다. 오히려 DP를 사용하는 것이 반복문보다 많은 시간이 걸렸다. 반복문 이용 public class BOJ_2839_Sol1 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedRe..

문제 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 분할정복 문제를 많이 풀어보지 않아 꽤 어려워 솔루션을 참고한 문제.. 핵심은 전체 N크기를 2등분씩 하면서 1,2,3,4 분면씩 나누어 분할 탐색하는 것이 포인트 처음에 해당 사분면의 r,c 값과 r+size, c+size까지 돌면서 흰색인지, 파란색인지 체크하면된다. 만약 size크기만큼 탐색하면서 처음 temp에 넣었던 값과 다른값이 나온다면 boolea..

문제 http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=99&sfl=wr_subject&stx=%EB%83%89%EC%9E%A5%EA%B3%A0 JUNGOL www.jungol.co.kr 풀이 전형적인 그리디 문제 N개씩 최저 보관 온도 xi와 최고 보관 온도 yi 가 입력된다. 문제에서는 모든 화학물질을 보관할 수 있는 냉장고의 수를 구하는 것이 목적이다. 문제 접근 방법은 다음과 같다. 최고온도 yi를 기준으로 오름차순 정렬한다. (xi, yi 배열 ) 첫번째 화학물질의 최고온도를 maxDegree라는 변수에 할당한다 두번째 화학물질 부터 최저온도와 maxDegree값을 비교한다. 만약 최고온도 maxDegree와 다음 화학물질 ..

1. 순열(Permutation) 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현할 수 있다. 수식으로 나타내면 다음과 같다. 위 식을 간략화 하면 다음과 같다 순열 만드는 방법으로 반복문과 재귀문을 활용한 방법이 있다. 먼저 반복문으로 순열을 구하는 방법은 다음과 같다. 기존 수와 중복되지 않게 숫자를 한 개씩 뽑는 일을 가능한 모든 수에 대해 반복해서 시도한다. 목표하는 횟수만큼 "1"을 반복 (뽑는 횟수가 고정되어 있다면 목표하는 횟수까지 돌아가는 반복문으로 해결할 수 있지만, 정해지지 않았다면 뽑는 횟수만큼 재귀적으로 호출하는 구조를 이용하는 것이 적합할 수 있다.) (여기를 참고) 아래 코드는 반복문을 이용해 배열의 원소를 sw..