전체 글

전체 글

    [java] 프로그래머스 (가장 큰 정사각형 찾기) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (가장 큰 정사각형 찾기) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr Approach 이 문제는 백준 1915번 가장 큰 정사각형 문제와 유사하다. 아래는 내 풀이에 대한 포스팅이다. 2021/01/13 - [Algorithm/Baekjoon Online Judge] - [java] 백준 1915 (가장 큰 정사각형) Gold 5 [java] 백준 1915 (가장 큰 정사각형) Gold 5 Problem : https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 ..

    [java] 프로그래머스 (쿼드압축 후 개수 세기) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (쿼드압축 후 개수 세기) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr Approach 일단 이 문제는 백준 1992번 쿼드트리와 유사한 문제이다. 백준 문제의 내 풀이는 다음 링크로 가면 된다. java 백준 1992 (쿼드트..

    [java] 백준 9019 (DSLR) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 9019 (DSLR) Gold 5

    Problem : https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net Approach BFS + DP + Tracing 을 사용하여 풀이한 문제이다. 필자는 위의 과정보다 숫자를 만드는 작업이 더 어려웠다.(어렵다기보다 생각할 조건들이 많아서 귀찮았다.) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다. S: S ..

    [java] 백준 9252 (LCS 2) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 9252 (LCS 2) Gold 5

    Problem : https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net Approach LCS(Longest Common Subsequence) 문제로 DP로 풀이가 가능한 문제이다. 배열은 DP[s1.length + 1][s2.length + 1] 으로 선언하여 두 문자열을 각각 한 문자씩 비교해 나간다. DP[i][j] 는 s1.charAt(i)와 s2.charAt(j)를 비교한 후, 그 때까지의 ..

    [Java] HashMap 메소드 및 사용법
    Language/Java

    [Java] HashMap 메소드 및 사용법

    HashMap HashMap을 정의한다면, '키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array'라고 할 수 있으며, 이 associate array(연관 배열)은 Map, Dictionary, Symbol Table 이라고도 불리운다. 간단하게 말하자면 Key-Value의 형태를 가진, Key와 Value가 1:1 매핑이 되어 하나의 쌍(Pair)으로 하여 중복된 Key를 허용하지 않는 기본적으로 순서가 없는 자료구조이다. 기본적으로 equals()를 사용하여 중복을 판단하기에 primitive data type은 걸러지지만, 객체(Object)는 객체의 값이 같더라도 equals()에서 서로 다르다고 판단하기 때문에 걸..

    [java] 프로그래머스 (타겟 넘버) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (타겟 넘버) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr Approach BFS나 DFS로 탐색하여 target number에 몇번 도착하는지를 계산하면 된다. 보통 DFS/BFS 는 목적지까지의 최소비용을 구하는데에 사용하지만, 이 문제에서는 최소비용이 아니라 몇번 도착하는지를 구하면 된다. Code public class TargetNumber..

    [java] 프로그래머스 (카펫) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (카펫) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr Approach 수학적 규칙을 찾는다면 편한 문제이다. 일단 전체 사각형 넓이는 (가로) x (세로) = brown + yellow 이다. 그리고 전체 사각형의 (가로 - 2) x (세로 - 2) = yellow 이다. 이 두 성질을 이용하여 전체 사각형의 넓이를 가질 수 있는 (가로, 세로)의 쌍 중에 (가로 - 2) x (세로 - 2) ..

    [java] 백준 11444 (피보나치 수 6) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 11444 (피보나치 수 6) Gold 3

    Problem : https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net Approach 유명한 피보나치 수열의 n번째 수를 구하는 문제이다. 이 문제는 백준 2749 피보나치 수 3 문제와 나머지 연산 부분만 다르고 아예 똑같은 문제이다. 문제풀이 개수 늘리기 좋다. 하지만 n이 1,000,000,000,000,000,000 이하의 숫자이므로 오랜시간이 걸릴 것이다. 따라서 아래와 같이 피보나치의 행렬적 규칙을 이용하여 계산하여야 한다. (long 자료형을 사용하여) 아래 규칙만 알고 있다면 O(log n)의 행렬제곱 문제와 ..

    [java] 백준 1629 (곱셈) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1629 (곱셈) Silver 1

    Problem : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net Approach 수학적 지식이 있어야 하는 분할정복(Divide & Conquer)문제이다. A^4 % C = ((A^2 % C) * (A^2 % C)) % C A^5 % C = ((((A^2 % C) * (A^2 % C)) % C) * A) % C 위의 규칙을 이용하여 구현하면 된다. Code import java.io.*; /** * no.1629 : 곱셈 * hint : A^2 % C = ((A % C) * (A % C)) % C */ p..

    [java] 백준 1992 (쿼드트리) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1992 (쿼드트리) Silver 1

    Problem : https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net Approach 전형적인 분할정복(Divide & Conquer)문제이다. 다음과 같은 과정을 반복하면 답을 도출할 수 있다. 현재 영역의 제일 좌상 요소를 기억한 후, 모든 영역을 검사한다. 기억한 요소와 모든 영역이 같다면, 기억한 요소를 반환한다. 다르다면, 정확히 4등분한다. (나누기 전 괄호로 감싼다.) 나눠진 영역의 크기가 1x1이 될 때까지 1번 전체를 ..

티스토리툴바