[Python/파이썬] 백준 10942번: 팰린드롬?

문제 풀이 dp[i][j] : i ~ j까지의 수열이 팰린드롬인지 저장 ex) dp[1][3] = True : 1 ~ 3까지의 수열이 팰린드롬 수 arr 배열에 전체 수열 저장 1. 원소가 하나인 경우 무조건 팰린드롬 수 dp[0][0], dp[1][1], ... dp[n][n] = True 2. arr[i] == arr[i+1]인 경우 팰린드롬 수 (부분 수열의 길이가 2이고, 원소가 동일한 경우) ex) 11, 22, 33, 44 는 팰린드롬 수 3. a~b까지의 수열에서 arr[a] == arr[b]이고 그 사이의 수열이 팰린드롬인 경우 원소가 4개인 경우, 5개인 경우 ... 반복하면 된다. 코드 import sys input = sys.stdin.readline n = int(input()) a..

[Python/파이썬] 백준 1695번: 팰린드롬 만들기 / 파이썬 메모리초과 해결

문제 풀이 1. 주어진 수열에서 팰린드롬 수열을 구한다. 12342의 부분 수열 중 팰린드롬은 242(12342)이다. 2. 팰린드롬의 정 가운데를 기준으로 수열을 나눈다. 123 4 2 3. 팰린드롬이 아닌 수를 반대편에 추가한다. 123 4 321 수열에서 이미 팰린드롬인 수열을 구했고, 팰린드롬이 아닌 수만 추가하면 되므로 최적의 알고리즘이다. 또다른 예시 팰린드롬을 찾는 과정에서 DP가 이용된다. [수열 A] 12342 [수열 A를 뒤집은 수열 B] 24321 이 있다고 가정해보자. 수열 A와 수열 B의 최장 공통 부분 수열(LCS)이 곧 팰린드롬 수열이다. (수열 A를 뒤집었을 때의 부분 수열 = 수열 A의 부분 수열 이므로, 팰린드롬 수열의 조건을 생각해봐라) 말로 설명하기가 참 어렵다... ..

[Android] 디자인 패턴(참고 링크 모음)

프로젝트에 MVVM패턴을 적용하고 있으나 정확한 개념이 숙지되지 않아 정리해보려 한다. 우선 디자인 패턴 -> MVC -> MVP -> MVVM 순서로 공부하겠다. 디자인 패턴이란? 쉽게 말하면 디자인 패턴 = 검증된 소프트웨어 개발 설계 방법인 것 같다. 안드로이드 앱을 설계할 때 디자인 패턴을 적용 이미 검증된 패턴이므로 문제가 발생할 일이 적다. 정형화된 패턴이므로 개발자 간의 의사소통이 수월해진다. 더 유연하고 좋은 코드를 사용할 수 있다. 디자인 패턴은 크게 3종류로 나뉜다. 생성 패턴 구조 패턴 행위 패턴 생성 패턴 1. 추상 팩토리 인터페이스를 활용하는 패턴 https://sup2is.github.io/2020/06/22/abstract-factory-pattern.html Sup2's bl..

[Python/파이썬] 백준 17404번: RGB거리 2

