반응형 Computer Science25 그리디 알고리즘? 1. 문제 기다란 다리가 있습니다. 다리가 낡아 여기저기 구멍이 나서 지나가는 사람들이 종종 물에 빠지곤 합니다. 다리의 구멍을 메우기 위해서 한 칸을 이동하는 데에는 1분이 걸립니다. 다만, 배를 타고 다리의 끝으로 이동할 경우 1분이 걸립니다. 구멍이 난 곳을 1, 멀쩡한 곳을 0으로 표시한 배열 bridge가 주어졌을 때, 다리를 보수하기 위해 이동하는데 걸리는 총시간을 구하십시오. 예) 아래와 같은 다리의 경우 현위치 0 0 0 0 0 1 1 배를 타고 이동하는데 1분 + 옆으로 한 칸 이동하는데 1분 총 2분이 소요됩니다. 2. 풀이과정 firstX lastX 0 0 1 0 0 1 0 0 0 위와 같이 처음 구멍이 난 곳을 firstX라 하고, 마지막으로 구멍이 난 곳을 lastX라 할 때, 배.. 2021. 11. 4. 완전탐색 - 순열 1. 개요 n개의 숫자로 가능한 모든 순열을 만드는 문제입니다. 2. 고난과 역경 완전탐색이 그렇게 어려운 문제는 아니라고 하는데 저한테는 왜 이렇게 골치가 아팠는지 모르겠습니다. 1) 잦은 실수 소수를 찾기 위해 n 보다 작은 수 (i < n) 로 모조리 나눠보던 기존의 코드에서, 효율성을 높여보겠다고 n의 제곱근* 까지 (i < Math.sqrt((double)n) 로 범위를 좁힌 게 화근이었습니다. 간단하게 더하기 1을 해주니 i < Math.sqrt((double)n) + 1 제곱근 값이 포함되면서 해결되었습니다. 이외에도 순열이 0으로 시작하는 경우의 문제라든지 문자열을 붙이는 순서 같은 것들이 여러 번 발목을 잡는 통에 시간을 지체하게 되었습니다. 완전탐색의 경우 적당히 어림잡아서 때려맞히는 .. 2021. 11. 3. 피보나치 함수 카운팅 문제 : https://www.acmicpc.net/problem/1003 1. 개요 재귀함수의 대명사 피보나치 함수가 구현은 쉽지만 얼마나 성능이 구린지 확인해보는 문제입니다. 2. 고난과 역경 ver 1. fibo함수에 count만 추가하면 기능 자체는 쉽게 구현할 수 있지만 당연하게도 시간초과로 실패하고 말았습니다. ver 2. import java.util.*; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int[] count = new int[2]; while(T>0) { int n = sc.nextInt(); fiboCount(count,.. 2021. 11. 1. 그래프의 탐색, bfs 와 dfs 1. 개요 그래프의 모든 정점을 방문하기 위한 방법으로 깊이우선탐색(depth first search)과 너비우선탐색(breadth first search) 가 있습니다. 깊이우선탐색은 하나의 정점에서 인접한 다음 정점을 방문한 뒤, 다시 새로 방문한 정점과 인접한 정점을 방문하는 방식으로, 한 우물만 죽어라 파는 방법입니다. 반면 너비우선탐색은 시작정점과 인접한 정점 모두를 방문한 뒤, 방문한 정점들 중에서 한 놈을 골라 그와 관련된 정점들을 모두 터는 방식입니다. 마치 저 반역자의 삼족을 멸하라! 하는 것처럼.. 2. 알고리즘 (1) dfs a. 정점 하나를 방문합니다. b. 방문한 정점과 인접한 정점 중 방문하지 않은 정점 하나를 방문합니다. c. 해당 정점을 중심으로 다시 깊이 우선 탐색을 시작합.. 2021. 11. 1. 집합 - Set 구현하기 문제 : https://www.acmicpc.net/problem/11723 1. 개요 Set 라이브러리에 있는 삽입 삭제 등의 기능을 구현하는 문제입니다. 왠지 Set 를 사용하면 반칙인 것 같지만 굳이 다른 자료형을 이용하라고 낸 문제는 아닌 것 같아서 그냥 Set를 썼습니다. 2. 고난과 역경 구현 자체는 어렵지 않으나 관건은 시간 제한입니다. 보통 출력하면 생각나는 System.out.print 가 문제였습니다. 출력값을 어디에 저장해뒀다가 한꺼번에 출력을 할 필요가 있어 보였고 BufferedWriter로 바꿨더니 통과할 수 있었습니다. 3. 대안 문제상에서 입력 원소 값의 범위가 정해져 있기 때문에 2진수의 비트연산을 이용해서 조금 더 간단하게 해결할 수 있습니다. 10 9 8 7 6 5 4 .. 2021. 11. 1. 로봇 청소기 문제 : https://www.acmicpc.net/problem/14503 1. 개요 n x m 바닥에서 순회를 하는 문제입니다. 2. 고난과 역경 모든 문제 해결은 문제를 꼼꼼히 읽는 것에서 시작합니다. 문제를 잘못 이해한 죄로 한참을 헤맨 끝에 후진을 과소평가했다는 것을 깨닫게 되었습니다. 문제의 조건에 따르면 이 청소기는 '청소를 한 곳' 과 '벽' 을 구분할 수 있고, 사방에 청소할 곳이 없더라도 뒤가 벽으로 막힌 것이 아니라면 계속 후진하여 탈출이 가능합니다. 3. 코드 import java.util.*; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.next.. 2021. 10. 31. 이전 1 2 3 4 5 다음 반응형
