hwooo

https://www.acmicpc.net/problem/2098풀이완전 탐색의 방법으로 시도하려 했으나, 이 경우 탐색해야 할 노드의 수가 많아져 시간 초과가 발생한다.알고리즘을 보니 비트마스킹과 DP가 있어 바로 풀이를 봤다.유명한 알고리즘이었으나 접근 방법이 생소해서 모르면 못 풀겠다 싶었다. [알고리즘] 외판원 순회 문제모든 도시들을 단 한번씩만 방문하고 원래 시작점으로 돌아오는 최소 비용을 구해보자!velog.io Java 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { private static final int INF = 16_000_..

https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이데이터의 수가 작지 않아서 dp를 생각했는데, 정리할 수 있는 기준이 생각나지 않았다.더 생각해보니 일단 막을 수 있는 만큼 병사를 막고, 안 되는 케이스에만 무적권을 사용해야겠다고 생각했다.우선순위 큐를 사용, 막을 수 없을 때는 현재까지 나온 값 중 가장 큰 값에 무적권을 사용했다고 판단, 병사를 복구하여 다시 탐색했다. Java 코드import java.util.*;class Solution { public int solution(int ..

https://www.acmicpc.net/problem/9466풀이처음에는 해당 학생이 팀을 가지고 있는지를 확인하고, 없다면 다시 방문하는 식으로 작성했다.이 경우 이미 탐색을 했음에도 다시 탐색해야 하고 이로 인한 방문 체크 배열을 초기화 하는 과정까지 포함되어 시간초과가 발생했다. 모르겠어서 다른 풀이를 봤다. visited, finished 배열을 사용해 각각 방문 여부와 현재 탐색하는 사이클이 끝난 여부를 저장했다.방문했지만 아직 사이클이 끝나지 않았다면, 이는 (출발점과 도착점이 동일 여부와 관계없이) 내부에 다른 사이클이 존재하는 것이므로 해당 사이클 내의 노드의 개수를 세어준다.해당 사이클을 다 탐색했다면 그 사이클 탐색을 완료했다고 표시해주면, 그 사이클에 있는 학생들은 더 이상 방문..

https://www.acmicpc.net/problem/9252풀이LCS 알고리즘으로 분류되어 있는데 해당 알고리즘을 몰라서 밑의 블로그를 참고해서 풀었다. [Algorithm] Longest Common Subsequence(LCS) 알고리즘 : 두 문자열 간 최장 공통 부분 수열 찾기🗨 개인적인 공부 목적으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :) ⭐ Longest Common Subsequence(LCS) 알고리즘은 두 문자열에서 순서를 유지하면서 공통으로mojing.tistory.com Java 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamRead..

https://school.programmers.co.kr/learn/courses/30/lessons/160585풀이주어진 게임의 결과를 보고 판단하기에는 규칙이 없기에 완전탐색으로 풀었다.게임판의 크기는 3*3 고정이므로 모든 경우의 수를 따져도 2^9 이다. 주어진 문자열 배열을 2차원 char 배열로 변경하여 순서에 따른 모든 경우의 수를 확인한다.이 때 현재 보드판이 주어진 보드판과 같다면 true를 반환, 탐색을 종료한다.또한 끝나는 조건 (한 줄 이상이 동일한 문자로 구성)이라면 false를 반환하여 다음 경우의 수로 넘어간다.(보드판이 같은 조건을 먼저 판단했기에 같지 않으면서 끝나는 조건일 때는 false를 반환)Java 코드import java.util.*;class Solution {..

https://www.acmicpc.net/problem/2252풀이순서가 정해져 있는 작업을 수행해야 하므로 위상정렬을 사용했다.학생들의 키 순서를 저장하여 앞선 사람이 없는 학생부터 차례로 탐색하며 줄을 세웠다.Java 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;public class Main { private static int N, M; private static List orders[]; ..

https://www.acmicpc.net/problem/1644풀이연속된 소수의 합으로 n이 될 수 있는 가능성을 찾는 문제다.주어진 숫자보다 적은 소수를 다 찾아 해당 값을 리스트에 저장한 후, 해당 리스트를 순회하며 부분합을 구했다.부분 합 부분 합 > 주어진 수라면 start 인덱스를 증가하며 부분합에서 뺐다. 이 때 end 인덱스로 끝까지 탐색했을 때 부분 합 > 주어진 수라면 start 인덱스를 증가하며 주어진 수가 소수일 때를 확인했다.Java 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List..

https://school.programmers.co.kr/learn/courses/30/lessons/340212 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이1 ~ 300,000 사이의 최소 레벨을 구해야 하므로 완전 탐색시 시간 초과가 날 것 같아 이분탐색을 사용했다.최소 레벨을 1 (난이도가 양의 정수라 했으므로 최소 레벨은 1 이상이어야 함), 최대 레벨을 30만으로 잡고 탐색했다.최소 - 최대의 중간값을 구해 해당 레벨일 때 주어진 퍼즐을 모두 풀 수 있는 지 확인,풀 수 있다면 현재 레벨이 높은 것이므로 최대 레벨을 낮추고, 아니라면 최소 레벨을 높이는 방식으로 풀었다.Java 코드im..