전체 글

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 풀이 카드뭉치가 여러개 있고 한 뭉치씩 차례대로 합칠 때 카드의 갯수가 적은 순서로 합치면 된다. 카드 갯수가 적은 뭉치 2개를 하나로 만들고 , 만들어진 하나의 뭉치를 또 비교대상으로 쓰면 된다는 것 예를들어 30 40 50 60 이 있다고 가정하면 30+40 = 70 이 되고 , 70장의 하나의 뭉치를 50장짜리 뭉치랑 합치는 것이아닌 50 60 70 중에 갯수가 적은 순의..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제 풀이 수학적으로 더 쉽게 풀 순 있지만 , 완전탐색 그리디를 연습중이므로 완전탐색으로 접근하였다. 주어진 단어들의 알파벳들이 몇 가지인지 리스트에 저장. 알파벳에 0~9 까지의 숫자들을 완전탐색으로 매핑 탐색이 진행될때마다 depth 카운트를 하나씩 증가시키면서 주어진 단어의 길이와 depth가 같아질 때 탐색을 그만하고 계산해서 제일 높은 값이 나오면 끝 1 2 3 4 5 6 7 8 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 12주차 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 풀이 입장 피로도와 소모피로도 두 가지가 있는데 만약 입장컷이 큰 순서대로 간다면 .. ? => 예제에서 3번째 던전을 못 돌기때문에 fail 그렇다고 작은 순서대로 간다면 .. ? => 입장컷이 큰 것이 나중에 나오면 못 돌기때문에 fail 결론 => 완전탐색 던전의 방문여부를 visit , 던전을 통과한 시점으로 남은 피로도를 tired , 던..

https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 문제 풀이 첫번째. 1면, 2면, 3면 인 경우의 최소합을 각각 구하기 두번째. N개 일때 1,2,3 면이 각각 몇개 나오는지 구하기 1. 3면이 나와야 하는 경우 - 맨 윗면 꼭지점 부분 4군데 : 4 2. 2면이 나와야 하는 경우 - 전체 모서리 수에서 육면체 꼭지점 부분을 뺀 값 + 맨 아래 꼭지점부분 4 : 8(N-2)+4 3. 1면이 나와야 하는 경우 - 각 면마다..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 풀이 상어 기준으로 bfs 탐색 시작하여 거리가 가장 가까운 물고기를 priorityQueue에 먼저 넣는다. 탐색이 끝났을 때 , 큐의 맨 앞에 있는것을 먹거나 물고기가 없을 경우엔 종료하면 끝. 큐에 담는 이유 1. 거리가 가까운 순 2. 같은 거리에 있는 것이 여러개 있으면 좌표평면상 1.위쪽 -> 2.왼쪽 우선순위로 먹음.(이게 중요) bfs 탐색으로 위,왼쪽을 먼저 하는게 아..

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 재귀호출로 이동할 수 있는 다른 도시들을 완전 탐색을 진행하면서 만약 모든 도시를 다 탐색 했을 경우 , 방문했던 도시를 다시 방문하지 않은 것으로 백트래킹시켜준다. 모든 도시를 다 탐색했을 경우엔 이때까지 비용들의 총합과 현재 최소비용을 비교하면서 갱신하..

https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제 풀이 완전탐색 + 백트래킹 문제이다 주어진 numbers 로 모든 순열을 만들어서 소수인지아닌지 판별하여 카운트를 리턴하면된다. String -> int 형으로 바꿀 때 , "01234" 이런것도 1234 로 변환할 수 있는 메서드가 Integer 라이브러리에 있다. Integer.valueOf 라는 메서드로 변환을 한 다음, 중복을 허용하지..

문제 https://programmers.co.kr/learn/courses/30/lessons/87694 코딩테스트 연습 - 11주차 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 programmers.co.kr 풀이 좌표평면 위에 여러 사각형이 겹쳐지는데 , 이들을 겉 돌면서 최종목표까지 탐색하는 방법이다. 사각형이 그려지는 면적을 allowed로 체크해주고 겉 둘레만 돌기위해 visit 배열로 사각형 내부만 true 로 준다. (외부는 false 그대로 놔둠) 여기서 중요한데 , 만..