본문 바로가기
728x90

파이썬10

[백준/BOJ] 27172번 - 수 나누기 게임 (Python) 문제링크 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 1. 핵심 1) 유형 DP: [@+작은 팰린드롬+@] 작은 팰린드롬 양쪽의 @만 확인해서 더 큰 팰린드롬 [@+작은 팰린드롬+@] 인지 확인 2) 왜 reversed(range(n))을 할까? IF. reveresed가 아니라 range(n)을 생각해보자. → 인덱스의 범위가 (0, x)가 팰린드롬을 확인하기 위해서는 작.. 2023. 10. 28.
[Java] 1주차 스터디 - 파이썬 list 자바 Array, ArrayList 에 대해! 1. Array 연관된 data를 메모리상에 연속적이며 순차적(ordered)으로 미리 할당된 크기(fixed-size)만큼 저장하는 자료구조 장점: 조회가 매우 빠름 단점: 미리 할당된 크기를 선언해야하므로 메모리 낭비 또는 할당된 사이즈를 넘는 경우 문제 발생 시간복잡도 조회: O(1) 추가: O(1) 삽입, 삭제: O(n) 2. Python - list와 Java - ArrayList 1) Python의 list와 Java의 ArrayList 내부 로직 - Dynamic Array 거의 동일하므로 [ Java-ArrayList = Python - list ]로 생각하면 세상 쉽다! [차이점] Python-list에서는 Object의 주소값이 들어가서 타입 제한 없이 요소가 될 수 있다. 내부로직(D.. 2023. 10. 21.
[백준/BOJ] 27172번 - 수 나누기 게임 (Python) · 문제링크 https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net · 핵심 : 약수 + 시간복잡도 → 문제 요약 : 내가 다른 수를 나눠서 나머지가 0이면 +1 득점, 나뉘어진 수를 가진 상대방은 -1 감점 1. 시간복잡도 계산 → 바로 떠오르는 풀이는 이중 for문 써서 전부 확인하는 방법 → N = 100,000이므로 이중for문 사용하면 반드시 시간초과 발생 2. 약수 구하기 → 제곱근까지만 확인하기 : 시간복잡도 O(N^(1/2)) 3. +1 과 -.. 2023. 10. 17.
[코드트리 챌린지] 3주차 - 2차원 바람 · 문제링크 https://www.codetree.ai/cote/13/problems/The-2D-wind-blows?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai · 핵심 : 2차원 돌리기 1. 대상이 되는 2차원 좌표들의 집합 모으기 # 2차원 회전 - 좌표집합 밀기로 접근 def get_grids(r1, c1, r2, c2): qs = deque([]) for col in range(c1, c2 + 1): qs.append((r1, col)) for row in range(r1.. 2023. 9. 29.
[백준/BOJ] 2623번 - 음악프로그램 (Python) · 문제링크 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net · 핵심 : 위상 정렬 - 「 in-degree를 활용한 방법」 1. 방향성이 존재하는 그래프 생성 & 들어오는 간선 수 기록 → 3 1 4 3 → 3 : 가수의 수, 1 4 3 : 가수의 번호 → 1 - 4 / 4 - 3 으로 그래프 연결 2. in-degree = 0인 후보들 적절한 자료구조(리스크, 큐, 스택, 힙 등)에 넣기 3. candiates가 전부 비.. 2023. 9. 29.
[백준/BOJ] 1347번 - 미로 만들기 (Python, Java) · 문제링크 https://www.acmicpc.net/problem/1347 1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net · 핵심 1. 시작점이 설정되어있지 않다. → 명령어의 최대 길이는 50이므로 넉넉하게 아주 큰 board를 생성하고 적절한 시작점을 임의로 설정한다. → max_n = 200, cr = max_n // 2 , cc = max_n // 2 2. 큰 board에서 이동한 영역을 추출하기 → 도착을 1로 표시 → 사각형을 추출하기 위해서 1이 존재하는 (행, 열)들 중에서 min_r, .. 2023. 9. 25.
728x90
반응형