본문 바로가기
728x90

알고리즘316

[python] 백준 14500 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 해결 사실 너무 어려웠다. 한 점을 잡고 이동을 해야할 것 같은데 어떻게 해야할 지 몰랐다. 이 모양을 제외 하면 모두 한 붓 그리기, 즉 다시 되돌아가지 않고 이동하면서 그릴 수 있다는 특징이 있다. 이 모형도 가운데를 중심으로 동,서,남,북 으로 이동 후 하나를 자른다는 생각을 할 수 있다. 자르는 것은 최소의 값을 가진 지역이라 할 수 있다. 이동하는 방법을 move = [ (1,0),.. 2023. 1. 2.
[python] 백준 1476 날짜계산 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 문제 해결 - E의 값은 연도%15 (단 나머지 0은 15), S의 값은 %28 (단 나머지 0은 28), M의 값은 %19 (단 나머지 0은 19)한 값이다. - 따라서 E가 작으면 E+15 S가 작으면 S+28 M이 작으면 M+19를 반복적으로 하여 E=S=M이 되도록 한다. 그 때가 연도이다. CODE import sys input = sys.stdin.readline e, s, m = map(i.. 2022. 12. 31.
[Python] 백준 3085 사탕게임 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 문제 해결 $N \times N$ 행렬을 만들어야 한다. 행별로, 열별로 각각 옆에 있는 사탕의 색깔이 다르다는 조건하에 서로 바꾼다음 같은 색으로 이어진 가장 긴 행 또는 가장 긴 열을 찾는다. 찾은다음 다시 사탕의 위치를 원위치 시킨다. 위의 사고를 가지고 코드를 짜면 O($N^4$)가 나온다.... 그러나 N이 작다는 것때문에 큰 문제가 되지 않는다. brute force(부루트 포스)알고리즘으로 분리되어 있는 것 보면 가능하다는 뜻.. CODE import sys input = sys.stdin.readli.. 2022. 12. 31.
[Python] 백준 2309 일곱 난쟁이 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제 해결 리스트 안에 두 개의 원소를 빼는 방법을 선택 뺄 두 개원 원소 인덱스중 작은 인덱스를 start, 큰 인덱스를 end로 잡고 하려고 함. 알고 있는 지식이 전체 수의 합이므로 리스트를 sort 시킨 후 start, end 포인트 이동이 편할 것 같다. 시간 복잡도면에서 더 효율적인 것이 있을 것 같지가 않았다. (Brute force algorithm) CODE import sys input .. 2022. 12. 30.
728x90