본문 바로가기

알고리즘204

[백준] 11054번 - 가장 긴 바이토닉 부분 수열 (파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic programming) - 가장 긴 바이토닉 부분 수열 -> www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net (백준 - 11053번)가장 긴 증가하는 부분 수열 문제와 (백준 - 11722번) 가장 긴 감소하는 부분 수열 문제를 합치면 풀 수 있다. 가장 긴 증가하는 부분 수열의 아이디어를 채택해 우리는 1~n까지 탐색( i )하면서 그 이전까지 i번째 숫자보다 작으면서도 가장 긴 증가하는 부분 수열의 길이를 저장한다. 가장 긴 증가.. 2021. 3. 9.
[백준] 11722번 - 가장 긴 감소하는 부분 수열 (C++, 파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 가장 긴 감소하는 부분 수열 -> www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 참고) 2021.03.02 - [Algorithm_note/틀린 문제] - [백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬) [백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬) 문제) 백준 - 동적 계획법 .. 2021. 3. 9.
[백준] 1890번 - 점프 (파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 점프 -> www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 오른쪽이나 아래로 점프가 가능한 경우 dp 리스트에 +1 해준다. (0, 0)부터 시작해 (n - 1, n - 1)까지 재귀로 완전 탐색하며 (n - 1, n - 1)일 때 기저 사례를 처리해 1을 반환한다. 소스 코드) import sys sys.setrecursionlimit(1000000) input = sys.s.. 2021. 3. 9.
[백준] 1520번 - 내리막 길 (C++, 파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 내리막 길 -> www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 각 지점까지 이동할 수 있는 경로의 수를 저장한 2차원 리스트(dist)에 메모이제이션을 적용한다. dist 리스트의 초기값을 -1로 선언해 방문 여부를 판단한다. 각 지점까지 이동할 수 있는 경우의 수는 dfs를 이용하여 경로가 겹치는 지점에서 서로의 경로 수를 합친다. Python 소스 코드) C++ 소스 코드) Python .. 2021. 3. 9.
[프로그래머스] 2019 카카오 공채 - 실패율 (파이썬) 문제 및 풀이 문제) 프로그래머스 - 2019 카카오 공채 - 실패율-> 코딩테스트 연습 - 실패율 | 프로그래머스 (programmers.co.kr)코딩테스트 연습 - 실패율실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스programmers.co.kr ① 나의 풀이관찰을 하다 보면 플레이어가 도달한 스테이지( j )와 해당 스테이지( i )를 비교하여 실패율을 계산하여 실패율과 해당 스테이지를 result 리스트에 넣어준다. 플레이어가 도달한 스테이지가 해당 스테이지보다 높은 경우( j > i ): 플레이어는 스테이지에 도달했고 성공한 경우이므로 participant만 1을 늘린.. 2021. 3. 4.
[프로그래머스] 2019 카카오 공채 - 오픈채팅방 (파이썬) 문제 및 풀이 문제) 프로그래머스 - 2019 카카오 공채 - 오픈채팅방 -> 코딩테스트 연습 - 오픈채팅방 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr ① 나의 풀이 Dictionary 형태로 record의 유저 아이디와 닉네임을 취합하기 위해서 collections의 Counter 모듈을 이용하자. 각 record의 원소를 split 하여 order 리스트로 받아준다. record탐색을 두 번 해주는데, 첫 탐색에서 유저 아이디에 대한 최종 닉네임을 결정해주고 두 .. 2021. 3. 4.
[백준] 1904번 - 01타일 (C++/파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 1(Dynamic programming)- 01타일 -> www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net dp 가능한 숫자 dp[1] 1 dp[2] 11 00 dp[3] 111 001 100 dp[4] 1111 0011 1001 1100 0000 ... dp[n] dp[n - 1] ... dp[n - 2] n을 숫자의 길이, dp[n]에 해당하는 값을 가능한 숫자의 개수라 하자. '00' 타일과 '1' 타일을 붙이는데 별 다른 제약 조.. 2021. 3. 4.
[백준] 14502번 - 연구소 (파이썬) 문제 및 풀이 문제) 백준 - 너비 우선 탐색(BFS) - 연구소 - 14502번: 연구소 (acmicpc.net) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 벽과 바이러스가 아닌 모든 지역(space)을 탐색해 벽의 후보(wall_candidates)를 골라 준다. combinations를 이용해 조합을 만들어주고 원본을 유지하기 위해 deepcopy를 이용해 복사 후 벽을 세워 bfs로 탐색해준다. 그 후 각 조합마다 안전 지역 개수의 최댓값을 구한다. 완전 탐색으로 접근하면 쉽게 풀리는 문제이지만 처음에 그리디하게 접근해서 헤.. 2021. 3. 3.
[백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬) 문제) 백준 - 동적 계획법 (Dynamic programming) - 가장 긴 증가하는 부분 수열 -> www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 각 숫자로 만들 수 있는 가장 긴 증가하는 부분 수열의 길이를 저장할 length 리스트를 선언한다. 각 숫자(i)들을 차례대로 순회(0 ~ n)하면서 해당 숫자(i)보다 작고 가장 긴 증가하는 부분 수열을 찾아 그 길이에서 1을.. 2021. 3. 2.
반응형

티스토리툴바