분류 전체보기

[BJ] 백준 11057 오르막 수 (JAVA)

문제 https://www.acmicpc.net/problem/11057 풀이 방법 한창 DP 문제를 풀 때의 문제들을 올리고 있어서 아마 한동안은 DP문제들만 게시할 것 같다.. 문제를 간단하게 리뷰하면 오르막수는 수가의 자리가 오름차순으로 이루어진 수를 말한다. 이때, 같은 수인 경우에도 오름차순으로 생각한다. 예를들어 1123, 3456, 249 등의 수가 있다. 수의 자리수 N이 주어지면 이 오름차순인 N자리 수의 개수를 구하면 되는 문제다. 이 문제도 DP를 사용해서 풀이했다. 바로 직전의 문제와 동일하게 dp[N][10] 의 2차원 배열을 선언해주고, N은 몇자리 수인지, 그리고 뒤에 0~9는 마지막 자리라고 생각해줬다. 예를 들어 2135 인 숫자는 dp[4][5] 에 포함이 되어있을 것이다..

[BJ] 백준 10844 쉬운 계단 수 (JAVA)

문제 https://www.acmicpc.net/problem/10844 풀이 방법 dp를 사용하는 문제다. dp는 왜 항상 해도해도 새로울까... 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다. N이 주어지고 N자리 숫자에서 계단수가 총 몇개 있는지 구하면 되는 문제이다. dp는 2차원 배열로 선언해주고, dp[N][m] : N자리 숫자이고 마지막 자리의 수가 m인 숫자의 개수를 넣어준다고 생각하면 된다. 그래서 반복문 N번 돌면서 j : 0부터 10까지 반복문을 돌린다. j는 마지막 자리 숫자이다. 만약 2343라는 수는 dp[4][3]에 포함이 되는 숫자이다. 어쨌든 반복문을 돌면서 마지막 자리수에 -1, +1을 하는 경우가 0~9사이에 존재한다면 [n+1][j+1] 또는 [n+1][j-1..

[BJ] 백준 2116 주사위쌓기(JAVA)

문제 https://www.acmicpc.net/problem/2116 풀이 방법 구현문제로 브루투포스 알고리즘을 사용하면 된다. 우선 나는 문제에 있는 ABCDEF을 보고 각 마주보는 면의 인덱스를 미리 저장해뒀다. 다음과 같은 순서로 구현했다. 1. 맨 아래에 올 주사위의 윗면을 정해준다. (6면 전부 다 구해보기) 2. 윗면이 정해졌으면 옆면중에서 가장 큰값을 고른다. 3. 윗면의 값과 위에서 골랐던 옆면 중 가장 큰값을 가지고 주사위를 쌓으러 간다. //재귀함수 시작 (아래서 2번째 주사위부터 쌓아올리는 함수) 1. 아래에 있는 주사위의 윗면에 해당하는 값을 현재 주사위에서 찾는다. => 자동으로 윗면의 인덱스가 정해진다. 2. 옆면중에서 가장 큰값을 고른다. 3. 그 다음 주사위를 쌓으러 간다...

[WEB] Next.js + Typesctipt + StyledComponents 프로젝트 생성하기

이번에 새로운 사이드프로젝트를 진행하면서 기술 스택들이 정해졌고, 해당 스택들을 사용해서 프로젝트를 생성하려고 한다. react와 scss로 작업해본 경험이 있어서 이번엔 크게 next.js (react를 했으니 그래도 좀 수월하지 않을까라는 생각) 와 typescript, styled-component를 사용해보려고 한다. next 프로젝트 생성하기 with Typescript $ npx create-next-app --example with-typescript [프로젝트 이름] typescript와 같이 next프로젝트를 생성해주는 명령어이다. 실행이 끝나면 cd 를 사용해서 프로젝트로 이동해준다. $ npm install npm install를 사용해서 필요한 패키지들을 설치해준다. 설치가 다 되면..

[BJ] 백준 11463 1로 만들기(JAVA)

