목록2018/01 (10)
Inor
- 문제 : https://www.acmicpc.net/problem/10798 가로로 쓰여진 단어를 세로로 변경하고 빈칸인 부분은 무시해서 이어 붙여주면 되는 문제 입니다. - 풀이 경사로 문제와 비슷하게 해결했습니다. for문에서 row와 col의 위치를 변경해주는 것이 아니라 애초에 위치가 변경된 배열을 선언하고 위치를 재배열 해줬습니다. 그 이후에는 비어있는 공간을 특정 문자로 채우고 특정 문자가 있을 경우에는 건너 뛰어서 계산하도록 했습니다. - 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Reading..
- 문제 : https://www.acmicpc.net/problem/12761 이동 가능한 방법이 총 8개 주어지고 방법에 맞게 동규를 이동 시키는 문제 입니다. 동규가 도착 지점까지 이동한 횟수의 최솟값을 출력하면 됩니다. - 풀이 처음에는 DP 방식으로 문제에 접근했습니다. 만약 앞으로만 이동할 수 있다면 DP를 이용해서 도착지점에서 가장 가까운 위치(도착지점 - 1)에서부터 값을 감소 시키며 시작지점에서 도착지점까지 이동한 횟수를 찾을 수 있다고 생각했습니다. 그러나 뒤로 이동하는 경우에 DP를 이용해서 문제 해결이 불가능했습니다. 예를 들어서 앞으로만 이동 가능하고 도착 지점이 20이고 현재 11번째에서 20까지 갈 수 있는 최단거리를 찾으려고 할때 11과 20 사이의 위치에서 최단으로 20까지..
- 문제 : https://www.acmicpc.net/problem/1992 쿼드트리를 이용해서 4등분된 영역을 압축하는 알고리즘 문제 입니다. - 풀이 처음에는 괄호와 0, 1 값들을 스택에 넣어두고 pop 하면서 압축을 검사하고 다시 스택에 넣는 방법으로 풀려고 했지만 실패했습니다. 애초에 조금 돌아가는 방법으로 판단했고 분할/정복 방식으로 재귀호출하여 문제를 해결했습니다. 이 문제를 풀기에 앞서서 분할 정복에대한 개념을 잡고자 Merge Sort를 공부 했습니다. 그리고 분할/정복 방식의 문제 풀이는 분할이 안될때까지 분할하고 정복(문제를 해결)하면서 문제를 풀어가는 방법과 분할 하기 전에 정복할 수 있는지 확인하고 다음 분할로 넘어가는 방식이 있는데 저는 분할을 하기 전에 정복할 수 있는지 확인..
- 설계 스택 두개를 이용하면 큐를 구현할 수 있습니다. 각각의 스택을 enQueue와 deQueue 연산에 맞게 구분해주면 간단하게 구현이 가능합니다. enQueue 연산이 필요하면 먼저 deQueue 스택에서 모든 자료를 enQueue 스택으로 옮기고 enQueue 스택에 데이터를 Push 해줍니다. deQueue 연산이 필요하면 enQueue 슽개에서 모든 자료를 deQueue 스택으로 옮기고 deQueue 스택에서 데이터를 Pop 해주면 두개의 스택으로 큐를 구현할 수 있습니다. 혹시 큐를 여러개 사용하면 스택 구현이 가능할까 생각을 해봤는데 큐는 넣는 순서대로 삭제 되기 때문에 맨 마지막에 있는 데이터를 꺼내는 것이 불가능하기 때문에 구현하지 못했습니다. 여기서 말하는 큐는 양방향큐가 아닌 일반..
최근들어 신문을 읽기 시작했는데 기술면을 보면 블록체인(가상화폐)과 CES 2018에서 어느 기업에서 새로운 기술을 선보였다는 얘기가 절반을 차지하고 있었습니다. 그래서 이 행사가 어떤 행사인지 찾아보니 매년 초에 '라스베가스'에서 열리는 소비자 가전 전시회라는 것을 알게됐습니다. 삼성, LG 등 가전제품으로 국내의 굵직한 대기업 뿐만 아니라 구글, 아마존, 포드, 벤츠 등 세계를 상대로 하는 기업들이 참가하는 매우 큰 전시회였습니다. 온오프믹스에서 세미나를 찾던 중에 CES 2018에 참가한 카이스트 교수님들과 성남시의원들이 함께 CES 2018을 리뷰하는 컨퍼런스를 열고 있다는 것을 확인했습니다. 기사로만 확인하던 내용을 전문가들의 시각에서 자세히 들을 수 있는 좋은 기회라고 생각하고 참가했습니다. ..
- 문제 : https://www.acmicpc.net/problem/2573 rowN x colN 크기의 행렬에 빙산과 바다가 표시됩니다. 빙산은 0 이상의 숫자로 바다는 0으로 표시됩니다. 빙산은 바다와 맞닿아 있는 수 많큼 빠르게 줄어들고 빙하가 두조각 이상으로 나뉠때까지 빙하를 녹이는 문제입니다. 문제가 지난번에 풀었던 안전영역과 비슷합니다. 안전영역 문제 및 풀이 : http://inor.tistory.com/26?category=723636 - 풀이 먼저 빙하를 방문했습니다. 방문을 위해 DFS를 이용했고 DFS를 이용한 이유는 빙산이 몇조각으로 나뉘어져 있는지 확인하기 위해서였습니다. 방문 함수를 2번 이상 호출하면 빙하가 2조각 이상이라는 말이고 2번 이상 호출 됐을 경우에 탐색을 종료했습..