본문 바로가기
728x90
728x90

Language/Python

[Python][백준 2632][누적합] 피자판매 - 컴도리돌이 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 피자 A와 피자 B에서 나올 수 있는 피자 조각의 합 경우의 수를 각각의 딕셔너리에 저장한다. 하나의 피자에서 나올 수 있는 모든 경우의 수를 탐색한다. 하나의 피자에 존재하는 조각의 개수가 1000개 이하이므로 반복문 2개를 중첩하여 모든 경우의 수를 탐색하여도 시간 초과가 발생하지 않는다. 출력 딕셔너리_A [문제에서 요구하는 피자 사이즈] + 딕셔너리_B [문제에서 요구하는 피자 사이즈] + 딕셔너리_A [A에 있는 값] + 딕셔너리_B.. 더보기
[Python][백준 12015][이분 탐색] 가장 긴 증가하는 부분 수열 2 - 컴도리돌이 풀이 과정 해당 문제는 bisect 라이브러리를 사용해서 해결하였다. bisect에 대해서는 아래 링크를 참조하면 좋다. [Python] bisect - 컴도리돌이 알고리즘 문제를 해결하다가 다른 분의 블로그에서 제가 푼 알고리즘 문제를 파이썬에서 제공하는 표준 라이브러리인 bisect를 이용해서 간단하게 문제를 해결한 것을 보고, 요번 기회에 bisect 라 comdolidol-i.tistory.com 1. 입력받은 배열의 0번째 인덱스 값부터 순차적으로 반복문을 시행한다. 2. arr가 비어있으면 x 값을 arr에 insert 한다. 3. 현재 x 값이 arr의 마지막 인덱스 값보다 크면 insert 시킨다. 4. 마지막 인덱스 값보다 크지 않으면 bisect_left 함수를 이용해서 x값보다 같거나.. 더보기
[Python][백준 2470][투 포인터] 두 용액 - 컴도리돌이 풀이 과정 해당 문제는 단순한 투 포인터 문제이다. 두 값의 합이 0과 가까운 쌍을 찾으면 끝이다. 1. 주어진 x 배열을 정렬시킨다. 2. 문제에서 수들의 합이 매우 크기 때문에 minV를 매우 큰 값으로 설정하였다. 3. 투 포인터를 사용하기 때문에 0번째 인덱스와 n-1 인덱스부터 시작한다. 4. 오른쪽 인덱스 s와 왼쪽 인덱스 e의 합을 m으로 지정한다. 5. 절댓값 m이 minV보다 작을 경우 minV를 m으로 업데이트해준다. ans를 현재 x [s], x [e]로 업데이트해준다. 6. minV이 0이면 반복문을 종료하고 현재 ans을 출력한다. 7. m 값이 0보다 작을 경우 오른쪽 인덱스를 증가시키고 반대일 경우 왼쪽 인덱스를 감소시킨다. 풀이 코드 n,*x= map(int,open(0).r.. 더보기
[Python][백준 2234][BFS] 성곽 - 컴도리돌이 풀이 과정 본 문제는 전형적인 BFS문제이다. 왜냐하면 연결되어 있는 방의 개수를 물어봤기 때문이다. 부가적으로 특이한 요소를 첨가하였다. 각 좌표들 간에 연결되었는지를 15 이하의 값으로 주어져있다. 0~15 (?) 문제에서 언급한 힌트대로 이 문제는 좌표 이동을 비트 마스킹을 해준다. 하지만 비트 마스킹이 익숙하지 않아서,,, 나는 문자열로 표시를 하였다. 물론 하는 방법은 비트 마스킹이랑 똑같다..! "0000" ~ "1111" 맨 왼쪽부터 서북 동남을 의미하고 1은 이동 불가(벽으로 연결)를 의미하고 0은 이동 가능을 의미한다. 1. m*n 만큼 반복문을 돌려서 해당 (i, j) 위치를 방문하지 않을 경우 BFS 탐색을 한다. 2. 현재 위치 값을 bin함수를 이용하여 이진수를 나타내고 크기를 4.. 더보기
[Python][백준 2212][정렬][그리디] 센서 - 컴도리돌이 풀이과정 해당 문제는 좌표를 단순히 정렬시켜서 센서들 간의 거리를 저장하고 정렬하여 n-k까지 합을 구하면 된다. 여기서 n-k까지 합을 구하는 이유를 물어본다면,, 문제를 그리면서 푸는 것을 추천한다. 🙄 1. 센서 위치를 정렬시킨다. 2. x의 0번째 인덱스부터 n-1 인덱스까지 다음 좌표까지의 거리를 저장한다. 3. 다음 좌표까지의 거리들을 정렬시킨다. 4. 정렬된 좌표 간의 거리 리스트에서 n-k까지 합을 구하여 출력한다. 풀이 코드 n,k,*x = map(int,open(0).read().split()) ;x.sort() print(sum(sorted([x[i+1] - x[i] for i in range(n-1)])[:n-k])) 더보기
[Python][백준 2133][DP] 타일 채우기 - 컴도리돌이 풀이과정 해당 문제는 뭔가 일단 규칙성을 찾아야 하게끔 생겨 버렸다. 😶‍🌫️😶‍🌫️ 일단 n이 홀수이면 0인 거 알겠지만, n이 짝수일 때 규칙성을 찾는데 애를 먹었다. 일단 n이 2일 때는 3이다. 그다음 n이 4일 때는 11이다. 근데 여기서 n이 2일 때 경우의 수 각각 2,2이기 때문에 2 * 2에 새로운 모양 2개를 더해준 값이다. 그렇다면 일단 dp [2] * dp [2] + 2라고 표현할 수 있다. 그다음 n이 6일 때는 41이다. dp [4] * dp [2] + dp [2] * 2 + 2 그다음 n이 8일 때는 dp [6] * dp [2] + (dp [4] + dp [2] ) * 2 + 2 그다음 n이 10일 때는 dp [8] * dp [2] + (dp [6] + dp [4] + dp [.. 더보기
[Python][백준 20437][문자열] 문자열 게임 2 - 컴도리돌이 풀이과정 해당 문제는 시간 초과를 걸리 줄 알았는데, 생각보다 쉽게 해결되어서 허무(?)했던 문제였다. (원래 시간 초과 4개 걸리고 해결해야 짜릿한데,,🙄🙄) 1. 입력받은 w를 enumerate로 인덱스 번호(i), 문자열(str)로 열거하여 dictionary(ww)에 문자열의 인덱스를 삽입해준다. 2. 각 알파벳의 인덱스 정보를 담고 있는 ww를 반복문을 다음과 같이 수행한다. 3. 해당 알파벳의 인덱스 리스트를 'str_idx_list'라고 설정하였다. 4. 해당 리스트의 크기가 k보다 작으면, 문제에서 주어진 3,4번 조건을 만족하지 못하기 때문에 continue를 시킨다. 5. len_list는 k개를 포함하는 문자의 문자열 길이를 담는 리스트이다. len_list에 str_idx_list .. 더보기
[Python][백준 1194][BFS][bit masking] 달이 차오른다, 가자. - 컴도리돌이 풀이과정 해당 문제는 방문 표시만 제대로 하면 쉽게 해결할 수 있는 문제이다. 물론 방문 표시가 생각보다 까다롭다. 😂 시작점에서 끝점까지 도달하는 최단 거리는 너비 우선 탐색(BFS)으로 구현하면 된다. 그렇다면 이 문제의 핵심은 방문 표시이다. 탈출을 하기 위해서는 '.' 공간만 이용할 수 있다. 물론 주어진 n*m 행렬 맵에서는 키라는 특이한 요소를 첨가했다. 키의 종류는 a, b, c, d, e, f 총 6가지이며, 키의 종류 따른 문의 종류도 A, B, C, D, E, F 총 6가지이다. 문제에서는 탈출구까지 가는 길에 문이 있으면 해당 문에 맞는 키 값을 소유하고 있어야 한다. 그렇기 때문에 BFS 탐색할 때 방문 표시를 가지고 있는 키 값들에 따라 해주어야 한다. 키의 종류는 총 6가지이다... 더보기

티스토리툴바