전체 글

전체 글

    [java] 프로그래머스 (이진 변환 반복하기) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (이진 변환 반복하기) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/70129 코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr Approach 월간 코드 챌린지 시즌1의 문제이며, 문자열을 처리하는 문제이다. x의 모든 0을 제거합니다. x의 길이를 c라고 하면, x를 c를 2진법으로 표현한 문자열로 바꿉니다. 위의 두가지를 반복하면서 변환 횟수, 제거된 0의 개수를 세어서 반환하면 된다. 따로 설명이 필요없고 구현 문제기 때문에 코드를 보면서 문자열을 처리하는 방법을 익히는 것이 좋을 것 같다. Code public class BinaryConversion { public static void main(String[] args) { Str..

    [java] 프로그래머스 (숫자의 표현) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (숫자의 표현) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12924 코딩테스트 연습 - 숫자의 표현 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 programmers.co.kr Approach naive한 방법으로는 1부터 연속된 몇개의 숫자를 더해서 주어진 숫자 n을 만들 수 있는지를 검사하는 방법이다. 그러나 수학에서 주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다.는 정수론 정리가 존재한다. 따라서 위의 정리를 알았다면 문제 풀이가 더 쉬웠을 ..

    [java] 프로그래머스 (폰켓몬) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (폰켓몬) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/1845 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. programmers.co.kr Approach N개의 폰켓몬 중 N / 2개의 폰켓몬을 최대 종류로 가져가는 법을 찾는 문제이다. 간단하게 N개의 포켓몬을 모두 set에 넣는다. 그런 후 set의 size가 N / 2보다 작으면 set의 size를 반환하면 되고, 아니라면 N / 2를 반환하면 된다. 간단한 문제이다. Code import java.util.Arrays; ..

    [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) 입력으로 그래프를 먼저 구성하고, 플로이드..

티스토리툴바