문제 풀이 첫 번째 집의 색을 R로 선택하고 DP를 통해 최솟값을 구한다. G, B에 대해 반복 코드 import sys input = sys.stdin.readline n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] def minPaint(selHouse): dp = [[0] * 3 for _ in range(n)] dp[0] = arr[0] for i in range(3): if i == selHouse: dp[1][i] = 1e9 continue dp[1][i] = arr[1][i] + arr[0][selHouse] for i in range(2, n): dp[i][0] = min(dp[i - 1][1], dp[i..

2021.12.22 ~ 2021.01.22 회고 및 2022.1.22 ~ 2022.02.19 목표

2021.12.22 ~ 2021.01.22 회고 알고리즘 백준 골드1 달성 (하루 알고리즘 2문제씩 풀기, 공휴일 및 일요일은 1문제) 골드1 달성 성공! 하루 알고리즘은 1문제 정도밖에 못풀었다. SQL 생활코딩 DATABASE1 ~ 2 듣기 -실패 WEB 생활코딩 WEB1, WEB2 - CSS, JS 듣기 WEB1 - 성공 나머지 - 실패 프로젝트 비트모 리팩토링 수원대타임 - 강의평가 기능 추가 비트모 - 실패 수타 - 진행중 기타 부족한 부분 공부하기 - 진행중 2022.1.22 ~ 2022.02.19 목표 알고리즘 아래 알고리즘 졸업하기 골드1 이상 문제 풀면 졸업 DFS (졸업) BFS (졸업) 그리디 구현 이분 탐색 DP 백트래킹 소수 판별 투 포인터 구간 합 SQL 생활코딩 DATABASE..

[Python/파이썬] 백준 14942번: 개미

문제 풀이 1. 주어진 입력은 양방향 간선이므로 단방향 간선으로 만들어줘야함 2. 희소배열 사용 https://hello-capo.netlify.app/algorithm-sparse-table/ 🧩 [Algorithm] 희소 배열(Sparse Table) 알고리즘 | hello-capo! 희소 배열(Sparse Table) 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 데이터가 저장되지 않은 경우가 더 많은 희소 행렬과 같이, 희소 배열은 배열의 원소 위치가 연속적이지 않은 배 hello-capo.netlify.app 3. LCA와 유사하게 노드 탐색 https://cyberflower.github.io/2019/07/22/LCA.html LCA(Least Common Ancestor)..

[Python/파이썬] 백준 16437번: 양 구출 작전

문제 풀이 경로는 유일하므로 방문 처리는 따로 구현하지 않았다. 트리의 리프 노드까지 재귀를 통해 이동하고, 리턴 값을 통해 문제를 풀었다. 코드 import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline n = int(input()) tree = [[] for _ in range(n + 1)] for i in range(2, n + 1): type, amount, root = input().split() amount, root = int(amount), int(root) if type == 'W': amount = -amount tree[root].append((i, amount)) def dfs(x, amount): for next, nex..

[Python/파이썬] 백준 17616번: 등수 찾기

문제 풀이 등수를 찾을 노드 위로 몇 개의 노드가 있는지, 아래로 몇 개의 노드가 있는지 구하면 된다. 코드 import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline n, m, x = map(int, input().split()) up = [[] for _ in range(n + 1)] down = [[] for _ in range(n + 1)] for _ in range(m): a, b = map(int, input().split()) down[a].append(b) # a 아래에 b up[b].append(a) # b 위에 a visited = [False] * (n + 1) def dfs(x, graph, cnt): visited[x] ..

[Python/파이썬] 백준 16947번: 서울 지하철 2호선

문제 풀이 먼저 사이클을 구한다. 사이클은 하나만 존재하고, 길이는 3 이상 이어야 한다. for i in range(1, n + 1): if not visited[i]: tmp = [] if dfs(i, tmp): print(cycle) break def dfs(x, tmp): global cycle visited[x] = True tmp.append(x) for next in graph[x]: if visited[next]: if next in tmp: if len(tmp[tmp.index(next):]) >= 3: cycle = set(tmp[tmp.index(next):]) return True continue dfs(next, tmp) tmp.pop() 사이클을 이루는 노드에서 시작하여 깊이를 ..

[Python/파이썬] 백준 3584번: 가장 가까운 공통 조상

문제 풀이 백준 LCA 문제와 동일한 줄 알았는데 아니었다. https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 차이점은 LCA의 경우 양방향 간선으로 입력이 주어지지만, 가장 가까운 공통 조상의 경우 단방향으로 간선이 주어진다. 또한 LCA는 루트 노드가 1로 고정되지만, 가장 가까운 공통 조상의 경우 루트 노드를 직접 구해야 한다. 코드 import sys sys.setrecursionlimit(10**9) input = sys.stdin..