내가보려고만든 메자노트

문제 보러 가기 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 이 문제는 백트래킹에 속해있는 문제로 완전 탐색을 통해 풀이할 수 있다. [ 적절한 탐색 조건 + 탐색을 하는 순서 ]를 찾아 접근하여야 통과할 수 있었던 거 같다. 물론 나는 헤매다가 다른 분들의 접근법을 참고하였다 ^_ㅠ 문제풀이 -가장 적게 색종이를 사용하므로 5X5의 색종이부터 탐색 -해당 색종이 영역이 다 1인지 확인 -> 다 1이면 사용할 수 있다는 의미 -해당 색종이를 사용할 수 있다면 사용하고 다른 색종이에 걸리지 않도록 0..

팰린드롬 문제를 접하고 비슷한 문제들의 다양한 풀이 방법을 모아보았다. 단순히 팰린드롬인지 확인하는 문제가 아닌 문자열의 부분문자열이 팰린드롬인지, 그중 가장 긴 길이는 얼마인지 찾는 문제를 풀어보았다. 그냥 탐색이 아니라 알고리즘 적용해서 푸는건 아예 모르겠어서 여기저기 찾아보고 manacher알고리즘을 알게 되었다! 팰린드롬(Palindrome)이란? abcba 처럼 양쪽이 대칭이 되는 문자열을 의미한다. 한 글자의 a 두 글자의 aa 역시 팰린드롬이다. 프로그래머스-가장 긴 팰린드롬 이 문제는 주어진 문자열의 부분 문자열 중 가장 긴 팰린드롬의 길이를 찾는 문제이다. 문자열 최대길이가 2500 이므로 넉넉하게 각 인덱스마다 탐색으로 진행하면 되겠다. public class LongestPalindr..

문제보러가기 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 이 문제는 투 포인터 알고리즘을 접해봤다면 이 알고리즘을 써야겠구나 라고 바로 알 수 있다. 신경 써줘야 할 점은 중복이 가능한 문자열이라는 점! 문제풀이 - 왼쪽 시작 포인터 s와 오른쪽 끝 포인터 e를 이동해가면서 최대 길이를 찾는다 - 알파벳의 종류의 수를 체크하기 위해 Map을 이용한다 - Map의 size()가 주어진 종류의 수 보다 크다면 s++하고 해당 문자열을 key로 갖는 value를 -1 해준다. 만약, -1 했을 때 value==0이라면 m..

문제보러가기 이 문제의 경우 그래프 탐색 유형에 속해 있으며 bfs, dfs, 플로이드와샬등 다양한 풀이 방법으로 해결이 가능하다고 한다. 처음 문제를 접했을 때는 금방 풀릴 거 같았지만 생각보다 어렵게 느꼈고 다른 분들의 풀이 방법을 참고하여 해결하였다. 플로이드 와샬이라는 방법을 몰랐기 때문에 공부하였고 이 알고리즘으로 풀이를 하였다. -플로이드 와샬 기본문제 (백준 11404- 플로이드) 플로이드 와샬 이란? 다익스트라 알고리즘과 같이 정점-정점 간의 최단거리를 구하는 알고리즘이다. 차이점으로는 다익스트라는 하나의 고정된 정점에서 다른 모든 정점으로의 최단거리를 구하는 것이고, 플로이드 와샬은 모든 정점에서 다른 모든 정점으로의 최단거리를 구하는 것이다. 또한 dp를 기반으로 이루어진다. 문제풀이 ..

문제보러가기 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 이 문제는 기존 bfs처럼 영역을 나눠서 영역의 개수, 영역의 최대 넓이 , 벽을 하나 제거한 후의 영역의 최대 넓이를 구하는 여러 문제가 합쳐져 있는 복합적인(?) 문제였다. 여기서 까다롭게 봐야 할 점은 벽을 제시할 때 0~15의 값으로 주어지며 이를 bit로 변환하여 사용해야 한다는 점이었다. 문제풀이 - bfs로 구한 영역을 증가하는 groupCnt를 키값으로 묶어 아래 그림처럼 group [][]에 저장해준다. -bfs로 영역을 구할 ..

문제보러가기 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이문제는 전형적인 탐색 문제로 연결된 영역이 몇 개가 있는지 구하는 문제였다. 다른 점이라면 위, 아래, 오른쪽, 왼쪽이 아닌 대각선 포함 8방향으로 탐색해야 한다는 점. 문제풀이 -map [][]에 입력받은 값을 저장해준다. -map을 이중 for문으로 탐색하면서 1일 경우(섬일 경우) 그리고 방문하지 않았을 경우에 bfs()를 수행한다. -4방향이 아닌 대각선 포함 8방향으로 체크해주면서 연결된 섬의 개수를 체크한다. 사실 이문제는 "메모리..

문제보러가기 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 DP문제로 크게 어렵지는 않았지만 나의 경우 마지막 날짜인 n일까지 일할 수 있다는 것을 놓쳐서 시간이 좀 더 걸렸던 문제였다 ㅎ,,, 문제풀이 -주어진 시간을 저장하는 t [] 배열과 금액을 저장하는 p [] 배열을 생성한 후 값을 저장한다. -해당 날짜까지 받을 수 있는 최대 금액을 저장하는 dp배열을 생성한다. -총금액 중 최대 금액을 저장하는 max를 선언한다. -여기서 중요한 점 dp배열은 dp [n]..

문제보러가기 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 � www.acmicpc.net 이문제는 보자마자 음? BFS 써야지 했다가 바로 시간 초과가 나버린 문제다. BFS의 비용을 최소화하기 위해 그룹핑하는 과정부터 필요하다. 이걸 분리 집합이라고 부른다. 문제풀이 -그룹화가 된 배열 정보를 담을 수 있게 group [][] 배열에 0 끼리 묶음 정보를 저장한다. -여기서 포인트는 BFS를 통해 그룹을 만들 때 이미 만들어진 그룹에 속한 인덱스는 탐색하지 않고 넘기는 것 -벽이 아닌 즉 0인 인덱스는 한 그룹에..