phanre의 tistory

https://www.acmicpc.net/problem/25047 25047번: 사각형 게임 (Large) 이 문제는 Python3를 이용하여 풀 수 있음이 보장되지 않습니다. Python3를 이용하는 분들은 Python3과 같은 문법을 가지면서 일반적으로 더 빠르게 동작하는 PyPy3를 이용해 제출하는 것을 권장드립니 www.acmicpc.net 파이썬으론 아마 풀지 못하는 것 같다. 브루트포스 방식으로 민우가 고를 수 있는 경우의 수를 모두 실행한다 n이 5일때는 아무것도 고르지 않는 것부터 0,1,2,3,4 모두 고르는 것 까지 모두 탐색한다 이후 종진이는 자신이 가장 이득을 볼 수 있는 경우를 고르기 때문에 col 배열을 만들어 이미 민우가 골랐다면 +, 고르지 않았다면 -를 하여 더해준다 반복..

https://www.acmicpc.net/problem/17265 17265번: 나의 인생에는 수학과 함께 세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 www.acmicpc.net DFS 탐색을 이용해 간단히 해결 import sys ap = -sys.maxsize an = sys.maxsize def DFS(y,x,p): global ap, an if y == n-1 and x == n-1: ap = max(ap,p) an = min(an,p) return for i in range(2): yy, xx = y + dy[i], x + dx[i] if yy ==..

https://www.acmicpc.net/problem/17292 17292번: 바둑이 포커 첫째 줄에 임의의 카드 6장이 주어진다. 카드는 ','로 구분되어 있고, 같은 카드가 여러 번 주어지는 경우는 없다. www.acmicpc.net 주어진 규칙에 따라 소트하는 문제이다. seq, same, other 배열을 각각 생성하여 연속된 수 / 같은 수 / 그 외 배열을 분리한다. 이후 각각 배열 마다 1. 색이 같은 쌍 / 2. 큰 수가 큰 쪽 / 3. 작은 수가 큰 쪽 / 4. 큰 수가 검은색 조건에 맞게 lambda를 이용해 소트하였다. 1. 색이 같은 쌍 key=lambda x:x[1] == x[3],reverse=True 2. 큰 수가 큰 쪽 key=lambda x:max(int(x[0],16)..

https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 모든 경우의 수를 탐색하면서 최대 점수를 넘길 경우 프루닝 해주는 브루트포스(BrueteForce) + 백트래킹(BackTracking) 문제 n, l, r, x는 재귀함수를 이용하면서 자주 쓰이므로 전역변수로 초기화 하였다. for문을 이용해 첫번째 인자를 골라서 넣고, 그 이후 첫번째 인자의 다음 인덱스부터 for문을 돌린다 이 때 sum을 체크해 r을 넘어가면 재귀함수를 실행하지 않는다. 매번 재귀할 때 마다 max, min을 조정하며 sum이 l 이상이고 max-min이 x 이상이면 ret을 증가시켜 ..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 맥스 힙을 이용한 그리디 문제이다. arr 배열을 1001개 만들어서 arr[마감기한].append(점수)를 해준다 이후 가장 긴 마감기한부터 짧은 마감기한까지 역순으로 for문을 돌려서 점수를 맥스 힙에 추가시켜준다 역순으로 돌리는 이유는 마감기한이 길면 마감기한이 짧은 것 처리 후에 해도 되기 때문이다. 이후 마감기한을 1씩 감소될때마다 heappop을 해서 answer를 증가시킨다. import sys from heapq import ..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 브루트포스를 이용한 문제. 1번 - 상하좌우 2번 - 상하 3번 - 상하좌우 4번 - 상하좌우 5번 - 한가지 경우 이렇게 번호별로 경우의 수를 나눠 그대로 짜면 된다. 기능구현을 마쳤으면 모든 경우의수를 테스트 해보면 된다. 파이썬에서 재귀함수를 사용할 때 리스트를 인자로 넘겨주고 그 리스트에 변화가 없게 하려면 from copy import deepcopy를 해주어 deepcopy를..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net BFS를 이용해 관계를 탐색하는 문제 부모 - 자식 관계를 arr에 양방향으로 저장한 후 시작 - 끝 관계를 BFS 탐색하며 visit을 1씩 증가시켜준다 루프가 끝났을 때 visit[end]가 0인 경우 알 수 없어 -1을 출력하고, 0이 아닌 경우 시작할 때 본인에 1을 더했으니 visit[end]에 1을 빼서 출력한다 import sys from collections im..

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net BFS를 이용해 가장자리 치즈를 줄여나가는 문제. 자바와 익숙해지기 위해 자바로 풀었다. N * M 의 배열을 받아서 arr에 저장한다. 배열의 가장자리는 항상 치즈가 있지않으니 0,0을 Queue에 저장한다(LinkedList 이용) 이후 BFS를 돌려 0일 경우(치즈가 아님) Queue에 add해주고 visit을 1로 만들고 1일 경우(치즈임) visit을 1로 만들고 arr 값을 0으로 변경시킨다. ..

https://www.acmicpc.net/problem/21735 21735번: 눈덩이 굴리기 눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은 www.acmicpc.net 간단한 브루트 포스 문제. 시작점은 0이므로 다음 눈덩이의 위치는 1, 2 두가지가 가능하다. 만약 앞마당의 길이가 2가 되지 않는다면 2는 생략한다. 0에서 1로 가게되면 그대로 눈덩이의 크기를 전달하고 0에서 2로 가게되면 눈덩이의 크기를 절반을 만들어서 함수에 넣는다. 이후 1에서는 2, 3 / 2에서는 3, 4 / ... / n-1, n 까지 도달하도록 재귀함수를 작성한..

https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 각 노드에서 다른 노드까지의 거리를 플로이드 와샬(Floyd-Warshall)을 이용하여 구하고 노드를 두가지 고르는 경우의수를 모두 탐색하여 최소값을 구하는 문제이다. 노드와 노드가 연결되어있다면 edge 배열에 양방향으로 거리를 1로 초기화 해주고 플로이드 와샬 알고리즘으로 노드까지의 거리를 전부 구한다. 그리고 두 노드를 고른 뒤 두 노드 제외한 노드와의 거리의..