늦깎이 IT

[백준 2504번] 괄호의 값 URL 1. 입력으로 주어지는 문자열의 길이가 홀수라면 0을 리턴한다. 2. 여는 괄호는 스택에 넣는다. 3. 닫는 괄호가 나오면 다음을 수행한다. (설명은 [, ] 괄호에 대해서만 한다.)스택에서 pop 한 값이 닫는 괄호( ] )와 쌍인 여는 괄호라면( [ ) 3을 스택에 넣는다.스택에서 pop 한 값이 닫는 괄호( ] )와 쌍이 아닌 여는 괄호라면 ( ( ) 0을 리턴한다.스택에서 pop 한 값이 숫자라면, 닫는 괄호( ] )와 쌍인 여는 괄호( [ )가 나올때 까지 pop한다. 이 과정에서 pop하는 숫자들은 모두 더해줘야만 한다. 예) [ 2 2 2 ] = (2 + 2 + 2) * 3 = 18 임을 인지한다.스택을 모두 비울때 까지 여는 괄호를 못찾았다면 0을 리턴..

[백준 1992번] 쿼드트리 URL 분할정복의 정석(?)같은 느낌의 문제입니다. 비슷하지만 꼭 비슷하지않은 문제도 참고해보시기 바랍니다.2019/03/21 - [알고리즘 문제/알고스팟] - [알고스팟] 쿼드 트리 뒤집기 :: 늦깎이 IT [풀이 방법] 1. 현재 맵이 한 가지색으로 칠해져 있는지 확인한다. - 한 가지색으로 칠해져 있다면 답을 출력한다. 2. 한 가지색으로 칠해져 있지 않다면, 현재 맵을 가로 2등분, 세로 2등분으로 총 4조각으로 나눈다. 3. 각각의 조각 (왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래)에 대해 다시 DFS 탐색을 시작한다. - 결국 1 X 1 칸은 한 가지색으로 칠해져 있을 수 밖에 없으므로 이를 기저조건으로 삼는다. [소스 코드] 1234567891011121314151..

[백준 1935번] 후위표기식2 URL 문제풀이는 후위표기식과 후위표기식 계산에 대한 아래의 포스팅을 참고하시기 바랍니다. 2019/03/21 - [알고리즘 이론] - [자료구조] 스택으로 후위표기식으로 변환하기 :: 늦깎이 IT2019/03/21 - [알고리즘 이론] - [자료구조] 스택으로 후위표기식 계산하기 :: 늦깎이 IT [소스 코드] 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReade..

이전 포스팅에서는 스택을 활용해서 중위 표기법을 후위 표기법으로 변환했다.이 포스팅을 읽기 전에 이전 포스팅일 먼저 읽어보기 바란다. 2019/03/21 - [알고리즘 이론] - [자료구조] 스택으로 후위표기식 구현하기 :: 늦깎이 IT [후위 표기식 계산하기] 1. 피연산자는 무조건 스택에 저장한다. 2. 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내서 계산을 한다. 단, 여기서 주의할 점은 스택에서 먼저 꺼낸 피연산자가 연산자의 뒤에 위치해야한다. 3. 계산 결과는 다시 스택에 넣는다. 후위표기식을 만들었으면, 계산하는 것은 어렵지 않다.우선, "3 2 4 x +" 와 같은 후위 표기법이 있다고 가정해보자. 후위 표기식에서는 연산자를 만나면 그 연산자와앞의 두 개의 피연산자를 계산하는 방식이다. ..

[백준 1918번] 후위표기식 URL 중위 표기법을 후위 표기법으로 바꾸는 이론에 대해서는 아래 포스팅을 참고하시기 바랍니다. 2019/03/21 - [알고리즘 이론] - [자료구조] 스택으로 후위표기식 구현하기 :: 늦깎이 IT [소스 코드] 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293import java.util.Scanner;import java.util.Stack; public class Main { public static v..

후위표기법을 계산하는 방법은 아래 포스팅을 확인하기 바랍니다. 2019/03/21 - [알고리즘 이론] - [자료구조] 스택으로 후위표기식 계산하기 :: 늦깎이 IT [전체 구현 소스 코드 확인하기] 이번 포스팅은 스택 자료구조를 활용해서 중위 표기법을 후위 표기법으로 바꾸는 방법을 알아본다. 중위 표기법을 후위 표기법으로 바꾸는 데에는 아래와 같은 규칙이 있다. [소괄호가 없는 중위표기법] 1. 중위 표기법을 저장하는 배열 A와 후위 표기법을 저장하는 배열 B가 있다. 2. 아래 규칙에 따라, 피연산자와 연산자를 배열 A에서 배열 B로 이동시킨다. 1) 피연산자는 무조건 B 배열로 이동시킨다. 2) 연산자는 스택에 저장한다. 스택이 비어있다면, 연산자를 저장한다. 스택이 비어있지 않다면, 이미 저장된 ..

[알고스팟] 울타리 잘라내기 URL 1. 울타리의 최대 넓이를 찾는 방법은 아래와 같다. 1) 울타리를 N/2등분 하여, 왼쪽 울타리에서 최대 넓이를 찾는다.2) 울타리를 N/2등분 하여, 오른쪽 울타리에서 최대 넓이를 찾는다.3) 울타리의 N/2등분한 위치를 기점으로 왼쪽과 오른쪽을 탐색하며 최대 넓이를 찾는다. 반드시 N/2 위치가 포함되어야 한다. [소스 코드] 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960import java.io.BufferedReader;import java.io.IOException;import java.io.InputStr..

[알고스팟] 쿼드 트리 뒤집기 URL 1. 분할정복을 사용한다. 2. 예를 들어, N x N칸이 모두 흰색 혹은 검은색으로 칠해져 있는 경우 뒤집어도 똑같은 색이다. 3. 이 아이디어에서부터 1x1 칸에는 한 가지 색만 칠해져 있으므로, 뒤집어도 똑같기 때문에 기저조건을1x1칸으로 정한다. 4. 입력으로부터 input 문자열을 받고, 이 문자열의 인덱스를 가리키는 pointer를 선언한다. 5. recursive() 메소드를 호출하면, input 문자열의 처음부터 확인한다. input 문자열의 첫글자가 w 혹은 b라면N x N칸 모두 하나의 색으로 칠해져있다는 뜻이므로, input 그대로 정답을 출력한다. 6. input 문자열의 첫 글자가 x라면 이것을 4등분으로 나누어야 한다. 4등분으로 나누는 기준..