코테5 [백준] 17136번 색종이 붙이기 - JAVA ✍️풀이방식 1. 문제 분석 1이 있는 칸에만 색종이를 붙여야 하고 칸에 딱 맞게 붙여야 하는 것. 각 종류의 색종이를 5개씩 가지고 있기 때문에 한 종류 마다 5개까지 사용할 수 있다. 즉 전체 색종이 개수는 25개이다. 색종이를 붙일수 있는 경우의 수를 백트래킹 알고리즘을 이용하여 구하면 된다. 지금까지 연습했던 문제들 중에 가장 난이도가 높은 문제였던 것 같다... 2. 풀이 과정 1. 색종이를 붙일 수 있는 1번째 위치를 찾는다. 2. 탐색 위치는 왼쪽 위에서 시작하여 오른쪽으로 이동하고, 오른쪽 끝에 도달하면 한 줄 아래로내려가서 다시 왼쪽부터 이동하는 방식으로 진행한다. (가지치기를 극대화 하기 위해서 큰 색종이부터 탐색한다) 3. 현재 선택한 위치에 가지고 있는 색종이.. 2025. 9. 15. [백준] 9663번 N-Queen 배치하기 - JAVA ✍️풀이방식 1. 문제 분석 N-queen은 전형적인 백트래킹으로 풀 수 있는 문제이다. 크기 N × N 체스판 위에 퀸 N개를 서로 공격하지 않게 놓는 문제. 체스에서 퀸은 가로, 세로, 대각선으로 움직일 수 있으므로 같은 행, 열, 대각선에는 퀸이 동시에 존재할 수 없음. 즉 같은 행에는 퀸이 1개만 존재할 수 있음. 모든 행에 퀸을 1개씩 배치해야 N개의 퀸이서로 공격하지 않도록 놓을 수 있다. 2. 풀이 과정 퀸을 한 행씩 배치하면서, 현재까지 놓은 퀸이 조건을 만족하지 않으면 즉시 가지치기(백트래킹) -> 탐색을 종료하고 이전 단계로 돌아간다. 마지막 행까지 퀸 배치 성공하면 경우의 수 +1, 백트래킹 전체를 종료하면 경우의 수를 출력한다. 맨 위 행부터 시작해 각 행마다 퀸을.. 2025. 9. 12. [백준] 15649번 N과 M - JAVA ✍️풀이방식 1. 문제 분석 1부터 N까지 자수 중에서 중복 없이 M개를 고른 수열또한 수열은 사전 순으로 증가하는 순서, 즉 오름차순으로 정렬하여서 출력해야한다. 현재 수열에서 추가할 수 있는 자연수를 탐색, 자연수가 기존 수열에서 이미 사용한 수라면 해당 수를 선택한 탐색은 진행하지 않고 이전 단계로 돌아간다(가지지치기) 수열의 길이가 M이 될 때 수열의 정보를 출력한다 . 2. 풀이 과정 일단 작은 수 부터 탐색하도록 기준을 잡으면 오름차순 조건을 자연스럽게 만족할 수 있다. 가지치기 기준은 이미 수열에 포함한 수(중복 허용 x) 이전 단계로 돌아가는 로직은 재귀 함수 형태로 탐색하면 자연스럽게 구현된다. 🖥️문제풀이 import java.io.*;import java.util.*.. 2025. 9. 11. [알고리즘] 백트래킹 (Backtracking) ✏️해당 포스트는 인프런 알고리즘 코딩테스트 핵심이론 강의를 토대로 정리한 내용입니다. ⭐백트래킹이란? 문제를 해결하는 탐색 기법을 말한다. 문제를 해결할 수 있는 모든 경로를 탐색하면서 선택한 경로가 유효하지 않거나 조건에 만족하는 해를 찾지 못할 경우, 이전 단계로 되돌아가 다른 경로를 시도하는 알고리즘 즉 다시 정리하자면, 해(정답)를 찾기 위해 모든 경우의 수를 탐색하되, 탐색 도중에 해가 될 수 없는 경우(불필요한 경로) 를 만나면 더 이상 진행하지 않고 되돌아가(backtrack) 다른 경로를 시도하는 탐색 기법. 구현 방식재귀 함수로 구현하는 경우가 많음. (DFS의 개념과 구현방식이 매우 유사, 다만 DFS는 모든 노드를 탐색하는 것을 목적으로 함) 가지치기(pruning)를 통해.. 2025. 9. 11. [백준] 12819번 DNA 비밀번호 ✏️인프런 Do it! 알고리즘 코딩테스트 java 편을 듣고 푼 문제입니다. ✍️풀이방식 슬라이딩 윈도우 알고리즘이란?2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결한다 → 투 포인터 알고리즘과 비슷하고 원리도 간단 keypoint : 슬라이딩 윈도우 원리 이해 , 실제 문자열과 관련된 배열 처리 슈도 코드 작성//배열 저장 (s 배열 p 배열 저장 ) S(문자열 크기) P (부분 문자열의 크기) A( 문자열 데이터) CheckArr(비밀번호 체크 배열) //변수 선언 myArr(현재 상태 배열) cheackSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수) P 범위(0~p-1)만큼 s 배열에 적용하기 , 유효한 비밀번호인지 판단for(i를 .. 2024. 12. 29. 이전 1 다음
