본문 바로가기

알고리즘 문제 풀이207

백준 - 나이트의 이동 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/7562 [문제 설명] 체스판의 시작 좌표와 도착 좌표가 주어졌을 때, 도착 좌표까지 몇번만의 이동할 수 있나? [접근 방법] BFS로 풀었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; p.. 2022. 1. 4.
백준 - 1(JAVA) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/4375 [문제 설명] 1,11,111,1111,11111 주어진 숫자를 배수해서 만들 수 있는 1로 이루어진 숫자는 몇번째 숫자인지 구하시오. 예: 입력이 3일 때 3에 37을 곱한 111이 1로 이루어진 숫자다. 즉, 1로 이루어진 세번째 숫자. 입력이 7일 때 111111은 7의 배수다. 즉, 7로 이루어진 6번째 숫자. [접근 방법] 문제를 딱 봤을 때, 엄청 쉽네 생각하고 풀었다가 오버플로우나 시간 초과나서 망하기 좋은 문제. 백퍼센트 각각의 값에 관계가 .. 2022. 1. 4.
백준 - 촌수 계산 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/2644 [문제 설명] 촌수 구하기 [접근 방법] BFS로 걸리는 거리가 촌수다. [내 답안 수정하기] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedRea.. 2022. 1. 2.
백준 - 마인크래프트 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/18111 [문제 설명] N*M 크기의 맵이 있을 때, 높이를 나라시한다고 했을 때, 최소시간을 구하시오. 최소시간이 여러 개면 가장 높은 높이를 리턴하시오. [접근 방법] 현재 땅의 높이 중 최소 높이부터 최대 높이까지 모든 경우를 만들어보고, 그 중에 시간이 가장 작고, 높이가 가장 높은 것을 리턴한다. 3 4 99 0 0 0 0 0 0 0 0 0 0 0 1 위의 테스트 케이스라면 최소 높이가 0 최대 높이가 1이므로, 0부터 1까지 모든 경우의 수를 구한다. .. 2021. 12. 31.
백준 - 꽃길 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/14620 [문제 설명] 땅에 꽃을 3개 부화시킬려고한다. 가장 돈이 적게 들게 땅을 사는 방법은? [접근 방법] 완전탐색 문제다. 꽃은 왼쪽 오른쪽 위 아래 크기이기 때문에, 1~땅의 크기-1까지 놓을 수 있다. 땅의 크기가 6이상 10이하이므로 면적은 최소 36에서 100이 된다. 시간복잡도는 꽃을 심을 때마다 면적을 전부 검색하며, 꽃의 개수는 3개이므로 O(면적^3) 땅의 크기를 N으로 줬을 때, 면적은 N^2이니 O(면적^3)은 O(N^6)이 된다. 언뜻 .. 2021. 12. 31.
백준 - 팰린드롬 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/8892 단어 k개 중에서 2개를 붙였을 때, 그 수가 팰린드롬(앞에서 읽는 거랑 뒤에서 읽는 거랑 같으면)이면 그 문자를 출력하고, 없으면 0을 출력하시오. [접근 방법] 언뜻 보면 k개의 단어 중 2개를 선택하는 순열 문제 같지만, 만약에 ab aba가 단어로 주어지면 ab+aba => ababa는 팰린드롬이지만 abaab는 팰린드롬이 아니다. 따라서 kC2(조합)가 아닌 kP2(순열)가 된다. 그러므로 시간 복잡도는 O(kP2). kP2를 단순화하면 k!/(k.. 2021. 12. 30.

티스토리툴바