문제 https://www.acmicpc.net/problem/1463 풀이 방법 문제는 간단하다. 1. x가 3으로 나누어떨어지면, 3으로 나누기 2. x가 2로 나우어 떨어지면, 2로 나누기 3. 1를 빼기 위 세개의 연산을 적절히 사용해서 1을 만드는데 연산을 사용하는 횟수의 최소값을 구하는 문제이다. 이 문제는 dp를 사용해서 풀면 된다. dp[N]에는 N이 1이 될때까지의 최소 연산 횟수를 가지고 있다. 우선 N이 2또는 3으로 나누어떨어지는지 확인한다. 만약 나누어 떨어진다면 2로 나눴을 때와 3으로 나눴을때 어떤 수가 더 최소연산 횟수를 가지는지 비교해서 더 작은 값을 dp에 넣는다. 그리고 항상 -1를 했을 경우의 연산의 최소값을 구해서 기존의 dp값과 비교 후, 더 작은 값을 dp에 넣어..

[SWEA] D4 1251 하나로 (JAVA)

문제 저작권 문제로 인해 링크만 첨부합니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD&categoryId=AV15StKqAQkCFAYD&categoryType=CODE&problemTitle=1251&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 풀이 방법 프림 알고리즘에 대한 개념을 배우고 풀어본 문제다. 우선 입력값을 이요해서 인접 행렬을 만들어주고, 만들면서 각 섬 사이의 거리 값도 저장해줬다. 그 후 이제 프림 알고리즘을 수행했다. 아직 방문하지 않은 섬들중에서 가장 최소 거리..

[BJ] 백준 1753 최단경로(JAVA)

문제 https://www.acmicpc.net/problem/1753 풀이 방법 이 문제는 다익스트라를 이용하는 문제였던걸로 기억한다. 시작 위치에서부터 가장 최소인 경로를 출력하면 된다. 나는 우선 정점과 가중치를 저장하기 위한 클래스를 하나 선언해줬고, 우선 순위큐를 사용했다. 우선순위 큐에는 현재 시작점으로 부터 가장 가중치가 작은걸 우선으로 정렬하도록 선언했다. 우선순위 큐에서 하나씩 꺼내면서 꺼낸걸 방문 체크해주고, 꺼낸걸 기준으로 꺼낸 점접의 인접 점들을 보면서 꺼낸 것을 경유지로 간다면 더 작은 경로인 경우들만 경로를 업데이트 해주고, 우선순위 큐에다가 넣어주는 식으로 구현했다. 제출 코드 import java.io.*; import java.util.*; import sun.securit..

[SWEA] D4 3289 서로소 집합 (JAVA)

문제 저작권 문제로 인해 링크만 첨부합니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr&categoryId=AWBJKA6qr2oDFAWr&categoryType=CODE&problemTitle=3289&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 풀이 방법 문제를 간단하게 정리하면 각 원소가 초기에 자기자신만 가지고 있는 집합을 가지고 있고, 입력에 따라서 합집합과 같은 집합인지 확인하는 계산을 수행한다. 첫번째 원소가 0이면 합집합을 수행하고, 1이면 같은 집합인지 확인하는 연산을 ..

[BJ] 백준 10158 개미(JAVA)

문제 https://www.acmicpc.net/problem/10158 풀이 방법 문제를 간단하게 이해하면 t초후 개미의 위치를 구하면 되는 문제다. 이동은 45도로 이동을 하기 때문에 물론 이동 방향을 사용해서 하면 어려운 문제는 아니다. 하지만 이 문제에서 그런식으로 문제를 푼다면 시간초과가 난다. 시간을 단축시킬 수 있는 다른 방법을 찾아야한다. 나도 처음엔 위와 같은 방식으로 문제를 풀었는데 시간초과가 났고, 어떤 식으로 풀어야할 지 계속해서 고민을 한 것 같다. 몇시간을 고민하면서 시도를 했었는데 도저히 풀리지가 않아서 힌트를 조금 얻어서 풀었다. 내가 본 힌트는 x와 y좌표를 따로 구해보라 였다. 그래서 어떻게 따로 구하지 생각을 하다가 x좌표만 가지고 보니 좌표가 열 길이의 2배만큼 이동을..