Algorithm/백준알고리즘
(4)
백준15685번: 드래곤 커브 자바 해설 (삼성 SW 역량 테스트 기출 문제)
문제 : https://www.acmicpc.net/problem/15685 정답은 맨 아래에 있습니다. 문제에서 가장 큰 힌트는 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수 즉 변이 기준이 아닌 꼭짓점이 기준입니다. (문제에서 꼭짓점만 찾으면 된다는 거죠) 저는 3단계로 나눠서 풀었는데요. 방향 구하기 꼭짓점 그리기 1×1인 정사각형 구하기 1. 방향 구하기 먼저 드래곤 커브의 방향을 구합니다. 무슨 말인지 문제에 나와 있는 예시의 그림으로 보여드리겠습니다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽으로 3세대까지 그린 드래곤 커브입니다. 이 그림에서 화살표의 색깔이 다른 게 보이시나요? 세대가 증가할 때마다 이전의 드래곤 커브를 끝 점을 기준으로 ..
Algorithm/백준알고리즘
2019. 4. 7. 02:12
[백준] 5052번 전화번호 목록 (시간초과 해결과정)
문제 링크 - https://www.acmicpc.net/problem/5052 이 문제를 풀 때는 정말 쉽게 생각했다. 정규표현식을 사용해서 비교하면 되겠는데? 하고 풀었더니 시간초과가 나왔다. 그 다음에는 알고리즘 스터디 이 주의 주제였던 ChainHash를 사용해서 풀어보았다. 역시나 시간 초과를 했다. 해결하기 위해서 다양한 방법을 시도하고 정답을 맞춘 후에도 계속 다양한 방법을 시도해서 개선을 했다. 시간초과로 실패 목록 직접 ChainHash 구현 정규표현식 사용해서 모두 비교 직접 ChainHash 구현 번호의 앞자리로 해시코드 생성 후 버킷에 담음 ex) 1234 - table[1], 955 - table[9] Sort 후 앞자리 같고 길이가 다르면 비교 정규표현식으로 비교 해결 방법 실패..
Algorithm/백준알고리즘
2018. 12. 28. 17:42
[백준] 2751번:수 정렬하기2 (자바)
https://www.acmicpc.net/problem/2751 이 문제는 오름차순으로 정렬만 하면 간단한 문제이지만 시간제한이 있기때문에 시간복잡도가 O(n)인 정렬을 사용해야한다.그래서 정렬중에 평균 속도가 가장 빠른 퀵소트를 사용해서 풀었다. import java.util.Scanner; // 퀵소트를 이용한 수 정렬하기2 public class Main { static void quickSort(int[] nums, int left, int right) { int pl = left; int pr = right; int x = nums[(pl + pr) / 2]; do { while (nums[pl] x) pr--; if (pl
Algorithm/백준알고리즘
2018. 10. 9. 23:10
[백준] 2947번: 나무 조각 (자바)
https://www.acmicpc.net/problem/2947 123456789101112131415161718192021222324252627282930import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; //버블정렬public class Main { public static void main(String args[]) throws IOException { int[] piece = new int[5]; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nums; nums = br.readLine..
Algorithm/백준알고리즘
2018. 10. 7. 22:52