본문 바로가기

백트래킹

[BOJ] 백준 [17136] 색종이붙이기 JAVA
알고리즘,PS/백준 2022. 5. 25. [BOJ] 백준 [17136] 색종이붙이기 JAVA https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 📝문제 📝풀이 이 문제의 핵심은 그리디하게 접근해서는 풀 수 없는 문제이다. 반례) 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0..
[BOJ] 백준 [12100] 2048(Easy) JAVA
알고리즘,PS/백준 2022. 4. 28. [BOJ] 백준 [12100] 2048(Easy) JAVA https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 📝문제 📝풀이 완전탐색으로 풀어내면 되는데 2차원 이상 배열은 복사를 1차원 배열 단위로 고쳐서 .clone() 메서드를 사용해야 한다. dfs탐색하기 전에 기존 배열을 어디에 저장해놓고 dfs 탐색이 끝나면 저장된 배열을 원복하면서 탐색한다. 연쇄적으로 합쳐질 수 없기 때문에 큐를 하나 선언해서 하나씩 poll 하면서 병합을 진행한다. 1. 끝이 0 이면 큐에서 하나..
[BOJ] 백준 [16198] 에너지 모으기JAVA
알고리즘,PS/백준 2022. 4. 27. [BOJ] 백준 [16198] 에너지 모으기JAVA https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 📝문제 📝풀이 DFS 완전 탐색 문제이다. 1 2 3 4 가 주어질 때 (3) 번을 고를 경우 => energy += 2*4 가 되고 1 2 4 가 남는다. 1 4 는 고를 수 없기 때문에 남은 2번을 고르면 energy += 1*4 를 하면 최종적으로 12가 나온다. List 하나 선언해서 DFS를 돌리고 해당 위치 x 를 remove 한 뒤 백트래킹을해서 다시 x 를 넣어 주는 식으로 하..
[BOJ] 백준 [2580] 스도쿠 JAVA
알고리즘,PS/백준 2021. 12. 5. [BOJ] 백준 [2580] 스도쿠 JAVA https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net [문제] [풀이] 스도쿠 요약 : 가로줄, 세로줄, 부분 정사각형 모두 1~9까지 숫자가 한번씩만 있어야 함. 백트래킹으로 접근해야한다 빈칸에 숫자하나 넣어보고 아니면 되돌아가서 다른숫자선택하고 ... 반복 1. 빈칸은 0으로 하므로 0인 좌표들을 List에 add 2. List를 순회하면서 DFS 시작. 3. 해당 좌표에 1~9 까지 숫자가 들어갈 수 있는지 확인. 4. DFS 의 depth가 ..
[프로그래머스] [Level3] 여행경로 JAVA
알고리즘,PS/프로그래머스 2021. 11. 3. [프로그래머스] [Level3] 여행경로 JAVA https://programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr [문제] [풀이] 그래프 탐색문제이다. 처음엔 TreeMap과 같이 티켓과 정보를 한번에 저장해서 하려했으나 , 키중복에서 꼬이거나 다중 Map을 써야하는 상황이 나오는 등 쉽지 않았기때문에 티켓자체를 방문지점으로 써버렷다. 그래서 티켓의 사용여부를 boolean 타입의 visit 배열로 사용했고 그냥 완전탐색 + 백트래킹으로..
[BOJ] 백준 [10971] 외판원 순회2 JAVA
알고리즘,PS/백준 2021. 10. 21. [BOJ] 백준 [10971] 외판원 순회2 JAVA https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 DFS완전탐색 + 백트래킹 문제이다. 출발도시를 각자 주어진 도시마다 설정해놓고 dfs 재귀호출로 이동할 수 있는 다른 도시들을 완전 탐색을 진행하면서 만약 모든 도시를 다 탐색 했을 경우 , 방문했던 도시를 다시 방문하지 않은 것으로 백트래킹시켜준다. 모든 도시를 다 탐색했을 경우엔 이때까지 비용들의 총합과 현재 최소비용을 비교하면서 갱신하..
[프로그래머스] [Level2] 소수찾기 JAVA
알고리즘,PS/프로그래머스 2021. 10. 20. [프로그래머스] [Level2] 소수찾기 JAVA https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제 풀이 완전탐색 + 백트래킹 문제이다 주어진 numbers 로 모든 순열을 만들어서 소수인지아닌지 판별하여 카운트를 리턴하면된다. String -> int 형으로 바꿀 때 , "01234" 이런것도 1234 로 변환할 수 있는 메서드가 Integer 라이브러리에 있다. Integer.valueOf 라는 메서드로 변환을 한 다음, 중복을 허용하지..
LIST
Recent Posts
Popular Posts
Archives
Visits
Today
Yesterday

티스토리툴바