늦깎이 IT

[알고스팟] 고대어사전 URL 1. 입력으로 주어지는 단어의 순서가 사전 순서로 배치되어 있다. 2. 각 단어들마다 비교를 통해 각 문자들간의 우선순위를 비교해주는 연산이 필요하다. 3. 예를 들어, acb와 abb가 입력되었을 경우 맨 앞자리 알파벳은 같으므로 패스하고 두 번째 자리인 c가 b보다우선한다는 것을 표시해야한다. 4. 각 단어들간의 우선순위는 26 X 26 인접행렬로 표현해도되고 연결리스트로 표현해도된다. 5. a~z 까지의 알파벳을 순차적으로 탐색하되 연결되어 있는 알파벳이 있다면 다시 그 알파벳부터 DFS탐색을시작한다. 6. 순서가 정해져있는 경우이므로, 위상정렬을 한다고 생각하면 된다. 1234567891011121314151617181920212223242526272829303132..

[백준 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..

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

[알고스팟] 울타리 잘라내기 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등분으로 나누는 기준..

[SWEA 5648번] 원자소멸 시뮬레이션 URL SWEA 모의역량 테스트 문제들 중에서 시뮬레이션 문제로는 끝판왕인 것 같다.입력으로 주어지는 원자들의 초기 입력 값들도 음수로 주어지고, 원자 충돌이 1초, 2초가 아닌 1.5초, 2.5초처럼소수점으로도 충돌한다. 이 입력 값을 연산이 편하게 바꿔주는 것이 중요하다. ※ 런타임에러가 계속 뜨길래, 도대체 왜그런가 했더니 visited 배열과 collapse 배열을 tCase마다 새롭게 초기화했더니 메모리가 부족해서 그랬다. [풀이 방법] 1. 입력으로 주어지는 원자의 좌표 값은 -1000 이상 1000이하이므로, 이를 양수 좌표로 바꿔줘야 한다.입력된 좌표 각각에 +1000을 해줌으로써 0이상 2000이하로 범위를 바꾼다. 2. 0.5초 단위로 원자들이..