Problem Solving/BOJ-Gold (6) 썸네일형 리스트형 (Python) 백준 5430 - AC https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 아이디어 배열이 리스트로 주어지는게 아니라 문자열로 주어지는데, eval을 사용하면 별도의 처리가 필요하지 않다. 배열의 크기가 크기 때문에 배열의 반전을 자주 시행한다면 시간초과가 나므로, 배열을 직접 뒤집는 것이 아니라 배열이 뒤집힌 상태에서는 배열의 앞이 아닌 뒤에서 원소를 제거해준다. 배열의 앞에서도 원소를 제거해야 하기 때문에 deque를 사용한다. 코드 from collections import deque import sys input=sys.. (Python) 백준 11758 - CCW 아이디어 CCW 알고리즘에 대한 설명: https://monogatary.tistory.com/55 두 벡터의 외적을 구한 다음, 음수일 시 -1, 양수일 시 1, 0 일시 0을 반환 코드 a,b,c=[[*map(int,input().split())] for _ in range(3)] d=(b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0]) print((d>0)-(d (Python) 백준 2206 - 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 아이디어 가중치가 없는 그래프의 최단경로 찾기 문제이므로 BFS를 사용한다. 방문여부를 체크할 때, 벽을 부순 이후랑 이전을 구분해서 체크해준다. 코드 from collections import deque import sys input=sys.stdin.readline n,m=map(int,input().split()) a=[input().strip() for _ in r.. (Python) 백준 10282 - 해킹 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 아이디어 - 가중치가 있는 단방향 그래프에서의 최단 경로 문제로, 다익스트라 알고리즘을 사용한다 - 방문 시간을 업데이트할 때, 기존 시간이 초기값일 시 방문 노드의 개수에 1을 추가해서 구한다 - 방문 시간을 보관한 배열에서 초기값을 제외한 값 중 가장 큰 값이 걸린 시간이다 코드 from heapq import * import sys input=sys.stdin.readline f=float('i.. (Python) 백준 1016 - 제곱 ㄴㄴ 수 https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 아이디어 - 특정 구간 내 모든 소수들을 효율적으로 구하기 위해서 에라토스테네스의 체를 사용 - 입력 값이 매우 크기 때문에 1부터 최대값이 아닌 최소값부터 최대값만 계산 코드 #입력 n,m=map(int,input().split()) #에라토스테네스의 체 생성 시 1이 아닌 최소값부터 시작 a=[1]*(m-n+1) for i in range(2,int(m**.5)+1): k=i*.. (Python) 백준 1600 - 말이 되고픈 원숭이 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 아이디어 - 가중치가 없는 그래프에서 최단 경로를 구하는 문제이므로 BFS를 사용한다. - 각 칸의 방문 여부를 체크할 때, 말의 움직임 횟수에 따라 개별적으로 체크해줘야 한다. 코드 from collections import deque import sys input=sys.stdin.readline # 입력 k=int(input()) w,h=map(int,input().split.. 이전 1 다음