본문 바로가기

전체 글

[Python][백준 2539][이분 탐색] 모자이크 - 컴도리돌이 2539번: 모자이크 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 www.acmicpc.net 풀이 과정 이분 탐색의 팁은 주체를 찾고 해당 주체를 target으로 잡아서 이분 탐색을 해주면 된다. 하지만 해당 문제를 3번이나 틀렸다.😂 1. 첫째줄부터 셋째 줄까지 입력을 받고 잘못 칠해진 칸(y, x) 값을 입력받을 때 높이(y)의 max 값을 left에 저장해줘야 한다... 해당 작업을 하지 않고 정형적인 이분 탐색의 left 값을 0으로 해놓아서 9%에서 바로 틀려버렸다 ㅠ 색종이는 밑변에 맞춰서 붙이기 때문에 최소한 가장 높은 높이의 색종이 칸을 가지고 있.. 더보기
[Python][백준 6137][투 포인터] 문자열 생성 - 컴도리돌이 6137번: 문자열 생성 첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N 더보기
[Python][백준 16434][이분 탐색] 드래곤 앤 던전 - 컴도리돌이 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 풀이 과정 1. 알고리즘 분류로 이분 탐색으로 되었지만 단순 구현으로 풀 수 있다. 하지만 오랜만에 이분 탐색으로 문제를 해결하였다. 2. 보통 이분 탐색에서는 target을 뭐로 정해야하는지 감을 잡기 힘들 때가 많다. 그럴 때는 물어보는 것(HmaxHp)을 target으로 잡아주면 좋다. 아님 말고 😊 3. 필자는 최소 hp 값을 찾기 위하여 hp을 target으로 잡았다. left = 0,.. 더보기
[Python][백준 11657][벨만포드] 타임머신 - 컴도리돌이 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 과정 그래프 문제에서 노드간에 걸리는 시간이 음수가 포함했다? -> 벨만 포드 음수 간선에 관하여 최단 경로 문제는 다음과 같이 분류할 수 있다. 1. 모든 간선이 양수인 경우 2. 음수 간선이 있는 경우 2-1) 음수 간선 순환은 없는 경우 2-2) 음수 간선 순환이 있는 경우 벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다. 또한 음수 간선의 감지할 수 있으며, 벨.. 더보기
[Python][백준 5557][DP] 1학년 - 컴도리돌이 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 과정 1. n이 100개라고 브루트 포스로 풀면 안 된다.. 100개의 데이터가 나올 경우, 나올 수 있는 가지 수가 2^99가 나온다. 이 문제는 dp문제로 문제에서 주어진 0보다 크거나 같고 20보다 작거나 같은 조건을 이용해서 해결해야 한다. 2. dp의 크기를 21으로 할당해준다. 그리고 주어진 배열(arr)의 첫 번째 인덱스의 값을 dp의 인덱스에 1로 설정한다. 첫 번째 숫자는 반드시 포함되어야 하기 때문에!! 3. 이중 반복문을 사용하였.. 더보기
[Python][백준 2887][최소스패닝트리][Union-Find] 행성 터널 - 컴도리돌이 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에 저.. 더보기
[HackerRank][SQL][JOIN] Advanced Join, SQL Project Planning - 컴도리돌이 SQL Project Planning | HackerRank Write a query to output the start and end dates of projects listed by the number of days it took to complete the project in ascending order. www.hackerrank.com Problem If the End_Date of the tasks are consecutive, then they are part of the same project. Samantha is interested in finding the total number of different projects completed. Write a query to output th.. 더보기
[Python] bisect - 컴도리돌이 알고리즘 문제를 해결하다가 다른 분의 블로그에서 제가 푼 알고리즘 문제를 파이썬에서 제공하는 표준 라이브러리인 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,.. 더보기
728x90

티스토리툴바