Language/Python

5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 과정 1. n이 100개라고 브루트 포스로 풀면 안 된다.. 100개의 데이터가 나올 경우, 나올 수 있는 가지 수가 2^99가 나온다. 이 문제는 dp문제로 문제에서 주어진 0보다 크거나 같고 20보다 작거나 같은 조건을 이용해서 해결해야 한다. 2. dp의 크기를 21으로 할당해준다. 그리고 주어진 배열(arr)의 첫 번째 인덱스의 값을 dp의 인덱스에 1로 설정한다. 첫 번째 숫자는 반드시 포함되어야 하기 때문에!! 3. 이중 반복문을 사용하였..

2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 과정 1. 최소 스패닝 문제로 풀었기에 입력받은 x, y, z와 인덱스 번호를 붙여서 before 배열에 삽입해주었다. 2. before 배열을 이중 반복문으로 다음과 같이 after 배열을 생성해주었다. 2-1. x, y, z 순으로 정렬하기 위해서 첫 번째 반복문의 범위를 3만큼 돌려서 각각 x, y, z 순으로 정렬해주었다. 2-2 두 번째 반복문은 범위를 1~n까지 설정하고 0번째 인덱스 값을 before_loc에 저..

알고리즘 문제를 해결하다가 다른 분의 블로그에서 제가 푼 알고리즘 문제를 파이썬에서 제공하는 표준 라이브러리인 bisect를 이용해서 간단하게 문제를 해결한 것을 보고, 요번 기회에 bisect 라이브러리를 정리할려고 한다. bisect bisect는 이진 검색 알고리즘을 이용하여 입력 받은 시퀀스를 검색하는 기능을 제공한다. import bisect tmp = [1,3,4,5] bisect.bisect(tmp,2) bisect_left, bisect_right bisect는 bisect_right와 동일하며, 이 두 함수는 리스트 a에 x와 동일한 값이 존재하면 해당 값의 뒷 인덱스 값을 반환한다. 하지만 bisect_left는 동일한 값의 인덱스를 반환하다. import bisect tmp = [1,..

1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 1379번: 강의실 2 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 풀이 과정 - 강의실 1. 강의실을 최소로 배정하는 개수를 구해야 한다. 2. heap에서 시작시간, 끝나는 시간, 강의실 번호를 heap push를 한다. 3. 첫 번째로 시작시간이 가..

17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 과정 1. bfs로 해결을 하였다. q에는 x, y 좌표 값과 이동 시간, 무기를 갖고 있는지 확인용 key 값을 1x4 배열로 넣어줬다. 2. 주의할 점은 방문 표시를 n x m 행렬로 해주면 안 된다. n x m으로 방문 표시를 하면 용사가 무기를 가질 때, 용사가 무기가 없어서 우회했던 경로를 다시 방문할 수 없기 때문에 시간 초과가 발생할 것이다. 3. q에서 pop을 할 때 x, y 값이 공주가 있는 곳(n-1, m-1)으로 올 경우..

Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 과정 1. 규칙성을 찾는다. 4 - > 9 - > 25 -> 81 4 -> ((2 * √4) -1)^2 -> ((2 * √9) -1)^2 -> .... 풀이 코드 start = 4 for _ in range(int(input())) : start = int(((start ** (0.5)) * 2 - 1 ) ** 2) print(start)

23843번: 콘센트 광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한 www.acmicpc.net 풀이 과정 1. 입력받은 충전 시간 배열을 내림차순 정렬을 시킨다. 2. 콘센트 배열을 생성시킨다. 3. 내림차순 정렬된 충전 시간을 콘센트 배열에 삽입한다. 3-1 ) 만약 콘센트 배열의 크기가 주어진 콘센트 개수(m) 보다 작을 경우 -> 콘센트 배열에 해당 time을 삽입 3-2 ) 만약 콘센트 배열의 크기가 주어진 콘센트 개수(m) 이상일 경우 -> 가장 작은 값 + 현재 time을 더해서 다시 삽입 4. 콘센트 배열에 있는 값 중 가장 큰 값을 출력한다. -> 가..

18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 풀이 과정 (처음 시도) 처음에는 이중 for문으로 방문하지 않은 i, j가 있다면 해당 위치가 중앙으로 두었을 때 문제에서 요구하는 이미지가 형성되고, 방문하지 않은 이미지라면 방문 체크하고 탐색하게끔 설정하였는데, 이렇게 두면 아무리 가로 세로 크기가 5 이하여도 시간 초과가 발생한다. ㅠㅠ 1. 다른 분의 코드를 참고해서 이중 for문을 사용하지 않고 오른쪽 열로 하나씩 좌표 값을 탐색 인자에 넣어줬다. 그리고 행이 n과 같을 경우 강도의 ..