전체 글

[코딩테스트] 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..

[백준][gold5] 14502번: 연구소 - JAVA

[문제] www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [풀이 내용] * 알고리즘 분류 - 부르트포스 알고리즘 - 너비 우선 탐색 0으로 표시된 빈칸들 중에 3곳을 골라 벽을 세워야 한다. 어떻게 3곳을 골라야 가장 안전 영역을 많이 확보할 수 있는지 모르므로 경우의 수를 모두 해봐야 한다. 그 다음 각 경우마다 바이러스가 퍼질 수 없는 안전 영역의 크기를 구하고 그 중 최댓값을 출력한다. 1. 연구소 2차원 배열에서 0으로 표시된 칸들 중에 3가지를 선택하는 경우의 ..

[백준][Gold1]11401-이항계수3-JAVA

[문제] www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 1. 정수론에서의 합동 우리는 보통 합동이라는 단어를 도형의 합동을 얘기할 때 사용한다. 그런데 정수끼리의 관계를 얘기할 때도 합동이라는 개념이 존재한다. 정수론에서 합동은 어떤 개념일까? A: 비행기가 13시에 출발한다고? B: 응, 1시에 출발해 13과 1은 다른 숫자임에도 시각에서는 동일시된다. 우리가 쓰는 시계를 12시 단위이기 때문에 12로 나눈 나머지만 말해도 소통이 가능하다. 정수론에서도 마찬가지다. 정..

[백준][Gold1] 구간 합 구하기 - JAVA

[문제] www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리 자료구조를 이용해야 한다. 세그먼트 트리는 구간들을 보존하고 있는 트리로 구간합, 구간 곱 등을 구할 때 사용할 수 있다. [code] package com.algorithm.baekjoon.gold; import java.io.*; import java.util.StringTokenizer; public class Test03 ..

[백준][Gold1] 책 페이지 - JAVA

[문제] www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net [풀이] ✅구하려는 것: 1 ~ N까지의 숫자에 0~9가 각각 몇번 등장하는가 ✅규칙 * A=1, B=N으로 둔다. (ex. A=1, B=678) 1. ☝🏼정해진 약속: A의 일의자리는 항상 0, B의 일의자리는 항상 9여야 한다. 만약 아니라면 B--, A++ 하여 숫자를 변형해준다. A ~ B까지 일의자리에 0~9가 몇번들어가는가 2.예시의 A=1, B=678를 위 규칙대로 변형하면 A = 10, B=669가 된다. 이때, B = 678 -> 669로 변형되면서 숫..