본문 바로가기

분류 전체보기

 (341)
[백준 / BOJ] 16967 배열 복원하기 문제 출처 : https://www.acmicpc.net/problem/16967 16967번: 배열 복원하기 크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐 www.acmicpc.net 크기가 H*W인 배열A를 아래로 X 오른쪽으로 Y만큼 이동한 배열을 배열 A와 겹쳤을때 나온 배열을 배열 B라고 하자. (배열이 겹쳐지면 같은 위치의 수가 합쳐진다.) 배열의 크기 H, W 이동범위 X, Y, 배열 B가 주어질때 배열 A를 구하는 문제다. 풀이 수학? 구현? 문제다. 배열B가 주어졌을때, 원래 배열의 (i,j)의 값은 다음과 같..
[백준 / BOJ] 9944 N*M 보드 완주하기 문제 출처 : https://www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net N*M크기의 보드에 장애물(*) 빈칸(.)이 있다 보드의 빈칸위에 놓인 공은 다음 규칙에따라 움직인다. 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 공을 계속해서 이동시킨다. 공은 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지 계속해서 이동한다. 게임은 공이 더 이상 이동할 수 없을때 끝난다. 모든 빈칸을 방문하기위한 이동횟수의 최솟..
[티스토리 스킨 공유] xbSimpleskin 프로젝트 진행중 개인프로젝트를 블로그에 홍보하면 좋겠다는 생각이들어서 만들게되었습니다. 빠른 블로그속도 (블로그 속도가 빠르면 구글 검색에 더 높은 순위로 노출됩니다.) 레이아웃별 기능설명 홍보용 카드 만드는법 1. 블로그 관리 -> 스킨편집 -> html편집을 클릭합니다. 2. html편집에서 아래 사진이 있는 부분을 찾습니다. (Ctrl+F 입력후, cardLayer 검색) 3. 위 사진에서 부터 까지 복사후 붙여넣습니다. "이동할 사이트 주소" 에 클릭시 이동할 사이트 주소 "이미지 링크"에 이미지 주소 "카드 이름"에 카드의 대 제목, 설명에 카드 내용을 작성합니다. 최종 결과는 아래와 같아야합니다. 다운받는 링크 스타 를 눌러주시면 큰 도움이 됩니다. https://github.com/devxb..
[백준 / BOJ] 11049 행렬 곱셈 순서 문제 출처 : https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net N개의 행렬이 주어진다. 행렬 A의 크기를 N*M, 행렬 B의 크기를 M*K라고 할때, 각 행렬을 곱할때 필요한 곱셈 연산 수는 N*M*K이다. 모든 행렬을 곱하는데 필요한 최소 연산횟수를 구하는 문제다. 풀이 다이나믹 프로그래밍으로 풀리는 문제다. 처음엔 그리디로 생각했지만, 현재 최적값이 나중에도 최적이라는 보장이없기때문에 그리디로는 풀기 힘들어보인다. 이 문제처럼 ..
[백준 / BOJ] 1498 주기문 문제 출처 : https://www.acmicpc.net/problem/1498 1498번: 주기문 어떤 문자열 X를 n번 연달아 쓴 것을 (X)^n으로 나타내기로 하자. 예를 들어 (ab)^3는 ababab를 의미한다. 어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있다면, 그리고 n이 1이 아니라면 Y를 주기문 이라고 한다 www.acmicpc.net 어떤 문자열 X를 n번 연달아 쓴 것을 X^n으로 나타낸다. 예를들어, 문자열, ababab는 ab^3이 된다. 문자열 X를 앞에서부터 i번째까지 주기문을 이룬다고 했을때, 해당 주기문의 n(n은 가능한 가장 크게)을 구하는 문제다. 예를들어, 문자열 abababab는 4 2 6 3 8 4 가 출력된다. 풀이 kmp로 푸는 문제였다. 주기를 찾는다는것은 ..
[백준 / BOJ] 1097 마법의 단어 문제 출처 : https://www.acmicpc.net/problem/1097 1097번: 마법의 단어 첫째 줄에 단어의 개수 N이 주어진다. N은 8보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 20이다. 단어는 알파벳 대문자로만 이루어져 있다. 마 www.acmicpc.net N개의 단어가 있다. N개의 단어를 적절히 조합하여 (이때, N개의 단어를 전부 사용해 조합해야한다) 문자열 T를 만든다. 문자열 T의 시작지점을 i만큼 오른쪽으로 이동시켰을때 문자열을 T(i)라 한다. (문자열 ABCD를 오른쪽으로 2만큼 움직인후 문자열은 CDAB가 된다.) 이때, 문자열 T와 바뀐문자열 T(i)가 정확히 일치하게되는 i가 k개 있으면, 이 문자열을 "마법의..
[백준 / BOJ] 1854 K번째 최단경로 찾기 문제 출처 : https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net n개의 도시, m개의 길, k가 주어진다. 김 조교가 1번째 도시에서 출발한다 했을때, 1번부터 n번도시까지 k번째 최단경로를 구하는 문제다. 풀이 다익스트라로 푸는 문제다. k가 100으로 크지않아서, n번째 도시에 k번째 도착하는 모든 경로를 찾아서 구해주면된다. 로직 1. 1번도시에서 다익스트라를 시작한다. 2. 최단경로..
[백준 / BOJ] 5719 거의 최단 경로 (Java) 문제 출처 : https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net N개의 장소와 M개의 도로가 주어진다. (각 도로는 가중치를 갖고있다.) 시작도시 S에서 도착도시 D로 가는 최단경로를 포함하지않는 경로중 가장 빠른 경로를 출력하는 문제다. 풀이 쉬운 문제이해와 그렇지 않은 최적화 과정.. 다익스트라로 푸는 문제였다. 문제가 특이한게, 플래티넘 난이도 임에도 푸는 방법이 굉장히 직관적으로 보인다. 최적화와 경로 추적이..

티스토리툴바