![]()
문제 출저 https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 문제 풀이 재료들의 번호가 주어집니다. 재료들의 고유 번호를 합쳐서 M이 되는 경우의 수를 구해야 합니다. 두 포인터를 이용해 풀었습니다. 재료들을 정렬합니다. start, end 두 개의 포인터를 사용합니다. start는 배열의 시작, end는 배열의 끝에서 시작합니다. 두 개의 합을 합쳐서 M 보다 작으면 start를 올리고 M보다 크면 end를 줄입니다. ..
![]()
문제 출저 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 문제 풀이 인식할 수 있는 알파벳의 종류 n과 문자열이 주어집니다. 문자열에서 인식할 수 있는 최대의 길이를 구해야 합니다. 투 포인터를 이용해 풀었습니다. 어떤 알파벳이 몇 개 나왔는지 세기 위한 int[] counts = new int[26]; 일차원 배열을 이용했습니다. 알파벳 갯수는 26개 이므로 배열의 크기를 26으로 설정했습니다. int start = 0, int end = 1 인 두..
![]()
문제 출저 https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 문제 풀이 -100,000,000 ~ 100,000,000 값을 갖는 용액이 n개 주어집니다. 두 개 용액을 섞어 0에 가장 가까운 값이 무엇인지 구해야 합니다. 투 포인터로 문제를 풀었습니다. int[] liquors 용액 배열에 입력값을 받습니다. Arrays.sort() 메소드를 통해 liquors int 배열을 정렬합니다. 처음과 끝은 두 개의 포인터..
![]()
문제 출저 https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 문제 풀이 성원이는 다이어트 중이다. 성원이의 현재 몸무게의 제곱 - 기억하는 몸무게의 제곱 = G 이다. 이 때 G를 만족하는 현재 몸무게를 구해야 한다. 투 포인터를 이용해 풀었습니다. long e : 현재 몸 무게 long s : 기억하는 몸 무게 이렇게 두 개의 포인터를 사용하여 e*e - s*s
![]()
문제 출저 https://www.acmicpc.net/problem/5076 5076번: Web Pages Input will consist of a number of lines of HTML code, each line containing from 0 to 255 characters. The last line will contain a single # character – do not process this line. Within the text of each line will be zero or more tags. No angle bracket will www.acmicpc.net 문제 풀이 String이 #이 나올 때까지 주어집니다. String이 HTML 태그 형식에 맞는지 확인해서 옳다면 leg..
![]()
문제 출저 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/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://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개의 길이를 비교해서 길이가..
![]()
목차 개념 크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용됩니다. 그래프에는 정점과 간선이 있는데, 간선에 가중치가 포함되어 있습니다. 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용합니다. 즉, 최소 신장 트리를 구하기 위한 알고리즘 입니다. 신장 트리와 최소 신장 트리 신장 트리(Spannging tree) 다음과 같이 정의합니다. 그래프에서 1) 모든 정점을 포함하고 2) 정점 간 서로 연결되어 있으며 싸이클이 존재하지 않는 그래프 (싸이클이 존재하는 않는 것은 tree 기본 조건) 예를 들어 아래와 같은 그래프가 있다고 가정해 보겠습니다. 여기서 나올 수 있는 신장..
![]()
목차 개요 순열 및 조합을 생성할 때 재귀적으로 구현하지 않고 각 인덱스 값을 비교하여 모든 경우의 인덱스 값을 뽑아내는 방법입니다. 현 순열에서 사전 순(오름차순)으로 다음 순열을 생성합니다. 즉 배열을 가장 작은 값으로 정렬한 뒤, 한 자리씩 swap 하면 서 출력합니다. 예시) 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 (가장 큰 값) 장점 재귀로 짜여진 순열과 달리 시간 복잡도가 낮습니다. (재귀적 호출이 없고 인덱스의 값만 교체해주므로) 순열과 조합을 함께 사용할 수 있습니다. 단점 원래의 배열을 재배열하여 순열을 만드므로 nPr 과 같이 특정 개수의 순열을 만들 수 없습니다. 구현 소스 배열을 오름차순으로 정렬합니다. (1, 2, 3...) (모든 탐색은 오른쪽에서 왼쪽으..
