JSPT

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제는 사진이 많아서, 따로 블로그에 적지 않겠습니다. 👇 접근방식 문제를 보았을 때, 사방 탐색 문제라는 걸 알았습니다. dfs 또는 bfs 문제인데, 일단 최소가아니라 depth(5)가 정해져있으니, dfs 로 문제를 풀어야겠다고 생각했습니다. 일단 생각으론 NxN 칸을 매 번 이동 시켰을 시, 기억을 해주어야하며? 그리고 이동했던 방향까지 기억을 해야한다고 생각하..

구슬 탈출2 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 👇 접근 방식 이 문제는 처음에 전에 풀었떤 두 동전(16197) 문제와 유사해서 1차 로직 설계는 금방 했던 거 같습니다. 제 생각은 이 문제 풀기 전에, 두 동전 문제 풀고 오시면, 훨씬 이해하기도 쉽고 계단식의 문풀을 경험할 수 있을 거 같아요. 1차 로직 설계는 1. 두 구슬 위치를 저장해 놓기. (R, B 구분을 해주어야합니다. 따라서, 구슬 한 객체에 두 구슬 위치 값을 넣습니다) 2. 두 ..

가르침 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다. 남극언어의 모든 단어는 "anta"로 시..

알파벳 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를..

BFS 그래프 전체를 탐색하는 방법 중 하나로, 루트 노드 또는 다른 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점을부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 순회함으로 써 노드를 넓게(wide)하게 탐색을 합니다. 더 설명하자면, BFS는 해를 찾아서 조직적으로 트리의 모든 노드들을 검사하는 무정보 탐색(Uniformed search)입니다. 달리 말하자면, 목표에 대한 고려없이 목표가 발견될 때까지 전체 트리 또는 그래프를 전부 탐색하고, BFS는 휴리스틱을 사용하지 않습니다. (반대로 휴리스틱을 사용하는 알고리즘은 ex) Greedy best-first search 또는 A*) 👇 search 의 두 분류 더보기 Uniformed search ..

문제 설명 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. - 정사각형은 서로 겹치면 안 된다. - 도형은 모두 연결되어 있어야 한다. - 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 아래에 그림 보면, 다음과 같은 5가지가 있다 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 테트로미노는 반드시 한 정사각형이 정확히 하나의..

DP 문제를 처음 접했을 때 풀었던 문제입니다. 일단 DP에 대해서 잘 모르신다면, 아래 링크를 타고 가서 한 번 읽고 오셔도 좋을 거 같습니다. 다이나믹 프로그래밍 점화식 1로 만들기 문제는 Top-down, Bottom-up, dfs 방식으로 각기 다르게 문제를 풀어보았습니다. 아래코드 기준으로 메모리,시간 효율이 좋은 순서는 dfs > Bottom-up > Top-down 입니다. 하지만 dfs 와 Bottom-up은 큰 차이는 보이지 않았습니다. 각 코드마다 주석으로 코드 설명을 해놓았습니다. 혹시 코드개선할 점과, 모르는 부분이 있으시면 댓글 남겨주시면 감사합니다 : ) DP 문제는 종이와 펜을 가지고 일일이 확인을 해보면서 점화식을 찾으며 문제를 풀고 그 능력을 키우면 실력에 도움이 많이 될거..