백준 썸네일형 리스트형 [백준 9251][DP] LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 출처: https://www.acmicpc.net/problem/9251 점화식 dp[i][j]: 수열1 i까지, 그리고 수열 j 까지 최장 공통 부분 수열 길이 수열 ACAYKP, CAPCAK에 대해 점화식을 2차원 배열로 표현하면 다음과 같다. 원소 하나에 대해 3가지 방향으로부터 영향을 받아 값이 정해진다. 특징LCS 기본 문제 점화식 루프를 돌때 배열의 범위를 벗어나지 않게 조심해야 한다. 따라서 i 또는 j가 0인 경우는 따로 로직으로 처리해줄 수.. 더보기 [ 백준 3954 ] Brainf**k 인터프리터 ( 자바 ) [ 백준 3954 ] Brainf**k 인터프리터 ( java ) Brainfuck 프로그램이 주어졌을 때, 이 프로그램이 끝나는지, 무한 루프에 빠지는지 알아내는 프로그램을 작성하시오. Brainfuck 인터프리터는 정수를 담는 하나의 배열(unsigned 8-bit 정수)과, 그 배열의 칸 하나를 가리키는 포인터로 이루어져 있다.Brainfuck 프로그램은 다음과 같이 8개의 명령어로 이루어져 있다. 인터프리터는 Brainfuck 프로그램의 첫 번째 명령부터 수행하고, 더이상 수행할 명령이 없다면, 프로그램을 종료한다. 각 명령을 수행하고 나면, 다음 명령을 수행한다. ([와 ]인 경우에는 점프를 할 수 있다.) 데이터 배열의 크기는 문제에서 주어지는 값을 사용해야 한다. 또, 데이터 배열의 값이 u.. 더보기 [ 백준 17825 ] 주사위 윷놀이 ( 자바 ) [ 백준 17825 ] 주사위 윷놀이 ( java ) - 삼성 공채 sw 2019 하반기 기출문제 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 가장 처음에는 시작에 말 4개가 있다. 말은 게임판에 적힌 화살표의 방향대로만 이동할 수 있다. 파란색 칸에서 말이 이동을 시작하는 경우에는 파란색 화살표의 방향으로 이동해야 하며 파란색 칸을 지나가는 경우에는 빨간 화살표의 방향대로 이동해야 한다. 게임은 1부터 5까지 한 면에 하나씩 적혀있는 5면 주사위를 굴려서 나온 수만큼 이동하는 방식으로 진행한다. 이동하려고 하는 칸에 말이 이미 있는 경우에는 그 칸으로 이동할 수 없다. 시작과 도착칸은 말이 이미 있어도 이동할 수 있다. 말이 이동을 마칠때마다 칸에 적혀있는 수가 점수에 추가된다. 말이 도착으.. 더보기 [ 백준 17779 ] 게리맨더링 2 (java) [ 백준 17779 ] 게리맨더링 2 (자바) 삼성 2019 하반기 오전 첫 번째 문제 시뮬 문제 (+ dfs, +간혹 dp로 푸는 사람들도 있는 듯 ) 문제에 조건들이 많아지고 복잡해지고 있다. 출처:백준 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역.. 더보기 [ 백준 17837 ] 새로운 게임 2 (java) [ 백준 17837 ] 새로운 게임 2 (자바) https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 www.acmicpc.net 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다.. 더보기 [ 백준 14503 ] 로봇청소기 (java) [ 백준 14503 ] 로봇청소기 (자바) https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 핵심 1 시뮬레이션 (+메모이제이션) / bfs 문제 시뮬이나 bfs 문제 특징은 조건.. 더보기 이전 1 다음
