알고리즘40 [백준 15663번 N과 M (9)] 오늘의 문제는 N과 M(9)이다. #고민의 흐름처음엔 무조건 완전탐색! 수가 중복되지 않도록 visited배열을 만들어 방문처리를 해줌과 동시에,M만큼 수를 골랐을 때, 이미 고른 조합인지를 확인해줘야 했기 때문에.다 골랐을 때 이 결과를 String으로 만들어 ArrayList에 contains 함수를 통해 이미 있는지를 확인하고있다면 넣어주고 StringBuilder에 추가 / 없다면 return을 해주었다. 코드는 다음과 같다.( 코드가 너무 커보인다면 "Ctrl + 스크롤 내리기" 하면 잘보여요 ! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" ) import java.util.*;import java.io.*;public class Main { stati.. 2024. 8. 16. [백준 9251번 LCS] 오늘의 문제는 LCS이다. #고민의 흐름처음엔 무조건 완전탐색! 최악의 경우 길이가 1000인 2개의 문자열을 각자 만들어지는 모든 문자열의 종류를 비교해 준다면..?당연히 시간 초과가 날 것이라 생각했다.(애초에 문제 이름이 LCS이기도 하고,,) 그렇다면 LCS란 무엇일까?문제에 나와있듯이, LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제란문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 과거에 이미 다른 문제(공통부분문자열)로 LCS를 다룬 적이 있다!(한번 설명했던 내용기반이라 해당 문제가 보다 설명이 자세할 수 있다. 부족한 부분은 해당 문제로 채워보자.)기억이 가물가물하지만 이참에 제대로 혼자 풀어보려 했다.메.. 2024. 8. 15. [백준 17626번 Four Squares] 오늘의 문제는 Four Squares이다. #고민의 흐름처음엔 무조건 완전탐색!처음엔 너무 쉽게 생각했었다.문제를 보자마자 가장 큰 제곱수부터 0이 될 때까지 빼주면 되는 거 아닌가?생각하였고, 이를 바탕으로 코드를 작성하니 예제 3번에서 틀리게 되었다..가장 큰 제곱수가 선이라는 보장이 없었기 때문이다! 시작된 나의 고민 ,, 그럼 재귀를 통해 해당수 ~ 1까지 다 해줘야 하나 ,, 일단 해보자!! 코드는 다음과 같다.( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" ) import java.util.*;import java.io.*;public class Main { static int .. 2024. 7. 18. [백준 11727번 2xn 타일링 2] 오늘의 문제는 2xn 타일링 2이다. 처음엔 무조건 완전탐색! 코드는 다음과 같다.( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )import java.util.*;import java.io.*;public class Main { static int N, cnt; public static void main(String [] args)throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBui.. 2024. 7. 11. [백준 9461번 파도반 수열] 오늘의 문제는 파도반 수열이다. 처음엔 무조건 완전탐색! 이 문제는.. 보고 규칙성을 찾아야만 할 것 같았다.처음에는 많이 헤맸지만..!찾았다 빈틈의 실..!P(6) 이후인 P(N)들은 그 값이 P(N-1) + P(N-5)라는 사실을 알게되었다.그리고 N의 범위는 ( 1 아예 길이가 100정도인 배열을 선언해 해당 idx의 값들을 구해주고 출력만 하도록 코드를 작성하였다. 코드는 다음과 같다.( 코드가 너무 커보인다면 "Ctrl + 스크롤 내리기" 하면 잘보여요 ! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )import java.util.*;import java.io.*;public class Main { public static void main(Stri.. 2024. 7. 10. [SEWA 1249번 보급로] 오늘의 문제는 보급로이다. 처음엔 무조건 완전탐색! 이 문제를 보고 BFS를 사용해야겠다는 생각을 했다.하지만 단지 방문처리조건 하나만으로 목적지 도착시 값이 최소로 걸린 시간이라 보장할 수 있을까?결론은 아니다. 문제에 제시된 예시만 확인해도 아닌 경우가 많다는 것을 알 수 있다. 그렇다면 어떤 방법을 통해서 이를 해결할 수 있을까? 나는 좌표마다 방문처리와 현재까지의 최소 시간을 저장해 비교하는 방법으로 해결했다. 코드는 다음과 같다.( 코드가 너무 커보인다면 "Ctrl + 스크롤 내리기" 하면 잘보여요 ! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )import java.util.*;import java.io.*;public class Solution { .. 2024. 7. 10. [백준 12865번 평범한 배낭] 오늘의 문제는 평범한 배낭이다. 처음엔 무조건 완전탐색! 첫 접근은 재귀함수를 해당 물품을 챙겼을 때, 물품의 수와 버틸 수 있는 무게를 확인하고챙기고 or 챙기지 않고 진행하는 방법으로 구현하였다. ( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )import java.util.*;import java.io.*;public class Main { static int N, K, info[][], max; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe.. 2024. 7. 2. [백준 13265번 색칠하기] 오늘의 문제는 "색칠하기"이다. 처음엔 무조건 완전탐색! 2가지 색으로 색칠이 가능한지 확인하는 문제이고, 입력이 두 동그라미(노드)를 연결하는 내용이라 생각하였다 !각 동그라미(노드)들을 연결시켜놓고 상태(색)을 저장해주는 식으로 구현한다면 문제를 풀 수 있을것이라 생각했다.동그라미의 개수 n의 범위와 직선의 개수 m의 범위를 확인했을 때, 시간초과를 고려하지 않아도 될 것 같았다. 그래서 작성하기 시작한 코드는 아래와 같다 !( 코드가 너무 커보인다면 "Ctrl + 스크롤 내리기" 하면 잘보여요 ! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )import java.util.*;import java.io.*;public class Main { static A.. 2024. 6. 1. [백준 5582번 공통 부분 문자열] 오늘의 문제는 "공통부분 문자열"이다. 처음엔 무조건 완전탐색! 각 문자열에 다중 for 문을 적용하여 선택되는 문자열들이 같은지 비교하며 그 수를 세준다.하지만 한 문자열은 최대 4000자까지 가능하고 두 문자열 모두, 모든 길이의 부분 문자열을 구한다면 시간초과를 피할 수 없다. 그리하여 생각한 첫 방법은..!A문자열만 모든 부분 문자열을 확인하며 B문자열에 포함되는지 확인한다면..?import java.util.*;import java.io.*;public class Main { public static void main (String [] args) throws IOException { BufferedReader br = new BufferedReader(new Input.. 2024. 5. 31. 이전 1 2 3 4 5 다음
