728x90 백준14 [백준] 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. [백준] 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. [백준] 2743 단어 길이 재기 - JAVA ✍️풀이방식 String의 length 메소드를 사용해서 길이를 반환했다String 관련 메소드 🌟문자 추출 charAt()문자열 비교 equals()바이트 배열로 변환 getBytes()문자열 찾기 indexOf()문자열 길이 length()문자열 대치 replace()문자열 잘라내기 substring()알파벳 소대문자 변경 toLowerCase(), toUpperCase()문자열 앞뒤 공백 잘라내기 trim()문자열 변환 valueOf() 🖥️문제풀이 import java.util.*;import java.io.*;public class Main{ public static void main(String[] args)throws IOException { BufferedRead.. 2024. 11. 23. [백준] 9086 문자열 - JAVA ✍️풀이방식 처음에 간단하게 while문을 사용하려고 했으나 java에서는 c++이나 다른 언어처럼 whle문안에 저런 식으로 쓰는 것이 안된다고 한다. (Java에서는 C나 C++처럼 T--을 boolean 조건으로 사용할 수 없다 )while(T--){ int i=0; String str = br.readLine(); name[i]=str.substring(0,1)+ str.substring(str.length()-1, str.length()); i++; } String의 메소드 중 하나인 substring 함수를 사용해서 접근하였다. 또한 while문도 for문으로 변경해주었다.for(int i=0;i 🖥️문제풀이 impo.. 2024. 11. 20. [백준] 1940번: 주몽의 명령 - JAVA 백준에 신기한 문제가 많다는 건 알고 있었는데 냅다 이름이 주몽으로 되어있어서 좀 웃겼던 문제주몽님 보고계신가요 21세기엔 철기군을 양성하기 위해서 코딩을 합니다 ✍️풀이방식 1. 재료의 개수 , 갑옷만드는 데 필요한 수 정의 후 입력받기2. N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어짐 3. 받은 재료를 정렬해서 풀기 (후에 투 포인터 사용) 투 포인터 이동 원칙 A[i] + A[j] > M; j--; // 번호의 합이 M보다 크기 때문에 큰 번호 index 감소 A[i] + A[j] > M; j--; // 번호의 합이 M보다 작으므로 작은 번호 index 증가 A[i] + A[j] > M; j--; // 양쪽 포인터를 모두 이동시키면 count 증가 🖥️문제풀이 im.. 2024. 11. 13. [백준] 2018번: 연속된 자연수의 합 구하기 - JAVA ✍️풀이방식 투 포인터를 활용해서 풀기 O(n)의 시간복잡도 알고리즘 사용할 것 * 입력되는 연산 수가 많으면 꼭 시간복잡도를 생각해서 관련 알고리즘을 적용시켜야합니다. 투 포인터 알고리즘이란? 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때 까지 탐색하는 알고리즘1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다. (strat, end) 2. 현재 부분 합이 M과 같다면 count3. 현재 부분 합이 M보다 작다면 end를 1 증가 4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가5. 모든 경우를 확인할 때까지 2-4번 과정을 반복 투 포인터 관련 개념 참고하였습니다. https://butter-shower... 2024. 11. 11. [백준] 11659번: 구간 합 구하기 4 - JAVA 백만년만에 코테를 풀어봤습니다... (앞으로 꾸준히 풀자) ✍️풀이방식 1초에 1억번 연산 -> 0.5초면 5천만번 연산이 일어난다는 뜻 데이터의 범위가 100,000을 넘어가는 것을 주의하면서 풀 것! 합 배열을 이용한 구간합을 사용해서 문제를 풀 것 합배열, 구간합 공식 S[i] = S[i-1]+A[i] // S가 합배열 S[j]-S[i-1] // 구간합 공식 또한 받는 데이터의 양이 많기 때문에 Scanner가 아닌 Buffer로 구현할 것 (까먹지 말기...) 🖥️문제풀이 import java.util.*;import java.io.*;public class Main{ public static void main(String[] args) throws IOException .. 2024. 11. 10. 이전 1 2 다음 728x90
