본문 바로가기

Algorithm231

[백준] 2589번 보물섬 사용 언어 - Python3, Pypy3 문제 - 2589번 보물섬 DFS (Depth-Frist search, 깊이 우선 탐색) = 경우의 수를 탐색하는 방법. 백트래킹 이용 BFS (Breadth-Frist search, 넓이 우선 탐색) = 노드와 노드의 관계를 탐색하는 방법. 그래프 탐색에 더 좋다. https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 정답 BFS 알고리즘을 활용해 그래프 탐색하기 BFS (deque()) = 샛길로 새지 않는다.. 2023. 11. 3.
[백준] 2606번 바이러스 사용 언어 - Python3 문제 - 2606번 바이러스 DFS (Depth-Frist search, 깊이 우선 탐색) = 경우의 수를 탐색하는 방법. 백트래킹 이용 BFS (Breadth-Frist search, 넓이 우선 탐색) = 노드와 노드의 관계를 탐색하는 방법. 그래프 탐색에 더 좋다. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 정답 DFS / BFS 알고리즘을 활용해 그래프 탐색하기 0. 그래프 형태로 입력받기 각 노드에서 연결된 .. 2023. 11. 3.
[백준] 10815번 숫자 카드 사용 언어 - Python3 문제 - 10815번 숫자 카드 이분탐색 : 업다운 게임. 절반부터 시작해서 효과적으로 범위를 줄인다. https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 정답 이분탐색 - 절반부터 값과 같은지, 큰지, 작은지 확인 후 포인터 수정 s = 0, e = n-1, mid = (s+e)//2 1. 정렬 시키기 이분탐색은 기준 숫자카드가 정렬되어 있어야 중간값보다 크고/작다 대소비교가 가능하다. .. 2023. 11. 3.
[백준] 16472번 고냥이 (투포인터 문제) 사용 언어 - Python3 문제 - 16472번 고냥이 투포인터 : 가능성을 지워주는 방법 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 정답 (투포인터) 양쪽 끝에서 비교하면서 만나면 종료 알파벳 종류가 n넘지 않는지 확인 + 최대 개수 확인 arr.rstrip() 불필요한 공백 제거 s = 시작포인터 = 0 e = 끝포인터 = 0 letters = [] 알파벳 종류 넣을 리스트 letters.append(arr[s]) 첫번째 값을 일단 넣고 시작.. 2023. 11. 3.
[백준] 22988번 재활용 캠페인 (투포인터 문제) 사용 언어 - Python3 문제 - 22988번 재활용 캠페인 투포인터 : 가능성을 지워주는 방법 https://www.acmicpc.net/problem/22988 22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 정답 (투포인터) 양쪽 끝에서 비교하면서 만나면 종료 두 병의 용량 반납 -> (A+B+X/2) 용량이 담긴 새로운 용기 s = 시작포인터 = 0 e = 끝포인터 = n-1 cnt = 채워진 용기 개수 rem.. 2023. 11. 3.
[백준] 3273번 두 수의 합 (투포인터 문제) 사용 언어 - Python3 문제 - 3273번 두 수의 합 투포인터 : 가능성을 지워주는 방법 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i 시간 복잡도 문제 ! 투포인터 알고리즘 활용 arr 정렬 후, s .. 2023. 11. 2.
[백준] 9251번 LCS (LIS 문제) 사용 언어 - Python3 문제 - 9251번 LCS LIS/LCS 문제 : 가장 긴 증가하는 부분 수열 LIS (Longest Incresing Subsequence) LCS (Longest Common Subsequence) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 정답 해당 위치 기준 나보다 작은 숫자가 있으면 추가해주기 dp[i] = max(dp[i], dp[j]+1) 완전탐색 방법).. 2023. 11. 1.
[백준] 2565번 전깃줄 (LIS 문제) 사용 언어 - Python3 문제 - 2565번 전깃줄 LIS/LCS 문제 : 가장 긴 증가하는 부분 수열 LIS (Longest Incresing Subsequence) LCS (Longest Common Subsequence) https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 정답 전체 n개에서 LIS 빼주기 dp[i] = max(dp[i], dp[j]+1) 전봇대에 겹친다 = A 전봇대 값이 작은 값 중에서, B전봇대 값이 더 크다. 안겹친다 = .. 2023. 11. 1.
[백준] 11053번 가장 긴 증가하는 부분 수열 (LIS문제) 사용 언어 - Python3 문제 - 11053번 가장 긴 증가하는 부분 수열 LIS/LCS 문제 : 가장 긴 증가하는 부분 수열 LIS (Longest Incresing Subsequence) LCS (Longest Common Subsequence) https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 정답 해당 위치 기준 나보다 작은 숫자가 있으면 추가해주기 dp[i.. 2023. 11. 1.
[백준] 1520번 내리막 길 사용 언어 - Python3 문제 - 1520번 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 정답 2차원 그래프의 DP # 모든 점을 방문 # 방문한 뒤 이동할 수 있는 모든 경우의 수를 재귀로 구현한다 # 재귀로 구현한 뒤 DP로 바꾼다. 현재 위치 graph[y][x] / 상하좌우 이동 dy,dx / 이동위치 ey, ex ey = y + dy, ex = x + ex 조건1) ex,ey가 m*n 그래프 안에 있어야함 조건2) .. 2023. 11. 1.

티스토리툴바