본문 바로가기

전체 카테고리361

[알고리즘] 프로그래머스 - 여행경로(dfs/bfs) 1. 문제 2. 문제풀이 처음에 풀때 인접행렬을 이용해서 인접행렬의 방문한 곳은 다시 방문하지 않는 형태로 풀었었다. 하지만 항공사를 여러번 방문 할 수 있기 때문에 인접행렬이아닌, 항공권을 사용했는지를 체크하는 형태로 바꾸었다. 주어진 조건중에 알파벳 순서가 앞서는 경로를 return 하라는 조건을 각 배열을 정렬해야하나 했다가 String으로 방문 가능한 경로를 ','로 이어주고 그 Stirng들을 저장한 list를 정렬하는 방식으로 수정하였다. 1. 출발 항공사가 "ICN"일 경우 그 항공권을 사용했다고 표시해주고 dfs알고리즘을 호출한다. 2. route에 현재 경로를 더해주고, 현재 사용하지 않은 티켓중에 이전 도착지와 현재 티켓의 출발지가 같다면 티켓을 사용했다고 표시하고 dfs 알고리즘을 다.. 2020. 8. 8.
[알고리즘] 프로그래머스 - 단어변환 (dfs/bfs) 1. 문제 2. 문제풀이 현재 주어진 단어를 한글자씩 수정해서 최종 목표 단어로 변환이 가능한지를 구하고, 만약 변환이 가능하다면 몇번만에 가능한지 최소 변환 횟수를 구하는 문제였다. 현재 단어에서 words 배열에 있는 단어로 변환이 가능하다면 visit 배열에 방문을했다고 표시를 한 후 dfs 탐색 방법을 이용해서 탐색을 진행한다. dfs의 base case로는 전부 방문했거나, 현재 단어와 찾는 단어가 같을 경우 탐색을 종료했다. 그리고 최소 횟수를 계속 갱신하여 최종적으로 minNum을 반환한다. 변환이 불가능할 경우 0을 반환한다. class Solution { int minNum = 999999999; public void dfs(boolean[] visit, String[] words, St.. 2020. 8. 8.
[알고리즘] 프로그래머스 - 카펫 (완전탐색) 1. 문제 2. 풀이 중앙은 노란색으로 칠해져 있고, 나머지는 갈색으로 칠해져 있는 직사각형(정사각형) 모양의 카펫의 가로 세로 길이를 구하는 문제였다. 우선 사각형 형태이므로 갈색 격자 개수와 노란색 격자 개수를 더한 수는 무조건 짝수가 나올 것이다. 우선 2개를 더한 수의 약수들을 구한다. 그리고 가로의 길이가 더 크므로 i와 곱해서 sum이 나오는 숫자가 가로의 길이가 된다. 그리고 나서 주어진 모양을 만족하는지 검사를 한다. 가로는 2개 이므로 가로 길이에 2를 곱해서 구해주고, 세로도 마찬가지로 2개지만 가로 길이를 구할때 각 사각형의 맨끝을 가로길이에서 이미 포함하고 있기 때문에 4를 빼준다. 그러면 쉽게 답을 구할 수 있다. class Solution { public int[] calRect.. 2020. 7. 30.
[알고리즘] 프로그래머스-숫자 야구 (완전탐색) 1. 문제 2. 나의 코드 순열과 해시맵, 완전 탐색을 이용해서 풀었다. 우선 1~9까지의 서로 다른 3자리 수를 구하는 permutation 메소드를 구현하였다. 그리고 구한 순열의 숫자와 현재 baseball에 들어온 수들과 전부 비교하여 스트라이크 수와 볼 수를 전부다 만족하는 수이면 해시맵에 그 키에 대해서 1씩 더해주었다. 결과적으로 baseball의 길이와 해시맵에 들어가 있는값이 같다면 케이스를 모두 만족하는 수이므로 answer를 1씩 증가 시켜주는 방식으로 답을 구했다. import java.util.*; class Solution { private static Map map; public void permutation(boolean[] visited, int depth, String a.. 2020. 7. 26.
[알고리즘] 프로그래머스-소수찾기 (완전탐색) 1. 문제 2. 코드 순열을 이용해서 모든 경우의 수를 완전탐색하는 문제였다. dfs알고리즘을 순열에 적용했다고 생각하면된다. 현재 입력받은 문자열을 배열에 int로 저장을하고, permutation 메소드를 재귀로 돌려주었다. 방문한 곳은 true로 표시를하고 다시 방문을 하지 않았다. base case에서는 전부다 선택을 안한 케이스와, 소수는 2이상부터 있으므로 0과 1은 넣어주지 않았다. 또한 맨앞이 0으로 시작하는 케이스도 세지 않았다. 그리고 중복되는 경우의 수들이 있어서 map을 이용해서 중복된 값을 제거해주었다. 마지막으로 map에 넣은 키값들을 다시 빼내서 정수로 바꾸고 소수판별 메소드로 검사를해주었다. import java.util.*; import java.lang.*; class S.. 2020. 7. 20.
백준 10974번 모든 순열 (java) 1. 문제 2. 코드 N이 주어졌을 때 구할 수 있는 모든 순열을 사전순으로 출력하는 문제이다. DFS 알고리즘을 순열을 구했다. 1. 필요한 배열 : 데이터를 담을 배열과 방문했는지 안했는지를 기록할 visited 배열 2개를 만든다. 2. 첫자리에 올 수를 반복문을 통해 하나씩 넣는다. 사전순이으로 출력해야하니까 1부터 쭉 넣어준다. 3. 배열에 넣은 수는 visited[] 배열을 통해 방문 했음을 표시한다. 그리고 방문한 곳을 제외하고 다시 반복문을 돌린다. 4. 모든곳을 방문하면 현재 값을 출력해주고 return으로 종료해준다. depth는 현재가 몇번째 반복문을 돌고있는지를 표시해주고, start는 이번에 넣을 데이터이다. base case로 depth가 n과 같아지면 종료를 해준다. impor.. 2020. 7. 20.

티스토리툴바