반응형 Computer Science26 스택과 괄호의 값 문제 : https://www.acmicpc.net/problem/2504 1. 개요 주어진 괄호들이 규칙에 맞는지 확인, 계산하는 문제입니다. 2. 고난과 역경 1) check () 우선 괄호의 짝이 맞는지 확인하기 위해 왼쪽 괄호를 하나씩 읽어와 스택에 추가합니다. 오른쪽 괄호를 만났을 때 스택이 비어있거나, 꺼내온 값이 왼쪽 괄호가 아니라면 규칙에 어긋나므로 0을 리턴합니다. 처음 완성한 check() 에는 " ( ( [ " 와 같이 왼쪽 괄호만이 들어왔을 때 그냥 통과시켜버리는 문제가 있었습니다. check가 규칙에 맞지 않는 녀석들을 통과시켜버리는 바람에 EmptyStackException 이 발생했습니다. for 문이 종료되었을 때, 스택에 값이 남아있다면 0을 리턴하는 문장을 추가하여 문제를.. 2021. 11. 4. 그리디 알고리즘? 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. 이전 1 2 3 4 5 다음 반응형
