For Programmer

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 간단히 0의 위치를 저장후 3개를 뽑는다 그 3개를 1로 바꾸고 바꾼상태에서 bfs를돌려 바이러스를 잠식하게 한다. 그 후 0의 개수를 세어 가장큰값을 찾으면 된다. from collections import deque N, M = map(int, input().split()) map_ = [list(map(int, input().split())) for _ in range(N)] brr = [] zero =..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net N = int(input()) arr = list(map(int, input().split())) ans = [-1] * N # 초기 정답을 -1로 설정 stack = [0] # 첫 인덱스 0을 넣어준다. for i in range(1, N): # 만약 스택의 마지막 인덱스의 arr값이 해당 비교하고자 하는 값보다 작다면 # 그 값보다 클때까지 해당 값을 오른쪽의 큰 수로 설정해준다. while stack ..

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 상당히 어려운 문제이다.. 아무리 풀어도 시간초과가 나길래 풀이힌트를 보았다. 해결방법은 다음과 같다. 어차피 대각선끼리만 영향을 주니 dfs를 돌 때 반씩 나눠서 돌자는 것이다. 즉, 최대 O(2^100) 인 시간복잡도를 O(2^25) * 2 로 줄일 수 있다는 것이다.(6700만 정도) 단, 한부분만 신경을 잘써야하는데 바로 N이 짝수일때와 홀수일때 열과 행의 계산이 달라진다는 점이다. 자세한 코드는 ..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 해당 문제 처음에 연결요소 개수 찾는 문제인지 알고 풀었으나 당연히 아니였다... 그래서 생각을 조금 더 해보니 다음과 같은 구조를 발견할 수 있었다. 1. 이미 방문처리된 그룹과 연결된다면(이미 설치했으므로) 굳이 safe-zone을 설치할 필요가 없다. 2. 아직 방문처리 되지않은 그룹과 연결되었는데 더이상 갈곳이 없다면 그때 개수를 1개 증가시켜준다. 3...

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 해당 문제 굉장히 어려웠다... (알고나면 쉬운데 모르면 어려운 문제) 문제 해결은 단순하다. 1. 붙어 있는 0끼리 딕셔너리로 그룹을 매긴다. 그리고 각 그룹마다 0의 개수를 저장해놓는다. 2. 그 후 1의 위치만 찾아서 위 아래 좌 우 4방향으로 한번만 이동하면서 각각의 그룹에 저장되어있는 0의 개수만 더해주면 된다. from collections import deque ..

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net O(n^2) 에 해결할 수 있기 때문에 잘생각해보면 리스트 전체의 각 지점을 반복문을 돌면서 한점을 기준으로 잡고 바로 오른쪽을 시작점 마지막 인덱스를 끝지점으로 투포인터를 돌리면 되는 간단한 문제이다. 세개의 점을 찾아야하기 때문에 투포인터의 응용버전이라 조금 생소할 수도 있지만 이기회에 잘 익히자. (참고로 N^2 임에도 불구하고 아주큰수의 + 연산때문에 파이썬3에서는 시..

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 아무리 구글링을 해도 바텀업으로만 풀었지 탑다운으로 푼 글이 없어서 탑다운으로 한번 풀어보았다. 3차원 메모제이션을 활용해서 풀었으며 마지막전에서 시작 번호와 같은지만 잘 비교해서 같다면 continue해버리는 느낌으로만 하면 쉽게 해결할 수 있다. import sys sys.setrecursionlimit(5000) N = int(input()) house = [li..

https://www.acmicpc.net/problem/1090 1090번: 체커 N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 www.acmicpc.net 백준 14400번 파이썬 (편의점 2) 과 비슷한 문제이나 난이도가 꽤있는 문제이다. 결국 문제에서 요하는 것은 완전탐색이다. N이 50이라 O(N^4)까지 돌 수 있어서 완전탐색으로 접근하면 생각보다 쉽게 해결할 수 있다. 문제해결방식은 다음과같다. 1. 우선 모든 좌표의 조합을 돈다. (O(n^2)) 2. 각각의 좌표마다 모든 좌표와의 거리를 구한다. 3. 오름차순 정렬 후 1개부터..