본문 바로가기
반응형

전체 글

 (168)
[백준] 16637번 괄호 추가하기 16637번 괄호 추가하기 1. 이해하기 왼쪽부터 차례대로 계산한다. 연산자의 우선순위는 괄호만 신경쓴다. 괄호를 추가해도 되고 안해도 된다. 완전 탐색의 문제이다. 2. 구현하기 solve(index) index를 이용하여 현재 위치에 괄호를 추가하는 방법과 추가하지 않고 넘어가는 방법으로 모든 방법을 살펴보고 그에 따른 값을 계산하였다. static int solve(int index) { if(index == str.size()) { int sum = 0; int idx = 0; while(idx < str.size()) { if(str.get(idx) == '(') { int cur = 0; int a = str.get(idx+1)-'0'; char op = str.get(idx+2); int b..
[백준] 9935번 문자열 폭발 9953번 문자열 폭발 1. 이해하기 폭발 문자열이 발견되면 그 문자열을 없애버려야 한다. 스택의 개념을 쓰는 문제이다. 가장 중요한 String +연산은 시간과 메모리가 많이 쓰인다는 것을 알아야 한다. 2. 전체 코드 주석의 코드를 실행하면 시간이 오래 걸린다. 그 이유가 모든 문자에 대해서 print를 하는데 시간이 걸리기 때문이다.(추측) 이를 줄이기 위해서는 StringBuilder를 사용하면 된다. package algo; // //import java.io.BufferedReader; //import java.io.IOException; //import java.io.InputStreamReader; // //public class Acm9935 { // static char[] cStk =..
[백준] 9466번 텀프로젝트 9466번 텀프로젝트 1. 이해하기 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 문제이다. DFS를 이용해서 구한다. 2. 구현하기 dfs(here,arr,visited,done) 현재 학생을 가리키는 here 와 이미 체크한 학생인지를 나타내는 visited 프로젝트 팀원에 속하는지 여부까지 확인하는 done을 가진다. 다음번 학생을 비교하는데 체크하지 않았으면 dfs를 다시 하고, 체크를 한 상태에서 아직 프로젝트 팀원 여부를 확인하지 않았다면 이에 해당하는 학생수를 세준다. 이 때 하는 작업이 순환이 생기는 곳을 찾아서 그 때의 원소 수를 세주는 것이다. static void dfs(int here, int[] arr, boolean[] visited, boolean[] done) { ..
자바 modifier와 생성자 클래스 변수 Static 예약어 멤버 변수와 메서드 앞에 붙일 수 있는 modifier로서, 활용 방법을 제어함 Static예약어가 붙지 않는 인스턴스 변수 생성된 인스턴스마다 그 안에 클래스의 인스턴스 변수들이 포함됨 일반적인 멤버 변수를 인스턴스 변수라고 부름 Static 예약어가 붙는 클래스 변수 클래스로부터 생성된 인스턴스에 포함되지 않는 변수 많은 인스턴스를 생성하더라도 메모리에 하나의 변수만 존재함 객체를 생성하지 않고도 접근할 수 있는 변수 클래스 변수가 필요한 이유 동일한 값을 가지고 있는 변수를 클래스 변수로 선언하면 메모리 관리에 좋다 인스턴스 변수 클래스로부터 객체가 생성될 때마다 각 객체의 변수들이 생성됨 한 객체의 값이 변경되어도, 다른 객체의 값에 영향을 주지 않음 클래스 변수 ..
[백준] 1074번 Z Z(https://www.acmicpc.net/problem/1074) 1. 이해하기 Z모양으로 배열을 탐색한다. 배열을 만들기에는 메모리 공간이 충분하지 않다. 재귀적으로 4등분한 후 Z모양에 따라 순서대로 맞는지 찾아본다. 2. 구현하기 solve(x,y,n): 현재위치 (x,y), 현재 배열의 크기가 2의 n승. 만약 n의 크기가 1이라면 Z모양으로 탐색하면서 알고자 하는 위치인지 알아본다. 배열을 4등분한 후 다시 탐색한다. void solve(int x, int y, int n) { if(ans != -1) return; if(n == 1) { if(x == r and y == c) ans = cnt; cnt++; if(x == r and y+1 == c) ans = cnt; cnt++; if(..
[백준] 2263번 트리의 순회 트리의 순회(https://www.acmicpc.net/problem/2263) 1. 이해하기 인오더와 포스트오더로 나타내어진 트리를 프리오더로 나타내는 것이다. 인오더는 left root right, 포스트오더는 left right root 형태로 나타내어진다. 포스트오더에서 가장 오른쪽이 root이므로 이것을 이용해 인오더에서 left의 길이를 구한다. 구한 길이를 바탕으로 왼쪽과 오른쪽을 분할하여 다시 구한다. 2. 구현하기 solve(is,ie,ps,pe): 인오더의 시작,끝점과 포스트오더의 시작,끝점을 받는다. 포스트오더에서 구한 root를 가지고 인오더에서 root의 위치(ir)를 찾는다. 그 이후에 루트의 왼쪽에 해당하는 길이(l)를 구하고 그 길이를 바탕으로 트리의 왼쪽과 오른쪽을 분할한다..
[백준] 10815번 숫자 카드 숫자 카드(https://www.acmicpc.net/problem/10815) 1. 이해하기 상근이가 가지고 있는 카드 중 특정 카드를 가지고 있는지 찾는 문제이다. 이분 탐색문제이다. 2. 구현하기 단순히 이분탐색을 구현하면 된다. binarySearch(key): 중간값이 key에 해당하는지 보면서 검색해나간다. bool binarySearch(int n) { long long left = 0, right = N-1; while(left = en) return; findMid(st,en); int pivot = sang[st]; int l = st, r = en; while(1) { while(l = sang[l]) l++; while(l = en) return; int mid = (st+en)/2..
[백준] 2873번 롤러코스터 롤러코스터(https://www.acmicpc.net/problem/2873) 1. 이해하기 가장 큰 기쁨을 주는 롤러코스터의 움직임을 출력하는 문제. 행 혹은 열이 홀수인 경우, 모든 지역 탐색이 가능하다. 행, 열이 모두 짝수인 경우에는 어느 한 지역을 가지 않아야 한다. 가지 않는 한 지역을 구하는 기준은 다음과 같다. (행+열)이 홀수인 지역 중 가장 행복 지수가 낮은 지역을 구한다. 이유는 (행+열)이 짝수인 지역을 가지 않을 경우 한 곳은 두번 이상을 거쳐야 가장 오른쪽 아래 칸에 도착을 할 수 있기 때문이다. 가지 않는 지역을 결정했으면 그 지역을 기준으로 출발지역과 끝지역에서 서로 만나는 코스를 만든다고 생각한다. 가지 않는 지역을 기준으로 출발지역에서는 아래로 2칸, 끝지역에서는 위로 2..

티스토리툴바