본문 바로가기

분류 전체보기135

[백준] 11726 2×n 타일링 풀이 Java 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net DP 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 풀이 import java.util.Scanner; public class Main { static int[] dp; public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); dp =.. 2022. 7. 13.
[HackerRank] Abbreviation 풀이 Java Abbreviation | HackerRank Make two strings equal www.hackerrank.com DP 문제 a : daBcd b : ABC a는 소문자를 대문자로 변경하거나, 모든 소문자를 삭제하는 두 가지 액션을 할 수 있다. 그 결과 a == b 가 될 수 있는지 확인. 참고 처음엔 간단하게 두 문자를 비교하려고 했다. a의 처음부터 시작해서 소문자면 한칸 뒤로가고 대문자이면서 b와 같으면 b의 인덱스를 증가시키는 방법으로 했는데 16문제 중 4문제가 실패했고 이유를 찾아보니.. KeEdC KEC 이런 케이스 때문에 한 칸씩 뒤로 가면서 확인하는 방법은 쓰면 안됨 XX 유사한 문제 나오면.. 이차원 배열 사용하는 dp 떠올리는게 좋음 코드 i 가 b(ABC) j가 a(daBc.. 2022. 7. 12.
Alternating Characters 풀이 Java Alternating Characters | HackerRank Calculate the minimum number of deletions required to convert a string into a string in which consecutive characters are different. www.hackerrank.com 문제 5 AAAA BBBBB ABABABAB BABABA AAABBB 인접한 모든 문자가 같지 않으려면 몇 글자를 삭제해야 하는가? 아주 기본문제구만 허허.. class Result { public static int alternatingCharacters(String s) { char[] arr = s.toCharArray(); int res = 0; for(int i = .. 2022. 7. 11.
Recursion: Davis' Staircase 풀이 Java Recursion: Davis' Staircase | HackerRank Recursion: Davis' Staircase | HackerRank We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies. www.hackerrank.com Recursion and Backtracking에 DP를 살짝 얹은 문제 피보나치와 비슷하게 공식을 만들면 되지만, n이 커지는 경우를 생각해서 DP를 사용해야 한다. return stepPerms(n - 1) + stepPerms(n - 2) + st.. 2022. 7. 10.
Strings: Making Anagrams java 풀이 Strings: Making Anagrams | HackerRank How many characters should one delete to make two given strings anagrams of each other? www.hackerrank.com 시간복잡도 참고 https://hbase.tistory.com/185 [Java] 컬렉션들의 시간복잡도 (Collection Big-O) 자바를 이용해서 알고리즘 문제를 풀거나 큰 사이즈의 데이터를 다룰 때, 컬렉션들의 정확한 시간복잡도(Big-O)를 알고 사용하는 것이 중요하다. 자칫 불필요하게 느린 컬렉션이나 메소드를 사용 hbase.tistory.com list.contains의 시간복잡도는 O(n) 이기 때문에 내 풀이의 시간복잡도는 O(n^.. 2022. 7. 9.
Hash Tables: Ice Cream Parlor 풀이 java Hash Tables: Ice Cream Parlor | HackerRank Help Sunny and Johnny spend all their money during each trip to the Ice Cream Parlor. www.hackerrank.com 포인트는 카테고리에 있는 것처럼 HashTable (HashMap)! 1. cost 값들을 HashMap에 저장하고 2. for : cost 값을 하나씩 가지고 오며 money-cost 값을 구함 3. money-cost 값이 hashmap에 있는지 확인하고, 있으면 return 이렇게 하면 O(n)의 시간복잡도를 가져서 시간초과가 안남 import java.io.*; import java.math.*; import java.security.*.. 2022. 7. 9.
반응형

티스토리툴바