전체 글
-
[BOJ - 14500] 테트로미노백준알고리즘 2020. 2. 24. 02:40
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 작년에 진짜 자바에서 빡구현으로 풀었던 문제다. 빡구현을 통해 속도를 챙길수 있지만, 코드작성 시간효율 측면에서 굉장히 비효율적이라..
-
트리 순회(전위, 후위, 중위)개인공부 2020. 2. 17. 18:54
트리의 순회를 공부하기 전에 앞서, 트리의 순회는 이진트리에서의 순회를 말한다. 부모 노드 한개와, 자식노드 2개 , 또는 부모노드 한개 , 자식노드 한개, 그리고 부모노드만 있는경우가있다. 순회라는 관점에서 볼때는 굉장히 어려운 느낌이나, 간단히 생각해보면 -> 노드를 어떻게 순회할것인지? 를 재귀를 선행 중행, 후행으로 할것인지에 대한 선택의 문제다. 타고 들어가서 탐색하고자 하는 순서에 대한 알고리즘 작성자의 선택에 따라 바뀌는것으로, 트리 뿐만 아니라 재귀함수 자체에 대한 이해도를 조금더 높여줄수있는 학습이였던것 같다.
-
[BOJ - 18427] 함께 블록 쌓기카테고리 없음 2020. 2. 14. 17:12
https://www.acmicpc.net/problem/18427 18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구분되어 주어진다. 단, 모든 블록의 높이는 1,000 이하의 자연수이며 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르게 주어진다. www.acmicpc.net 재귀로 여러번했다가 실패했는데, 아마.. 시간 복잡도가 대략 10의 50승이 나오기 때문일것이다. 제일좋은 방법은 Dynamic Programming에서 할수있는 배낭알고리즘을 통해 풀수있다. 높이에 따른 DP를 통해..
-
[BOJ - 18429] 근손실백준알고리즘 2020. 2. 14. 17:10
https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 감소하게 된다. 따라서 운동을 하지 않고, 가만히 있다면 매일매일 중량이 감소할 뿐이다. 다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할 지는 마음대로 결정할 www.acmicpc.net 배열크기가 극도로 작아서, 재귀로 풀수있는 쉬운문제다.
-
[BOJ - 4217] 신성 문자백준알고리즘 2020. 2. 14. 17:08
https://www.acmicpc.net/problem/4217 4217번: 신성 문자 문제 고고학자는 초기 문명을 이해하기 위해서 고대 언어로 된 글을 공부하기도 한다. 이집트는 3000년전에 각종 동물이나 사물, 신체의 모습을 본딴 고대 언어 "신성 문자"를 만들었다. 이 문제에서, 아래와 같은 글자 여섯개를 인식하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 하나 또는 그 이상의 신성 문자를 포함하는 그림으로 이루어져 있다. 그림은 1 또는 0으로 이루어져 있고, 1은 검정 픽셀, www.acmicpc.net 디코딩 -> BFS를 통한 Flood Fill -> 안에있는 구멍 개수에 확인 이후, 그에 따른 문자열 담기-> 출력
-
[BOJ - 14632] 고급 작품백준알고리즘 2020. 2. 14. 17:06
https://www.acmicpc.net/problem/14632 14632번: 고급 작품 첫째 줄에 도화지의 세로 크기 N과 가로 크기 M이 주어진다. (1≤N,M≤1,000) 둘째 줄에 도장의 수 K가 주어진다. (1≤K≤500) 그다음 줄부터 도장의 크기와 모양이 K개 주어진다. 한 도장마다 도장의 크기 H, W가 주어지고, 다음 줄부터 H 줄에 걸쳐 도장의 모양이 주어진다. (1≤H,W≤500) 도장은 1번부터 K 번까지 번호가 매겨져 있다. 그 다음 도장을 찍는 좌표의 개수 Q 가 주어진다. (1≤Q≤10,000) 그 다음 줄 부터 Q www.acmicpc.net 단계별로 전부다 칠해서 해결했다. 그런데, 자료형을 쓰는것에 따라 많은시간 차이가나는데, 벡터에 저장한 이후 프로그램을 진행하는것보..
-
[BOJ - 17396] 백도어카테고리 없음 2020. 2. 12. 19:43
https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는지를 의미하는 N개의 정수 a0, a1, ..., aN-1가 공백으로 구분되어 주어진다. ai가 0이면 i 번째 분기점이 상대의 시야에 보이지 않는다는 뜻이며, 1이면 보인다는 뜻이다. 추가적으로 a0 = 0, aN-1 = 1이다., N- www.acmicpc.net 굉-장히 단순한 다익스트라 문제다. 하지만 여러번틀렸는데.. 시간초과야 내가 잘못짜서 그렇다치지만.. 자료형 실수는 치명적인것 같다. ..
-
[BOJ - 17394] 핑거스냅카테고리 없음 2020. 2. 12. 19:41
https://www.acmicpc.net/problem/17394 17394번: 핑거 스냅 [어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼고 손가락을 튕기면, 사용자가 원하는 것을 할 수 있다. 그러나 반동이 매우 심하기 때문에 그리 많이는 사용할 수 없다. 정신 나간 수학자 Sonaht는 우연히 이 인피니티 건틀렛을 손에 넣게 된다. 그러나 이 인피니티 건틀렛에는 약간의 하자가 있어서, 핑거 스냅으로 할 수 www.acmicpc.net 약간.. BFS같지않은 BFS로 문제를 풀었다. 다익스트라로 해도괜찮을법하긴 하지만, 크기가 크지않아서 그냥 BFS로진행했고, 문제..