뚝딱 뚝딱 개발일기

공통부분 문자열https://www.acmicpc.net/problem/5582문제두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJ..

해당 문제는  bfs , dfs로 모두 풀이가 가능하다.모든 경우의 수를 따져봐야하지만 세 수의 합이 3의 배수일 때  세 수가 같아질 수 있다는 특징을 가지고 있다.또한 세 수의 합은 언제나 같으므로 3차원이 아니 2차원만으로도 방문여부를 확인할 수 있다.3차원으로 선언해 버리면 메모리 초과 오류가 발생해 버린다. bfs 풀이import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.LinkedList;import java.util.Queue;class Main{ public static void main(String[] args) throws Exception { ..

https://www.acmicpc.net/problem/16928  시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초512 MB47405173931329833.847%문제뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다.주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라..

문제N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.오늘부터 인구 이동이 시작되는 날이다.인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고..

해당 문제는 dp 문제로 규칙만 찾으면 쉽게 풀 수 있는 문제다.생각보다 어려웠다.풀이를 참고하여 풀었지만 너무 어려웠던 만큼 복습을 해보도록 하자문제크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.예를 들어, A의 크기가 5×3이고, B의 크기가 3 ×2, C의 크기가 2 ×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해 보자.AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36..

https://www.youtube.com/watch?v=tZu4x5825LI  내비게이션은 어떤 원리로 최단거리를 추천해줄까? 궁금하다면 다익스트라 알고리즘을 알아보자! 다익스트라(Dijkstar) 알고리즘은 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 최단 경로 문제 알고리즘입니다. 음수 간선이 없는 경우 사용할 수 있고, 음수의 간선이 존재할 경우 벨만-포트 알고리즘을 사용하면됩니다.1. 다익스트라 알고리즘은 아직 확인되지않은 거리는 전부 초기값을 무한으로 잡습니다.Q 는 방문하지 않는 노드들의 집합   초기화를 실행합니다.출발지를 A 로 설정했기 때문에 ,  d[A] = 0 이 된다. ( A 노드를 아직 방문한 것은 아니다)출발지를 제외한 모든 노드들은 아직  확인되지 않았기에, d[다..

https://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  해당 문제는 누적합의 개념을 알아야 시간안에 풀 수 있다.시간은 초로 환산하여 계산하면 간단히 구현할 수 있다.  주의 1. 재생시간에서 끝나는 시간 end 에서는 -1 을 해주어야 한다. 시청 구간의 의미: 예를 들어, 로그에 00:00:00 - 00:00:10이라고 되어 있으면, 일반적으로 시청이 00:00:00에서 시작하고, 00:00:10이 시작되는 순간에 끝난다는 것을 의미합니다. 즉, 실..

https://school.programmers.co.kr/learn/courses/30/lessons/150369#  접근 방법매 순간 최적의 선택을 통해 문제를 해결해 나가는 그리디 유형이다.먼 곳의 택배의 갯수를 매번 최적으로 가져오면 최소한의 이동거리를 얻을 수 있다.멀리 있는 지점부터 시작해 트럭의 용량만큼 배달하고, 용량이 허용하는 한 수거작업 또한 진행한다.  import java.util.*;class Solution { public int update(int pointer, int[] arr, int cap){ int sum = 0; while(pointer >= 0 && sum cap){ arr[++pointer] = sum - ca..

https://www.acmicpc.net/problem/2579문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도..

https://www.acmicpc.net/problem/3190문제'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다..