본문 바로가기

Algorithm/Baekjoon117

11054. 가장 긴 바이토닉 부분 수열 (Python) 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 최장 증가 부분 수열(LIS)을 활용하여 해결하는 문제다. LIS는 이 링크를 참고하자. LIS를 구하는 방법에는 dp를 사용하는 방법과 이분 탐색을 사용하는 방법이 있다. 이 문제는 dp를 사용하여 해결하면 된다. A 배열의 각 원소까지 증가 부분 수열을 만들었을 때의 길이를 구한다. 위와 같은 array가 있을 때 dp 배열의 의미는 각 인덱스까지의 증가 부분 수열 중 가장 긴 증가 부분 수열의 길이를 의미한다. 이렇게 한 번 dp를 구하고 이번에는 배열을 뒤집어서 한 번 .. 2022. 4. 26.
7453. 합이 0인 네 정수 (Python) 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 풀이 두 가지 방식으로 풀었는데 기본적으로 적용되는 것은 A, B, C, D 이렇게 4개의 배열을 두고 각각 더하는 것이 아니라, A 배열과 B 배열의 원소를 합한 결과(이하 AB라고 표기) 그리고 C 배열과 D 배열의 원소를 합한 결과(이하 CD라고 표기) 이렇게 두 개로 나누어 구한다. 이때 AB의 원소와 CD의 원소의 합이 0이 되려면 두 값의 부호가 반대여야 한다(ex. AB: 29, CD: -29). (1) Dict를 사용한 풀이 먼저.. 2022. 4. 25.
2539. 모자이크 (Python, Swift) 2539번: 모자이크 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 www.acmicpc.net 풀이 문제의 조건을 잘 읽어봐야 된다.......... 문제에 주어진 조건 중에서 모든 색종이는 반드시 도화지의 밑변에 맞추어 붙인다고 되어있다. 처음에 이걸 도화지의 모든 행의 밑변으로 이해하고 풀었는데 결국 해결하지 못하여 인터넷에 검색해서 풀이를 조금 봤는데 알고보니 가장 아래 밑변 하나를 의미하는 거였다. 이걸 알고나니 쉽게 문제를 해결할 수 있었다ㅎ. 문제에서 가장 작은 색종이의 크기를 물어보고 있다. 색종이의 크기가 N이고 N크기의 색종이로 잘못 칠한 칸을 주.. 2022. 4. 23.
2042. 구간 합 구하기 (Python) 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 세그먼트 트리를 사용하는 대표적인 문제이다. 해당 문제에 대한 풀이는 세그먼트 트리에 대한 포스팅을 참고하자. 코드 import sys input = sys.stdin.readline # 세그먼트 트리 초기화 # start, end: 범위(구간), node: 세그먼트 트리에서 노드 번호 def init(start, end, node): # start와 end가 같다는 것은 leaf node임을 의미.. 2022. 4. 22.
2116. 주사위 쌓기 (Python, Swift) 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 풀이 주사위를 접어보면 (A-F), (B-D), (C-E)와 같이 짝을 이루어 위와 아래가 된다. 즉, 입력으로 주어진 배열에서 인덱스로 봤을때 (0번-5번), (1번-3번), (2번-4번)과 같이 되는 것을 알 수 있다. 1번 주사위에서 임의의 아랫면의 숫자를 정한다. 그렇게 되면 윗면의 숫자 역시 알 수 있다. 윗면과 아랫면의 숫자를 제외한 나머지 4개의 면 중에서 가장 큰 숫자를 찾아서 더해준다. 1번의 위와 아래를 임시로 정하고 나면 나머지 주사위의 윗면과 아.. 2022. 4. 21.
5014. 스타트링크 (Python, Swift) 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 현재 위치에서 bfs를 통해서 목표 층인 G층에 최소 몇 번의 버튼 동작으로 이동할 수 있는지를 구할 수 있다. bfs를 수행할 때 방문 체크가 필요한데 이 문제에서는 건물의 전체 층에 대하여 현재 위치인 n층에 도착하기 위해 총 버튼을 몇 번 눌렀는지를 기록해둔다. 예를 들어, 현재 n층에 5번 버튼을 눌러 도착했는데 이전에 n층에 4번 버튼을 눌러서 도착했던 경우가 있다면 현재 이동 기록은 큐에 넣지 않는다. 하지만 현재 n층에 3번 버튼을 눌러 도착했다면 더 적은.. 2022. 4. 20.

티스토리툴바