개발일지

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 이문제는 이전에 모든 도형을 정의해놓고 테트리스를 만들어본 경험이 있어 그렇게 풀까 했는데 DFS를 공부한 사람의 입장으로서 문제를 보니 백트래킹으로 간단히 해결이 될듯한 문제였다. 조금 신경써 주어야할 부분이 있다면 https://ko.wikipedia.org/wiki/%ED%85%8C%ED%8A%B8%EB%A1%9C%EB%AF%B8%EB%85%B8 테트로미노 - 위키백과, 우리 모두의 백과사전..

프로그램에서 데이터를 처리해서 결과 만들어 내는 것을 연산이라 하는데, 이런 연산을 하기위해 사용되는 기호나 표기방법을 연산자라고 한다. 이런 연산자들끼리는 우선순위가 정해져 있으며 또 그 처리방식에 따라 같은 결과를 낼지라도 성능적으로 더 우수한 연산자가 있다. 먼저 연산자의 종류를 표로 한번 보겠다. 종류 연산 방향 연산자 우선 순위 단항 연산자 ++ -- ~ ! (type) 높음 낮음 산술 연산자 → * / % + - >>> 비교 연산자 = instanceof == != 논리 연산자 & ^ | && || 삼항 연산자 ? : 대입 연산자 ← = *= /= %= += -= = >>>= &= ^= |= 이제 각각의 연산자에 대해 정리해보겠다. 1. 증감연산자 ++ , -- 와 같이 생긴 이 연산자는 증감..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 비슷한 문제를 조금 풀어봤다면 간단히 해결가능한 탐색문제이다. DSLR 각 명령어에 해당하는 좌표로 이동할때 D,S 명령어에 해당하는것은 누구나 쉽게 작성가능하지만, L,R에 해당하는 명령어를 문자열 변환을 사용해 이리저리 비틀어 풀려 하면 꼬이게 되는 문제이다. 이때 사용가능한 아이디어는 수식을 사용해 한칸씩 미루거나 땡겨오는 방법을 사용하는것으로, https://0bliviat3...

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 이 문제는 일단적으로 많이 알려진 풀이인 TreeMap을 사용하면 진짜 간단히 풀 수 있는 문제이지만, 필자의 성향상 구현 문제을 비열하게 컬렉션 프레임 워크를 사용해 풀고 싶진않았다. 그래서 조금 어려운 풀이로 가보려 한다. 이 문제를 푸는 아이디어는 최대 힙 하나, 최소 힙 하나, 그리고 방문배열 하나로 푸는것이다. 문제 제목이 이중 우선순위 큐이니 최대힙,최소힙 두개의 힙을 사용한다는건 ..

이번 포스팅에서는 조금 어렵지만 이해하고 사용한다면 정말 강력한 무기가 될 수 있는 힙에 대해 다뤄보도록 하겠다. 먼저 위키백과를 통한 정의를 살펴보고 오겠다. https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 힙 (자료 구조) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값을 가진다. 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 ko.wikipedia.org 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree..