전체 글

[프로그래머스] [Level2] 프렌즈4블록 - JAVA

[문제] 프로그래머스 level2 2018 KAKAO BLIND RECRUITMENT 출제 https://programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr [풀이] 1. 블록의 처음 칸부터 순회하며 현재 칸을 포함한 2 × 2 영역을 확인한다. 2. 모두 같은 문자이면 4칸 모두 checked=true 표시 3. 모든 블록을 탐색한 후 checked=true로 표시된 곳은 지워준다. 그리고 지워진 영영..

[백준][Gold2]10473 - 인간 대포 - JAVA

[문제] https://www.acmicpc.net/problem/10473 10473번: 인간 대포 입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대 www.acmicpc.net [풀이] * 알고리즘 : 다익스트라 알고리즘(https://programmer-chocho.tistory.com/63) 1. 출발지와 도착지가 존재하기 때문에(a -> b) 최단 경로 알고리즘을 응용하는 문제다. 최초에 그래프를 어떻게 만들것이냐가 관건이다. 만들어진 그래프가 있어야 최단 경로를 구한든 말든 할 것이기 때문에;; 2. 최단 경로를 구하는 그래프를 만들려면 가중치가 ..

최단 경로 알고리즘 - JAVA

1. 최단 경로 알고리즘 - 목적지에 이르는 모든 가능한 경로 중 최단 경로를 찾는 알고리즘 - 종류: ①다익스트라 알고리즘 ②벨만-포드 알고리즘 ③모든 쌍 최단 경로 알고리즘 ※ ①② 와 ③의 코딩테스트 제출 차이 - 특정 시작점에서 모든 정점들까지의 최단 경로 구하기 --> 다익스트라, 벨만-포드 - 모든 시작점에서 모든 정점들까지의 최단 경로 구하기 --> 모든 쌍 최단 경로 알고리즘 (대표: 플로이드와샬) ※ 최소 신장 VS 최단 경로 "최소 신장"과 "최단 경로"는 얼핏보면 같은 말 같다. 뭐가 다르길래 굳이 알고리즘을 나누었나 궁금하여 차이점을 간단히 메모해둔다. * 최소 신장 - 모든 정점을 방문하면서 간선의 비용이 합이 최소가 되는 "트리"를 만듦 - ex) 프림 알고리즘, 크루스칼 알고리..

[백준][Sliver1]1932 - 정수 삼각형 - JAVA

[문제] https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net [풀이] * 알고리즘: 다이나믹 프로그래밍 다이나믹 프로그래밍을 이용하여 푸는 문제이다. 점화식은 쉽게 세울수 있다. 그런데 인덱스를 이용한 삼각형 배열을 만드는 것이 어려웠다. 어려웠던 이유는 1차원 배열로 삼각형을 만드려했기 때문이었다. 2차원 배열로 삼각형을 만드니 쉽게 다이나믹프로그래밍을 이용하여 문제를 풀 수 있었다. 바텀업 방식으로 풀면되는데 현재 위치에서 위로 왼쪽 대각선, 오른쪽 대각선에 있는 수 중 큰 수를 현재값과 더해주면 된다. 그런데 삼각..

[코딩테스트] 2차원배열 회전하기

코딩테스트 문제를 풀다보면 2차원 배열을 조작하는 경우가 굉장히 많은 것 같다. (맵을 상하좌우로 기울여라, 지도를 회전하라 등등..) 최근에 푼 2020 KAKAO BLIND RECRUITMENT 기출문제중 자물쇠와 열쇠라는 문제가 있는데 여기서 2차원배열을 90, 180, 270, 360 도 회전시켜야 하는 코드가 필요하다. 배열의 인덱스를 이용해서 N도 회전했을 때 각 자리에 바뀌는 값들을 구해야 하는데 꾀나 번거로웠다. 다음에 또 구해야 한다면 할 수는 있겠지만 매번 시간을 굉장히 많이 잡아먹을 것 같아서 블로그에 정리해두려고 한다. 다음과 같은 2차원 배열이 있다고 하자. 먼저 배열을 시계방향으로 90도 회전시키면 배열이 다음과 같이 값이 바뀐다. 그리고 다음은 시계방향으로 180도 회전한 모습..

[프로그래머스][Level3] 자물쇠와 열쇠 - JAVA

[문제] https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr [참고 영상] https://www.youtube.com/watch?v=I1App3qLi6o [code] package com.algorithm.thisiscodingtest.implement; import java.io.*; import java.util.*; public class Test08 { public static void main(String[] args) throws IOException..

[백준][Gold5]1107 - 리모컨 -JAVA

[문제] https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net [풀이] - 알고리즘 분류 부르트포스 알고리즘 정리를 하면 원하는 채널로 이동하는 방법은 2가지가 있다. 1. +,- 로만 이동하는 방법 2. 가장 근접한 채널까지 이동후, 나머지는 +,-로 이동하는 방법 처음에 1번 방법은 생각을 못했다. 그런데 만약 이동하려는 채널이 102번일 때 고장난 버튼 없다고 해서 102 세자리 수를 누르는 것보다 +를 2번 누르는 것이 더 클..

[백준][Gold5] 12865 - 평범한 배낭 - JAVA

[문제] https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 처음에 완전탐색으로 풀었는데 시간초과가 떴다. 찾아보니 배낭문제(knapsack problem)는 dp를 응용하는 아주 유명한 문제라고 한다. dp, 즉 메모이제이션을 이용하기 위해서는 값을 저장할 테이블을 정의해야 한다. 다음과 같은 이차원 배열을 정의하겠다. dp[i][j] = value - i : 1 ~ i 까지의 아..

[백준][gold5] 9251번: LCS - JAVA

[문제] www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 대학교 알고리즘 수업때 들었지만 기억이 가물가물했다. 아래 유튜브를 보면서 다시 공부했다. www.youtube.com/watch?v=EAXDUxVYquY [코드] package com.algorithm.baekjoon.gold5; import java.io.*; /** * 9251 - LCS */ public class Test04 { public stat..