알고리즘 풀이/백준 (48) 썸네일형 리스트형 [백준] 1016번: 제곱 ㄴㄴ 수 - JAVA 🔗 문제 링크 BOJ 1016번: 제곱 ㄴㄴ 수 1016번: 제곱 ㄴㄴ 수 첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 📝 풀이 과정 min과 max 사이에서 1이 아닌 제곱수로 나누어떨어지지 않는 수를 찾는 문제이다. min과 max의 범위가 $10^{12}$으로 굉장히 크기 때문에 하나씩 조사하는 것은 불가능하댜. 어떻게 시간을 줄일 수 있을까 고민을 하던 중 범위 내에서 '소수 제곱'의 배수를 제거해준다면 훨씬 빠르게 제거가 가능할 것이라는 생각이 들었다. for (int i = 2; i [백준] 16236번: 아기 상어 - JAVA 🔗 문제 링크 BOJ 16236번: 아기 상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 📝 풀이 과정 문제의 규칙을 먼저 정리해보았다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다. 자신의 물고기보다 작은 물고기만 먹을 수 있다. 더 이상 먹을 물고기가 존재하지 않는다면 도움을 요청한다 먹을 수 있는 물고기가 많다면 거리가 가깝거나, 가장 위에 있거나, 가장 왼쪽에 있는 물고기 순으로 먹는다. 물고기가 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1씩 증가한다. 문.. [백준] 18870번: 좌표 압축 - JAVA 🔗 문제 링크 BOJ 18870번: 좌표 압축 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 📝 풀이 과정 예시를 통해 문제를 먼저 이해했다. // 입력 2 4 -10 4 -9 // 출력 2 3 0 3 1 문제를 보면 현재 좌표보다 작은 좌표들의 개수가 압축값이 되고, 좌표 값이 같은 여러 개의 좌표가 있어도 1개로 취급하는 것을 알 수 있다. int[] sortNums = nums.clone(); Arrays.sort(sortNums); Arrays.sort.. [백준] 17219번: 비밀번호 찾기 - JAVA 🔗 문제 링크 BOJ 17219번: 비밀번호 찾기 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 📝 풀이 과정 사이트 주소를 통해 비밀번호를 얻으면 되는 문제이다. N과 M의 범위가 10만이기 때문에 단순 반복문으로는 시간초과가 발생할 수 있다. 사이트가 중복되지 않고, Map의 경우 get과 set의 연산 모두 $O(1)$이기 때문에 Map을 사용하기로 했다. Map을 통해 주소값을 key로 두고 비밀번호를 value로 저장하였고, 출력시 get(key)를 활용해 비밀번호를 출.. [백준] 15686번: 치킨 배달 - JAVA 🔗 문제 링크 BOJ 15686번: 치킨 배달 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 📝 풀이 과정 치킨 집을 M개만큼 선택하여 각 집과의 치킨거리의 합이 가장 작을 때를 구하는 문제이다. switch를 활용해 입력 값이 1일 때는 집(home) List에 추가해주었고, 2일 때는 치킨집(chicken) List에 추가하여 위치들을 추가해 주었다. switch (sc.nextInt()) { case 1: home.add(new int[]{i, j}); break; case 2: c.. [백준] 14500번: 테트로미노 - JAVA 🔗 문제 링크 BOJ 14500번: 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 📝 풀이 과정 모든 테트로미노를 그린 뒤 탐색마다 도형을 회전시키고 대칭시키며 구할 수도 있지만 경우의 수가 너무 많아 귀찮아서 포기하였다... 예시로 그려진 테트로미노의 모양을 잘 살펴보면 ㅜ모양을 제외하면 DFS로 표현이 가능할 것이라는 생각이 들었다. 회색으로 칠해진 부분이 현재까지 탐색한 부분이고 ⭐의 위치가 현재 위치라고 할 때, 탐색할 수 있는 방향은 파란색의 화살표로 가는 방향뿐이기 때문에 ㅜ 모양의 탐색.. [백준] 11727번: 2×n 타일링 2 - JAVA 🔗 문제 링크 BOJ 11727번: 2×n 타일링 2 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 📝 풀이 과정 [백준] 11726번: 2×n 타일링 - JAVA과 이어지는 문제이다. 노란색으로 체크된 n - 1의 타일에 2x1 타일이 세로로 하나 붙은 형태를 가지고 있고, 파란색으로 체크된 n - 2의 타일에 2x1 타일이 가로로 2개 붙어있거나, 2x2 타일이 붙은 형태를 가지고 있다. 이전 문제에서 n - 2의 타일에 붙이는 타일은 2x1타일이 가로로 2개 붙은 형태만 가능했었는데, 타일이 추가되면서 대신 2x2타일도 가능하게 된 .. [백준] 11726번: 2×n 타일링 - JAVA 🔗 문제 링크 BOJ 11726번: 2×n 타일링 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 📝 풀이 과정 문제를 보고 경우의 수를 하나씩 그려보기로 했다. n = 4까지 그리고 난 뒤 확인해보면 일정한 패턴이 반복됨을 알 수 있었다. 노란색으로 체크된 n - 1의 타일에 세로 타일이 하나 추가된 모습이고, 파란색으로 체크된 n - 2의 타일에 가로 타일이 두 개 추가된 형태를가지고 있다. 따라서, $dp[n] = dp[n-1] + dp[n-2]$라는 점화식을 가지게 된다. 💡 mod 연산을 한 결과값을 출력해야 할 때에는 반.. 이전 1 2 3 4 5 6 다음
