프로그래머스 AND 백준17 백준 10971 동적 계획법으로 풀 수 있다는데 아직 안배웠다. 그래서 재귀(백트래킹)로 풀었다. 어차피 n 수가 적기 때문에 1. 하나하나의 순열을 모두 구하고 2. 거쳐간 order의 비용이 모두 0이 아닌 경우에 3. answer와 비교를 통해서 답을 업데이트한다. 풀고 나서 생각난건데 visited[]에서 if문을 걸 때 &&을 활용해서 비용 조건도 그때 확인했다면 더 좋았을 것 같다. package programers; import java.util.Arrays; import java.util.Scanner; public class BOJ10971 { static int[][] graph; static boolean[] visited; static int answer = Integer.MAX_VALUE; sta.. 2024. 4. 2. 프로그래머스 - 석유시추 구현 1차 절망, 시간복잡도 2차 절망이었다. 처음에는 그냥 bfs + visited로 해서 열마다 방문 횟수 초기화를 해주면서 계속 돌렸는데, 정답은 구할 수 있지만 효율성 테스트에서 전부 시간 초과가 나왔다. 그래서 생각한 건 방문 횟수 초기화를 하지 말고 모든 그래프를 돌며 수행한 bfs의 결과를 배열로 만들어서 [left, right, count] 전체 열을 돌면서 이중 배열을 만들어주고 전체 열만 돌면서 left = col 인 경우 count++ 를 해주고 나온 값의 max를 리턴해줬다. 이렇게 하니까 시간복잡도는 줄일 수 있었는데 문제 2,3 번에서는 시간초과가 나왔다. 그러다가 생각난 게 굳이 배열을 만들어서 for문을 돌릴 필요 없이 저 배열 하나를 add 하는 대신 처음에 전체 열의 co.. 2024. 3. 25. 백준 2573번 bfs 배우니까 신세계가 따로 없다. 뭐 말로는 dfs로 풀 수 있는 건 bfs로 풀 수 있는데 bfs로 풀 수 없는 건 dfs로 풀 수 없다니까 bfs라도 잘 알아놓고 가자. 일단 그래프를 만든다. 하지만 여기는 동서남북 모든 노드의 정보를 알아야 하기 때문에 테두리를 둘러줘야한다. 그래서 그래프의 넓이를 n+1이 아닌 n+2로 만들어준다. why? 1에서 n까지가 행과 열의 넓이라고 가정해보자 1 1 1 1 1 1 1 1 1 11 11 1 1 1 1 11 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1이 들어가있는 노드가 그래프의 시작이라고 가정하자. 시간의 흐름을 옆 노드를 기준으로 반영하기 위해서는 위, 아래, 좌, 우 노드가 모두 있어야만 한다. (그렇지 않다면 첫 번째 인덱스를 돌다가.. 2024. 3. 24. 백준 10448 배워두면 쓰기 좋은 개념이 나와서 써본다. 배열로 어떠한 조건이 맞는지 아닌지 확인할 때는 이렇게 boolean의 배열을 만드는 게 좋다. 이런 배열을 여러번 쓸 때는 이런 조건을 한번만 정의해두면 되기 때문에 시간복잡도에서 굉장히 유리하다. 아이디어는 다음과 같다. 삼각수 두개를 합한 배열 + 삼각수를 합한 배열 == 삼각수 세개를 합한 배열 1. 삼각수 두개를 합한 boolean의 배열을 만든다. 2. .삼각수 세개를 합한 boolean의 배열을 만든다. 3. 입력된 수의 index가 tripleOfEuraka에 속하는지 확인한다. (배열 인덱스가 입력된 수이고, 그에 대한 true, false로 알 수 있다.) package programers; import java.util.Scanner; pub.. 2024. 3. 14. 백준 3273 번 - 자바 아마 이 문제는 이중포인터로 풀라고 만든 것 같은데 나는 먼저 생각난게 TreeSet이라서 트리셋으로 풀었다. 집합은 뭘 해도 시간복잡도가 낮으니까. 아이디어는 이거다. 1. 어차피 중복을 허용하지 않으니까 더한 값이 x가 될 때 짝은 무조건 하나밖에 없으므로 모두 지우면서 result++해준다. 2. a + b > x라면, 가장 작은 수인 a랑 더해도 큰거기 때문에 b를 삭제한다. 3. a + b < x라면, 가장 큰 수인 b랑 더해도 작은거기 때문에 a를 삭제한다. 인덱스가 하나거나 없으면 break; TreeSet은 집합이지만 알아서 정렬이 되는 자료구조다. 참고하자. 왜인지 모르겠는데 set.size가 1일 때는 어차피 처음에는 계속 NoSuchElementException이 떴는데 이유를 모르다.. 2024. 3. 12. 백준 26069번 java 말이 길지만 결국 "ChongChong" 과 같은 line에서 입력되면 count가 하나 늘어나는 구조 + 해당 입력값도 ChongChong과 똑같은 능력을 가진다는 말이다. 풀이: "ChongChong"이라는 String이 들어간 set (dancingPeople)을 만들고, contains를 이용해 입력값 둘 중 하나가 set에 있다면 둘 다 set에 add하고 마지막에 size값을 출력한다. set은 중복을 허용하지 않으므로 중복된 값을 add해도 상관 없다. import java.io.*; import java.util.HashSet; public class Main { public static void main(String[] args) throws IOException { BufferedRea.. 2023. 10. 25. 이전 1 2 3 다음
