본문 바로가기

Python52

투포인터 (Two-Pointer) 알고리즘 00 개요목표: 코딩테스트 뽀개기!01 투포인터1. 투포인터란각 원소마다 모든 값을 순회해야할 때, O(N^2)연속하다는 특성을 이용해서 처리, O(N)두 개의 포인터(커서)가 움직이면서 계산처음부터 생각해내기 어려움, 쉬운 방법부터 생각하는 것 추천 (i.e., 일일히 다 계산해 본 후, 어떠한 패턴이 보이면 그 때 적용해보기)2. 연습 문제: 백준 2559 수열참조: https://www.acmicpc.net/problem/25591) 문제Q:매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이.. 2025. 2. 7.
실패율 - 프로그래머스 01 문제 설명슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라. 실패율은 다음과 같이 정의한다. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매.. 2025. 2. 6.
DP (Dynamic Programming) 알고리즘 00 개요목표: 코딩테스트 뽀개기!01 DP1. DP란Dynamic Programming이전의 값을 재활용하는 알고리즘예) 1 ~ 10 숫자 중 각각 이전 값들을 합한 값 구하기이전의 값을 활용해서 시간복잡도 축소 가능2. 연습 문제: 백준 117262×n 타일링링크: https://www.acmicpc.net/problem/117261) 문제Q:2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.입력:첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력:첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.예제 입력 1:더보기2예제 출력 1:더보기.. 2025. 2. 6.
롤케이크 자르기 - 프로그래머스 01 문제 설명철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다. 예를 들어, 롤케이크에 4가지 종류의 토핑이 올려져 있다고 합시다. 토핑들을 1, 2, 3, 4와 같이 번호로 표시했을 때, 케이크 위에 토핑들이 [1, 2, 1, 3, 1, 4, 1, 2] 순서로 올려져 있습니다. 만약 세 번째 토핑(1)과 네 번째 토핑(3) 사이를 .. 2025. 2. 6.
시뮬레이션 (Simulation) 알고리즘 00 개요목표: 코딩테스트 뽀개기!01 시뮬레이션1. 시뮬레이션이란각 조건에 맞는 상황을 구현하는 문제예: 지도상에서 이동하면서 탐험하는 문제, 배열 안에서 이동하면서 탐험하는 문제 등별도의 알고리즘이 없이 풀 수 있으나 구현력 중요매 시험마다 1문제 이상 무조건 출제됨2. 준비하기다른 알고리즘들과 달리, 상황을 보고 판단!3. 연습 문제: 백준 14503 로봇 청소기링크: https://www.acmicpc.net/problem/14503비고: 현재는 웹사이트에 없는 문제1) 문제Q:로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.로봇 청소기가 있는 장소는 N x M 크기의 직사각형으로 나타낼 수 있으며, 1 x 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽.. 2024. 12. 21.
리스트 내 중복값 제거하기 (Python) 00 개요리스트를 다루는 도중 리스트 안에 중복된 값이 존재할 때, 중복되지 않는 값들만 담은 리스트를 생성하는 방법에 대한 정리크게 두 분류로, 본래 리스트 안의 중복되지 않는 값들의 순서 보존 여부로 나뉨순서 보존 안 됨순서 보존됨set() 사용 pandas 라이브러리의 Series 객체의 value_counts 사용itertools 라이브러리의 groupby 사용dict.fromkeys() 사용 loop 사용 list comprehension 사용 pandas 라이브러리의 unique() 사용pandas 라이브러리의 Series 객체의 drop_duplicates 사용언제  어떤 사용법을 적용해야 할까?순서를 지켜야할 경우: dict.fromkeys(), loop, list comprehension.. 2024. 11. 25.
백트래킹 (Backtracking) 알고리즘 00 개요목표: 코딩테스트 뽀개기!01 백트래킹1. 백트래킹이란DFS와 같이 모든 경우의 수를 확인해야 할 때 사용됨DFS: 가능한 모든 경로(후보) 탐색, 그러나 불필요할 것 같은 경로를 사전에 차단하는 행동이 없으므로 경우의 수를 줄이지 못함 (i.e., N!가지 경우의 수를 가진 문제에는 적합하지 않음)for로는 확인 불가능한 경우 (깊이가 달라지는 경우)해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가야 되는 경우 모든 가능한 경우의 수 중 특정 조건을 만족하는 경우만 살펴봐야 하는 경우즉, 답이 될만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 해야하는 경우주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 .. 2024. 11. 8.
DFS (Depth-first search) 알고리즘 00 개요목표: 코딩테스트 뽀개기!1. 그래프 탐색이란 어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법 Graph: Vertex (어떤 것) + Edge (이어지는 것)2. 그래프 탐색 종류BFS: Breadth-first search (너비 우선 탐색)DFS: Depth-first search (깊이 우선 탐색) 01 DFS1. DFS란Depth-first search, 깊이 우선 탐색그래프 탐색 종류 중 하나Stack 또는 재귀 함수 사용, Queue 미사용!재귀 함수는 백트래킹 알고리즘에서도 사용!2. 재귀함수란자기 자신을 다시 호출하는 함수# 예시def my_function(a): c = a + 1 if c 주의: 재귀 함수가 종료되는 시점을 반드시 명시해야 됨재귀 함수의 깊이가 .. 2024. 11. 8.
BFS (Breadth-first search) 알고리즘 00 개요목표: 코딩테스트 뽀개기!1. 그래프 탐색이란어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법Graph: Vertex (어떤 것) + Edge (이어지는 것)2. 그래프 탐색 종류BFS: Breadth-first search (너비 우선 탐색)DFS: Depth-first search (깊이 우선 탐색) 01 BFS1. BFS란Breadth-first search, 너비 우선 탐색그래프 탐색 종류 중 하나Queue 사용, Stack 미사용!2. 준비하기1) 아이디어시작점에 연결된 Vertex 찾기 찾은 Vertex를 Queue에 저장 Queue의 가장 먼저 것 뽑아서 반복2) 시간 복잡도O(V+E)3) 자료구조검색할 그래프 방문여부 확인(재방문 금지) Queue: BFS 실행3. 연습 문제:.. 2024. 11. 4.

티스토리툴바