알고리즘/백준 (70) 썸네일형 리스트형 [백준] 1248번 맞춰봐 1248번 맞춰봐 1. 이해하기 설명은 길게 되어 있지만 결국은 N개의 숫자를 선택하는 문제이다. 하지만 부호를 잘 맞춰야 하는 문제이다. 완전 탐색과 백트랙킹으로 풀 수 있다. 2. 구현하기 solve(index) index를 N까지 진행해보며 N에 도달했다면 true를 반환한다. 0 ~ 20 부터 반복하면서 result배열에 하나씩 넣어본다. 이때 -10을 하고 넣어줘서 -10 ~ 10의 구간을 만들어준다. 이때 가장 중요한 것은 추가를 했을 때, 바로 가능한 경우인지를 비교해줘서 체크를 해야 시간 초과 등의 문제를 피할 수 있다. static boolean solve(int index) { if(index == N) return true; for(int i = 0; i = 0; i--) { sum .. [백준] 1918번 후위표기식 1918번 후위표기식 1. 이해하기 중위 표기식을 후위 표기식으로 바꾸는 문제. 스택을 어떻게 사용하는지 알아야 하는 문제이다. 2. 구현하기 현재 값이 알파벳이라면 출력하는 배열에 넣어준다. 현재 값이 +,- 라면 ( 이외의 연산자는 모두 빼고 출력하는 배열에 넣어준다. 그 이후 스택의 가장 윗부분에 현재 값을 넣어준다. 현재 값이 *,/ 라면 +,-,( 이외의 연산자는 모두 빼어 출력하는 배열에 넣어준다. 이후, 스택의 가장 윗부분에 현재 값을 넣어준다. 현재 값이 ( 라면 스택의 가장 윗부분에 넣는다. 현재 값이 ) 라면 ( 이 나올 때까지 빼어 출력하는 배열에 넣어준 후, (를 빼버린다. package algo; import java.util.Scanner; public class Acm1918_.. [백준] 17070번 파이프 옮기기1 17070번 파이프 옮기기1 1. 이해하기 파이프를 N,N으로 옮기는 경우의 수를 구하는 문제이다. DFS를 이용하여 구할 수 있다. 참고로 DFS에 DP를 추가하여 구할 수도 있다. 시간을 단축시킬 수 있다. 2. 구현하기 dfs(x,y,prev) 현재 위치와 이 전에 어떤 방향으로 있었는지를 받는다. 이를 이용해서 파이프가 어떤 모양으로 이어질 수 있는 지를 구한다. static int dfs(int x, int y, int prev) { if(x == N-1 && y == N-1) return 1; int ret = 0; for(int i = 0; i < 3; i++) { if((prev == 0 && i == 2) || (prev == 2 && i == 0)) continue; int nx = x.. [백준] 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) { .. [백준] 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)를 구하고 그 길이를 바탕으로 트리의 왼쪽과 오른쪽을 분할한다.. 이전 1 2 3 4 5 ··· 9 다음 목록 더보기
