Algorithm

    [java] 프로그래머스 (땅따먹기) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (땅따먹기) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr Approach 대표적인 DP문제이다. 다음 위치의 땅으로 가는 경우의 수는 바로 위 땅을 제외한 3곳에서 오는 방법이 있다. 따라서 dp[i][j] = Math.max(dp[i - 1][(j + 1) % 4], dp[i - 1][(j + 2) % 4], dp[i - 1][(j + 3) % 4]) + land[i][j] 이다..

    [java] 프로그래머스 (다음 큰 숫자) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (다음 큰 숫자) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12911 코딩테스트 연습 - 다음 큰 숫자 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니 programmers.co.kr Approach 자바에선 10진수로 표현된 숫자를 2진수로 변환 했을때의 1비트의 개수를 세어주는 Integer.bitCount() 메소드가 있어 편하게 문제를 풀이할 수 있다. 주어진 숫자 n을 1씩 증가시킨 숫자의 1비트의 개수가 n의 1비트의 개수와 같으면 그 숫자를 반환한다. Code public clas..

    [java] 프로그래머스 (올바른 괄호) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (올바른 괄호) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 ()() 또는 (())() 는 올바른 괄호입니다. )()( 또는 (()( 는 올바르지 않은 괄호 programmers.co.kr Approach 괄호체크는 간단하게 Stack을 사용하여 확인할 수 있다. '('을 만나면 stack에 push를 하고, ')'를 만났을 땐 stack이 비어있거나 stack의 top이 '('이 아니면 false를 반환한다. 맞다면 stack에서 pop을 한다. 또, 문자열의 끝까지 위 과정을 반복해서 끝낸 ..

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

    [java] 프로그래머스 (튜플) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr Approach 2019 카카오 개발자 겨울 인턴십 문제이다. Level2에 위치한 카카오문제들은 가끔보면 Level2가 아닌것 같은데 이 문제는 주어진 문자열만 잘 처리하면 꽤 쉬운 문제였다. mySolution은 내가 테스트를 통과한 코드이고, simpleSolution은 다른 분의 풀이를..

    [java] 프로그래머스 (단체사진 찍기) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (단체사진 찍기) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr Approach 2017 카카오코드 본선 문제이다. 생각보다 어려웠다... Level 2의 다른문제와는 난이도가 다른것 같다... {A, C, F, J, M, N, R, T} 로 줄을 세우는 방법 중 주어진 조건을 만족하는 방법의 개수를 구하는 문제이다. 줄을 세운다는 것 자체가 순열이므로 순열을 구하여, 특정 문자의 위치의 거리를 계산하여 ..

    [java] 백준 1915 (가장 큰 정사각형) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 1915 (가장 큰 정사각형) Gold 5

    Problem : https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net Approach DP로 풀 수 있는 문제로, DP[i][j] 는 (i, j) 위치에서 좌상으로 진행했을 때 만들수 있는 가장 큰 정사각형의 한 변의 길이이다. 따라서 주어진 board[i][j] 가 1이라면 일단 최소 1x1 정사각형을 만들 수 있으므로 dp[i][j] = 1을 저장한다. 그리고 board[i][j - 1], board[i - 1][j], board[i - 1][j - 1]이 모두 1이라면 DP[i][j]에 min(DP[i][j - ..

    [java] 백준 11780 (플로이드 2) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 11780 (플로이드 2) Gold 3

    Problem : https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Approach 플로이드와샬 알고리즘을 사용한 최단경로비용 구하기 + 최단경로를 구하는 문제이다. dist[i][j] = i부터 j까지 가는 최소비용이고, (i == j 일 경우거나, 도달할 수 없는 경우는 0) next[i][j] = j도착 직전 도시를 저장해놓은 배열이다. (i == j 일 경우거나, 도달할 수 없는 경우는 -1) 입력으로 그래프를 먼저 구성하고, 플로이드..

    [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 ..

티스토리툴바