공부공간

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다. www.acmicpc.net 두 용액은 이전 포스트 https://algorithmstudy-mju.tistory.com/120 BOJ - 2003 ) 수들의 합 2 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 위상정렬과 다이나믹프로그래밍(약간?)이 결합된 문제이다. 빌드와 시간이라는 개념이 등장하여 1 ->2 ->3 , 11->10->3 의 노드 연결정보에서 3의 진입차수가 0 이될때 1->2 / 11->10의 비용중 큰것을 골라야지 다른 빌드에서 걸리는 시간을 커버하면서 진행 할 수 있다. 중간중간 첫 건물이 목표건물인 경우와같이 예외사항을 처리해주면서 진행하면 풀리는 문제.. 위상정렬을 DF..

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투포인터 알고리즘 (Two-Pointer Algorithm)은 배열에 특정 구간에 대해 접근하여 처리할 경우, 시간복잡도를 O(n^2) 에서 O(n) 까지 단축하는 알고리즘이다. 사실 알고리즘 자체는 어렵지 않다. 문제에서 원하는 특정 값을 m이라할때 배열의 인덱스를 가리키는 두개의 포인터변수를 선언한다. 그리고 특정 값보다 크면 첫번째 포인터변수를 증가시키고, 작으면 ..

https://www.acmicpc.net/problem/2234 2234번: 성곽 문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로� www.acmicpc.net 주어진 맵에서 성곽의 크기를 구하면서 벽하나를 제거해서 합친 면적중 가장 큰 값을 찾는 문제이다. 성곽의 크기를 구할때 이미 각 면적의 합을 구하고 인접여부만 CHECK배열로 확인해 준다음 인접해있다면, 두 면적을 합친값 중 가장 큰 값을 답으로 선택한다. 다음 BFS진행시에 비트연산을 해주어야하는 신박한 문제 :) import java.io.BufferedReader; import java.io.Inpu..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 외판원순회(TSP)문제는 한지점에서 출발해 모든 노드를 거치고 다시 시작위치로 돌아오는 문제를 말한다. 그 중 최소 비용을 출력하는 것이 이번 외판원문제2이다. 백트래킹을 이용하여 미리구한값보다 크다면 더이상진행하지않는다. 문제에서도 알수 있듯이, MAP[I][J]값이 0이면..

https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다. 외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 www.acmicpc.net MAP에서 X를 순서대로 방문한 경로중 가장 짧은 것을 출력하는 문제이다. X의 방문에 순서가 있으므로, NextPermutatio..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다. 마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출 www.acmicpc.net (1,1)에서 (N,M)이동할때 마검 그람을 얻으면 모든벽을 부수면서 진행할 수있는 문제이다. 벽부수고 이동하기처럼, 방문처..

https://programmers.co.kr/learn/courses/30/lessons/62050 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 특정높이 이하로 움직일 수있는 공간에 mark를 남겨주고 이 mark만큼 크루스칼알고리즘을 적용하여 간선의 최솟값만큼만 노드들을 연결할 수 있게 해준다. 사실 pq에 1->2 가는 노드와 2->1 가는 노드가 같은것인데 들어있어서 비효율적일것같다. import java.util.ArrayDeque; import java.util.Comparator; import java.util.PriorityQueue; c..