![]()
문제 출저 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 문제 풀이 가장 긴 증가하는 부분 수열을 구해야 한다. 다만 n이 커서 for문 돌리기에는 시간 초과가 발생합니다. 시간 단축을 위해 이분 탐색을 도입해야 합니다. 이 문제는 부분 수열의 길이를 구하는 것으로 내용물은 몰라도 되는게 핵심입니다. int[] board 배열을 만들어 주어진 배열을 담았습니다. List list를 생성하여 부분 수열을 만들었습니다. 이 때 처음에 0을 넣는다..
![]()
문제 출저 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 풀이 스도쿠 판이 주어지면 빈 칸의 0에 숫자를 넣어 스도쿠 판을 완성시키는게 이 문제의 요구 사항 입니다. 백트래킹으로 모든 경우의 수를 대입하여 문제를 풀었습니다. 0의 자리에 1~9까지 숫자를 대입하며 스도쿠의 조건을 만족하며 계속해서 탐색해나가는 식으로 문제를 풀었습니다. 소스 코드 package baekjoon.backjoon9.day12; /* 스도쿠 https://ww..
![]()
문제 출저 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 풀이 별들의 좌표가 주어진다. 별들의 거리는 직각 삼각형 공식으로 구할 수 있다. 이 때, 모든 별들을 연결했을 때 가장 적은 거리가 무엇인지 구해야한다. 이 문제는 최소 스패닝 트리로 크루스칼 알고리즘으로 풀었다. 먼저 PriorityQueue pq를 선언하였다. 이 PriorityQueue는 두 별의 거리를 저장하는 용으로 거리를 오름차순으로 정렬했다. dot에는 int s, i..
![]()
문제 출저 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 풀이 용액의 양이 주어질 때 두 개를 섞어 0에 가까운 두 개의 용액을 찾는 것이 이 문제의 요구사항 입니다. 이 문제를 풀기 위해 투 포인터를 사용했습니다. 정렬된 배열에 처음(s)과 끝(e)으로 투 포인터가 시작됩니다. 두 개를 섞었을 때 0보다 크면 e-1 하여 값을 줄이고 0보다 작으면 s+1 하여 값을 키웁니다. 이것은 s가 e를 만날 기 전 까지 계속 반복합니다. ..
![]()
문제 출저 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 문제 풀이 정점의 개수(n)가 주어지고 정점을 잇는 선분(m)이 주어집니다. 이 때, 사이클이 몇 번째 순서에서 이루어지는지 구하는게 이 문제의 요구 사항입니다. 이 문제를 풀기 위해 Union-Find를 도입했습니다. 선분이 주어지면 각 시작과 끝의 부모를 비교하여 부모가 같으면 사이클이 이루어진거여서 순서를 저장하고 출력합니다. 부모가 같지 않다면 부모를 같게 만들어줍니다. 이..
![]()
문제 출저 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 풀이 (0,0) 지점에서 (n-1, n-1) 지점까지 이동하는데 0타일을 1타일로 바꾸는 갯수의 최소값을 구하는게 이 문제의 목표이다. (0,0) 을 시작으로 BFS 탐색을 진행했다. 이 때, int[][] count 라는 2차원 배열을 만들어 이 지점을 지날 때 타일의 바꾼 횟수의 최소값을 계속 갱신하게 했다. 즉, count 배열에 기존에 기록된 값이 작아야 탐색을 계속 할 수..
![]()
문제 출저 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제 풀이 한 지점에서 허용 범위(m) 이내에서 가장 많은 아이템을 얻을 수 있는지를 구하는 문제였다. 이 문제를 풀기 위해 다익스트라 알고리즘을 활용했다. BFS로 노드를 탐색하지만 visited로 방문 체크를 하여 한 번만 방문하는게 아니라 여러 번 방문해도 이전에 방문한 것 보다 더 적은 비용으로 방문하면 계속 탐색을 이어나가는 것 이다. 이러한 탐색 과정을 모든 정점에서 시행하였고 가..
![]()
문제 출저 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 풀이 트리가 주어지고 이 트리의 전위 순회, 중위 순회, 후위 순회 했을 때 결과를 출력하는게 이 문제의 요구 사항이다. 트리를 저장하기 위해 Node라는 클래스를 만들어 left, right를 저장했다. 이 노드의 연결 정보는 Map nodeMap 형태로 저장했다. 순회를 구하는 방법은 재귀 함수를 사용했다. 재귀 함수로 노드를 이동하고 적절한 시기에 StringBui..
![]()
문제 출저 https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 문제 풀이 0과 1이 주어진 숫자판에서 0을 1로 바꿨을 때 1이 이어진 가장 큰 넓이가 무엇인지 구하는게 이 문제의 요구사항이다. 숫자판을 입력 받을 때 0을 저장하는 zeroQue를 만든다. 또한 1이 이어진 영역의 넓이를 구하기 위해 BFS를 사용한다. 이 때 인덱스를 부여하여 탐사간 마친 1의 영역은 인덱스 번호로 바꾼다. Map areaMap을 만들어 인덱스에 따른 ..
![]()
문제 출저 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 풀이 도시의 갯수 n이 주어지고 도시에서 도시로 이동하는 경로와 비용을 제공하는 정보가 m개 주어진다. 이 때, 모든 도시에서 다른 도시로 가는 비용의 최솟값을 구하는게 이 문제의 목적이다. 시작 도시를 넣으면 시작 도시에서 다른 도시로 가는 최소 비용을 구하는 함수인 search를 만들었다. search는 BFS를 이용하여 탐색을 진행했고 answer 배열에 최소 비용을 기입했다..
![]()
문제 출저 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 풀이 수빈이의 위치에서 동생까지 가는 시간을 구하는게 이 문제의 목표이다. 수빈이는 1초 후에 현재 위치에서 +1, -1 가거나 0초 후에 현재 위치*2인 위치로 이동할 수 있다. 범위는 0, 100000이므로 십만개의 칸을 가진 int 배열을 생성하고 해당 위치에 몇 초 후에 도착하는지를 저장한다. BFS로 시작 위치 n을 시작으로 탐색을 진..
![]()
링크 https://softeer.ai/practice/info.do?idx=1&eid=624&sw_prbl_sbms_sn=246435 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 전광판의 숫자가 변할 때 몇 개의 전등의 스위치를 눌러야 하는지를 구해야 합니다. 이 때 전광판의 한 글자의 전등은 7개로 구성되어 있습니다. 먼저, 이 7개의 전등의 임의의 순서를 부여하여 어떤 숫자가 몇 번 전광판을 눌러야 하는지를 2차원 배열로 저장했습니다. 그 후 숫자 2개를 String으로 입력받았습니다. String으로 받은 이유는 한 글자씩 비교하기 편했고 자릿수 차이로 인해 불이 꺼진 전광판을 N 으로 구분하기 위해서 였습니다. 숫자 2개의 길이를 비교해서 길이가..
