밤이 블로그

카카오 코드 페스티벌 예선 - 캠핑 문제 해설 (Java) 이 문제는 n이 5000이므로 O(N^2)으로 풀어야 합니다.N^3으로 풀 수 있습니다만,, 최적화 과정이 들어가야 통과됩니다. 문제 출제 목적에 맞게 O(N^2)으로 푸셔야 맞습니다. (문제는 프로그래머스에서 다시 풀 수 있습니다.) O(N^2)의 해법은 다음과 같습니다. 1. 세그먼트 트리 개념과 비슷하게 주어진 범위의 직사각형 내부에 쐐기가 몇개 있는지를 먼저 구해놓습니다. -> O(N^2) S[i][j] : (0, 0) ~ (i, j) 범위의 직사각형 내부에 존재하는 쐐기의 개수 2) 그리고 모든 쐐기의 쌍에 대하여 -> O(N^2) 미리 구해놓은 S 배열의 값을 검사하여값이 0인 경우 (내부에 쐐기가 없음) 텐트를 설치할 수 있음을 쉽게..

Kakao 카카오 블라인드 채용 - 1차 코딩 테스트 - 6, 7번 코드는 프로그래머스에 문제 공개되면 다시 채점해보고 코드 올리도록 하겠습니다. - 4번 문제도 채점은 다시 해봐야되는데 틀린 점이 없어보여서 일단 올려봅니다. 잘못된 점 있으면 댓글 부탁드립니다. - 5번 문제는 너무 급하게 풀어서 불합리한 부분이 있을 수 있습니다. 댓글 달아주세요. 1번 문제. 비밀 지도/** * 카카오 Test#1_1 비밀지도 */ public class Main { public static void main(String[] args) { int n = 5; int[] arr1 = { 9, 20, 28, 18, 11 }; int[] arr2 = { 6, 1, 21, 17, 28 }; String[] map = sol..

카카오 모의 테스트 문제(Java) 문제 풀어본거 코드 올려봅니다. 궁금하신 점이나 코드에서 고쳐야할 부분이 있다면 댓글 달아주세요. * 문제 1, 2, 3 : 쉬움* 문제 4, 5, 6, 7 : dp 문제 * 문제 5- 재귀 형태로 풀이 시 (Java) 효율성 테스트 실패, 바텀업 방식으로 풀이 시 효율성 테스트 성공. 두 경우 걸리는 시간은 비슷함.(두가지 방식의 코드 모두 올려놨습니다) - 제가 올린 바텀업 코드에서 메모리를 더 많이 절약할 수 있습니다. dp배열을 [100001][4]로 선언하지 않아도 됩니다. * 문제 7- 문제 7번의 경우에도 재귀 형태로 풀이 시 (Java) 효율성 테스트 실패. 문제 #1/** * 자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 sol..

a^3 + b^3 = c^3 + d^3 을 만족하는 100 이하의 자연수를 모두 찾아보자 a, b, c, d는 자연수이므로 a^3 + b^3의 결과도 어떤 자연수 x로 표현할 수 있다. 즉, 아래와 같이 표현할 수 있다. a^3 + b^3 = c^3 + d^3 = x 다시 바꾸어 말하면, 어떤 자연수 x는 위 조건을 만족하는 두 자연수의 쌍의 집합으로 표현할 수 있다. a^3 + b^3 = c^3 + d^3 = x1 [(a11^2 + b11^2), (a12^2 + b12^2), ...] = x2 [(a21^2 + b21^2), (a22^2 + b22^2), ...] = x3 [(a31^2 + b31^2), (a32^2 + b32^2), ...] = ... 이제 우리는 위 형태의 자료구조를 만들고 집합의 ..

알고리즘 공부 리스트 및 순서 (Algorithm Problem Solving Roadmap) 제 Github 계정입니다. 많이 놀러오세요~https://github.com/stack07142/BOJ ▼ 대충 어떤 것들을 공부해야하는지 그려보았습니다. 잘못된 정보가 있을 수 있으니 참고해주시고, 고칠 점 있으면 댓글 남겨주세요. Inspired Byhttps://github.com/kamranahmedse/developer-roadmaphttps://github.com/godrm/mobile-developer-roadmaphttp://blog.naver.com/wnsgh224/220897329629

세그먼트 트리(Segment Tree, 구간 트리) ■ 구간에 대한 질문에 효율적으로 대답하는 것■ Segment Tree는 저장된 자료들을 적절히 전처리하여 그들에 대한 질의에 빠르게 대답할 수 있도록 한다.■ 구간 트리의 핵심 아이디어는 주어진 배열의 구간들을 표현하는 이진트리를 만드는 것 전처리하는게 핵심인 것 같습니다. 만약 구간의 최소값을 여러번 구하는 것이 목적이라면, 그 목적에 맞게 전처리하여 구간 트리를 구현하는 것입니다.그리고 그 구간 트리는 해당 구간의 최소치를 각 노드에 저장할 것입니다. 예) 길이 5인 배열을 표현하는 구간 트리가 저장하는 구간들 [0, 4][0, 2] [3, 4] [0, 1][2] [3][4] [0][1] ■ Heap 자료구조와 마찬가지로 일차원 배열로 표현하는 것..

BOJ#4307 개미 * 문제https://www.acmicpc.net/problem/4307 * 풀이 쉬운 문제입니다.(개미의 속도가 모두 같기 때문에) 저는 막대의 중간에서 가장 가까운점, 가장 멀리 있는 점을 구해서 최대/최소 시간을 구했습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/a4b77ff3f9b58feceb146cac9d85601a166cb545/BOJ%234307_Ant/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BOJ#4307 개미 * https://www.acmicpc.net/problem/4307 */ public class Main { public st..

import Foundation let input : String = readLine()!; var idx : Int = 0 while idx + 10 < input.characters.count { var startIdx = input.index(input.startIndex, offsetBy: idx) var endIdx = input.index(input.startIndex, offsetBy: idx + 10) let range = startIdx ..< endIdx print(input.substring(with: range)) idx += 10} var startIdx = input.index(input.startIndex, offsetBy: idx)var endIdx = input.endInd..

import Foundation let n : Int = Int(readLine()!)!var sum : Int = 0 for index in 1...n { sum += index} print(sum)

import Foundation let input : String = readLine()!;let inputArr = input.characters.split(separator: " ").map({Int(String($0))!}) var sum = 0 for number in inputArr { sum += number} print(sum)