본문 바로가기

전체 글

 (124)
Codility MinMaxDivision 풀이 (Java) 최대값이 M인 배열 A가 인풋으로 들어온다. 우리는 K개의 배열 A를 K개의 그룹으로 나누고 각 그룹의 합의 최대값을 최소로하도록 만드는 문제이다. 카테고리가 Binary Search이기 때문에, 이분 탐색을 써서 풀 수 있는 문제라는 것을 알 수 있다. 각 그룹의 최대값을 이분탐색을 통해서 찾아주면 된다. l = 0, r = M * A.length 로 설정해준다. r을 M * A.length로 설정한 이유는 배열의 각 원소의 최대값이 M이기 때문이다. sum이라는 변수를 만들어 각 그룹의 합을 저장하고, sum이 mid값보다 커질 때는 새로운 그룹을 만드는 것으로 코드를 작성한다. mid값은 새로운 그룹을 만드는 구분자로 사용되며, 정답과는 다른 값이다. 그룹의 개수가 K보다 크게 된다면, mid값이 ..
브롤스타즈 전투기록 JSON Parsing 하기 (Java) 브롤스타즈 개발자 사이트에서 battleLog를 가져오는 API를 호출해보고 어떤 JSON 포맷으로 가지고 오는지 확인한다. developer.brawlstars.com/ Brawl Stars API Let's get constructive with the Brawl Stars API! Build amazing experiences with access to accurate and secure game data. developer.brawlstars.com items 라는 field에 List의 형태로 각 전투기록들이 들어오는 것을 확인할 수 있다. 먼저 Request를 보내어 String 형태로 가져온다. public class APITest { @Test public void getBattleLog(..
백준 2075번 N번째 큰 수 (c++) N*N (N > n; for (int i = 0; i > arr[i]; } sort(arr, arr + n * n); cout > n; // 2. priority queue 풀이 priority_queue pq; for (int i = 0; i > input; pq.push(input); } //상위 n개만 남긴다. while (pq.size() > n) { pq.pop(); } } cout
백준 1774번 우주신과의 교감 (c++) 모든 우주신들을 연결하는데, 연결하는 통로의 길이를 최소로하는 문제이다. 모든 우주신들을 각각 vertex로 보고, 모든 우주신들을 연결하는 Edge를 만들면, Minimun Spanning Tree를 찾는 문제로 해석할 수 있다. MST는 Union and Find를 이용한 크루스칼 알고리즘을 이용하여 해결할 수 있다. 크루스칼 알고리즘의 시간 복잡도는 O(elog(e)) 인데, 우리는 모든 우주신들이 연결되어 있다고 가정하므로 e = (n -1)n / 2 이 된다. n의 범위는 n x = x; this->y = y; this->dis = dis; } }; struct cmp { bool operator()(Edge &t, Edge &u) { return t.dis > u.dis; } }; double..
백준 2638번 치즈 (c++) 외부 공기와 2칸이상 접속한 치즈는 다음 시간에 사라지게 된다. 내부 공기와 외부공기를 구분하는 코드를 짜주어야한다. 문제의 조건에서 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는다고 주어졌다. 이 말은 외부의 공기는 가장자리를 시작으로 모두 연결되어 있다고 생각할 수 있다. 그래서 (0,0)에서 DFS를 실행하여, 외부 공기를 모두 방문하고 이를 구분할 수 있는 값으로 바꿔준다. 그런 후에 모든 치즈를 확인하면서 외부 공기와 맞닿아 있는 치즈를 지워주면 된다. 현재의 모눈종이 상태를 map[110][110] 에 저장하여 관리하고, 다음 모눈종이의 상태를 nMap[110][110]에 저장하여 계속 업데이트 하는 과정을 치즈가 없어질 때까지 반복한 후에 얼마나 시간이 걸렸는지 출력하면 된다. #includ..
백준 1967번 트리의 지름 (c++) 트리에서 가장 멀리 떨어진 두 노드를 찾는 문제이다. 다익스트라를 2번 사용하면 지름을 구할 수 있다. #include #include using namespace std; #define MAX_NODE 10010 #define MAX_NUM 10000000 int dist[MAX_NODE]; vector node[MAX_NODE]; int n; void dij(int start) { priority_queue pq; pq.push({0, start}); for (int i = 0; i < MAX_NODE; i++) { dist[i] = MAX_NUM; } dist[start] = 0; while (!pq.empty()) { pair top = pq.top(); pq.pop(); int cost = -t..
지뢰 찾기 for Web JavaScript로 구현한 지뢰찾기 입니다. 플레이 방법 마우스 우클릭 또는 오른쪽 위(깃발) 후 터치 : 깃발을 세움 마우스 좌클릭 또른 오른쪽 위(폭탄) 후 터치 : 칸이 열리며 지뢰를 찾음 얼굴 클릭 : 게임 초기화 왼쪽 위 : 상위 10개의 기록을 보여줌 즐겁게 플레이 하세요~ 000 000 × No Date Time
백준 1030번 프렉탈 평면 (JavaScript) 1초마다 가로세로가 N배씩 커지고 가운데 K*K개는 검은색으로 칠해진다. 이를 0초일 때부터 차곡차곡 블럭을 붙이면서 만들게 되면, O(N^s) 만큼의 시간복잡도와 공간복잡도를 가지게 된다. N는 최대 8이고 s는 최대 10이다. (2^3)^10 = 2^30 = 10^9 인데, 0,1을 1byte로 저장한다면 1GB의 공간이 필요하게 된다. 그래서 전부다 계산하는 것은 비효율적이고 문제의 128MB메모리 제한에 걸리게 된다. 그래서 역으로 x,y 좌표의 프렉탈 평면의 값이 무엇일지를 계산한다. find함수 내에서 하는 것이 바로 그 일이다. 먼저 복사 되기 이전의 가로길이(beforeWidth)를 구하고, n과 k를 이용해 x,y가 검은색으로 칠해지는 범위에 있는 값인지 확인한다. 만약 범위 안이라면 1..

티스토리툴바