Coding Test/BaekJoon

문제https://www.acmicpc.net/problem/14502 14502번: 연구소인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크www.acmicpc.net 접근법세로와 가로 크기가 최대 8이기 때문에 3중 for문을 사용해 벽의 위치를 선택해도 된다. 나는 for문이 아니라 재귀 함수를 사용했다. 3개의 벽 위치가 다 정해졌으면 BFS를 사용해 바이러스를 퍼트리고, 바이러스가 다 퍼진 후에는 안전 영역의 개수를 세어 현재 최댓값과 비교했다. 코드import java.io.BufferedReader;import java.io.IOException;import ja..

문제https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net 접근법연속된 수의 합을 보자마자 투포인터구나 하고 투포인터로 풀었는데 DP 문제였다. 그런데 채점현황을 보니 투포인터나 DP나 성능 차이는 크게 나지 않는 것 같다. 두 풀이 다 설명해보겠다. 투포인터기본적인 투포인터 문제는 sum의 크기에 따라 오른쪽 포인터가 가리키는 값을 더해주거나, 왼쪽 포인터가 가리키는 값을 빼주어야 하지만 이 문제는 다르다. 누적해서 더해주다가 sum이 음수가 되었을 때 sum을 ..

문제https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의www.acmicpc.net 접근법처음에 BFS로 풀면 되겠다 싶어 BFS로 풀어 통과를 했다. 그런데 채점현황을 보니 나만 메모리랑 시간이 장난아니게 컸다.. 심지어 처음에는 시간초과가 발생했다. 그래서 알고리즘 분류를 봤더니 DP를 사용하는 문제였다..!ㅋㅋ 두 풀이 다 설명해보겠다. BFSPipe 클래스를 하나 만들어 파이프가 시작하는 위치, 파이프의 방향을 변수로 가지도록 하였다. 그냥 BFS..

문제https://www.acmicpc.net/problem/1517 1517번: 버블 소트첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.www.acmicpc.net 접근법원래 세그먼트 트리 연습을 하려고 세그먼트 트리 문제를 고른거였는데 세그먼트 트리로 푸는 것보다 분할 정복으로 푸는게 훨씬 쉽다.. 세그먼트 트리는 다른 문제로 연습을 하는 것이 좋은 것 같다. 따라서 이번 글에서는 합병 정렬(분할 정복의 대표적인 예)을 사용해 푸는 것을 설명해보겠다. 과정{9, 1, 7, 4} 데이터 셋이 있을 때, 합병 정렬 과정은 아래와 같다.분..

문제https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽www.acmicpc.net 접근법쉬운 구현 문제이다. 동서남북~ 에서 BFS를 사용하라는 것을 대놓고 보여준다. 문제에서 주는 작동 방식을 정말 그.대.로 구현하면 된다. 주의할 점은 방향을 다루는 것인데 문제에서 제시한 방향은 0북 1동 2남 3서 이지만 반시계 방향으로 회전하는 것은 북->서->남->동 이기 때문에 잘 처리해주어야 한다. 나 같은 경우 dir 배열을 0..

문제https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)www.acmicpc.net https://st-lab.tistory.com/285 해당 게시물을 참고하였습니다.  [백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - JAVA [자바]https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가..

문제https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net 접근법이런 문제를 최장 증가 부분 수열(LIS)라고 한다. 그냥.. 나중에 아는척 하면 간지나는 상식!ㅎ.ㅎ 문제에 있는 예시를 그대로 따라해보다 보면 어떠한 방식으로 풀어야 될지 감이 온다. A[0]부터 A[5]까지 자기 자신까지의 최장 길이를 구해보자. 일단, 모두 적어도 가장 긴 증가하는 부분 수열의 길이는 1이다..

문제https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호www.acmicpc.net문제에서 자리 배정하는 과정을 그림으로 보여주고 있으니 보고오자 접근법N이 최대 20이기 때문에 이중 for문을 써도 괜찮다. 따라서 학생마다 모든 자리를 돌아보며 비어있는 자리를 우선순위 큐에 넣었고, 마지막에 하나만 꺼내서 자리를 배정했다. 자리를 나타내는 class를 만들고, compareTo() 함수를 오버라이딩해서 문제에서 제시하는 우선순위를 그대로 나타내주었다.   시간을 조금..