Python) Algorithm_study

:현재상황에서 지금 당장 좋은 것만 고르는 방법그리디 해법: 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리게 하므로 정당성 분석이 중요하다.(가장 좋은 것만 반복적으로 선택했을때 최적의 해를 구할수 있는지 확인해야한다.)가장 큰값만 고르는 경우

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 (코테에서는 그리디 알고리즘의 정당성을 고민하면서 문제 해결방안을 떠올려야 한다)🔥의 개수는 체감 난이도입력조건: 첫째 줄에 모험가의 수 N이 주어진다,둘째줄에 각 모험가의 공포도의 값을 N이하의 자연수로 주

입력조건:첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다.(1<=N<=1,000)둘째줄에는 각 동전의 화폐단위를 나타내는 N개의 자연수가 주어지며 각 자연수는 공백으로 구분한다.(화폐단위는 1,000,000이하의 자연수)출력조건:첫째 줄에 주어진

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게

문제타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때,

어려웠던 문제와 문법 위주 복습하기 현재상황에서 지금 당장 좋은 것만 고르는 방법그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리게 하므로 정당성 분석이 중요하다. (가장 좋은 것만 반복적으로 선택했을때 최적의 해를 구할수 있는지 확인해야한다.)

구현이란?머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정구현 예시1\. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제2\. 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제3\. 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제->파이썬이 다른

알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다. 예를 들어 K1KA5CB7 이라는 값이 들어오면 ABCKK13 을 출력한다.입력조건:

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터

문제 설명레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다.레스토랑의 구

<문제>현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.맵의 각 칸은 (A, B)

원하는 데이터를 찾는 과정 \-DFS & BFS\-먼저들어온 데이터가 나중에 나가는 형식(선입후출)\-입구와 출구가 동일한 형태로 스택을 시각화파이썬에서는 리스트를 이용하면 된다.가장 왼쪽에 있는원소가 가장 먼저들어온 원소\-먼저들어온 데이터가 먼저 나가는 형식의 자료

<문제>N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이

<문제>어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한

<문제>NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으

✏️문제(18428) [감시 피하기] NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복도로 빠져나온 학생들은 선생님의

<문제>로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N)

정렬 >데이터를 특정한 기준에 따라 순서대로 나열하는 것을 의미 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨 데이터 정렬 방법 >7,5,9,0,3,1,6,2,4,8 1.선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택하여 맨 앞

하나의 수열에는 다양한 수가 존재하며, 이런 큰 수는 크기와 상관 없이 무작위로 주어진다. 이 수를 큰 수부터 작은 수까지 내림차순으로 정렬하면되는 문제다. 즉 수열을 내림차순으로 정렬하는 프로그램을 만들면된다.입력첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다.

도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.국어 점수가 감소하는 순서로국어 점수가 같으면 영어 점수가 증가하는 순서로국어 점수와 영어 점수가 같으면 수학 점수가 감소하는

✏️문제[실패율] 문제 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민

https://www.acmicpc.net/problem/10989https://www.acmicpc.net/problem/10989https://www.acmicpc.net/problem/2108

https://www.acmicpc.net/problem/2108a=원소 추가 대상 리스트 b=추가할 원소a=원소를 삭제할 대상 리스트->가장 작은 원소 삭제 후 값 리턴 참고 블로그:https://www.daleseo.com/python-heapq/

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법정렬되어있는 리스트에서 탐색범위를 절반씩 좀혀가며 데이터를 탐색하는 방법이진탐색은 시작점, 끝점, 중간점을 이용하여 탐색범위를 설정3번의 step만에 찾고자 하는 값이 존재하는지 , 어

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1, 1, 2, 2, 2, 2, 3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.단, 이

✏️문제[공유기 설치] https://www.acmicpc.net/problem/2110 ✏️문제[가사 검색] https://programmers.co.kr/learn/courses/30/lessons/60060 너무 어렵다... https://deok2kim.t

https://www.acmicpc.net/problem/2512https://www.acmicpc.net/problem/17266https://www.acmicpc.net/problem/2613

✏️문제[정수 제곱근] https://www.acmicpc.net/problem/2417 ✏️문제[이상한 술집] https://www.acmicpc.net/problem/13702 ✏️문제[도토리 숨기기]

참고블로그 : https://handhand.tistory.com/178https://ariz1623.tistory.com/274

다이나믹 프로그래밍:메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다다이나믹 프로그래밍의 구현은 일반적으로 두가지방식(탑다운(하향식), 보텀업(상향식))으로 구

https://www.acmicpc.net/problem/1463정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연

✏️문제[금광] n × m 크기의 금광이 있다. 금광은 1 × 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다. 이후에 m -

✏️문제[병사 배치] https://velog.io/@j_user0719/병사-배치-PYTHON ✏️문제[못생긴 수] ✏️문제[편집 거리]

https://www.acmicpc.net/problem/9095https://www.acmicpc.net/problem/1149https://www.acmicpc.net/problem/2156

가장 짧은 경로를 찾는 알고리즘다양한 문제상황1.한 지점에서 다른 한 지점까지의 최단경로2.한 지점에서 다른 모든 지점까지의 최단경로3.모든 지점에서 다른 모든 지점까지의 최단경로각 지점은 그래프에서 노드로 표현지점 간 연결된 도로는 그래프에서 간선으로 표현특정노드에서

✏️문제[전보] ✏️문제[미래 도시]

:공통원소가 없는 두 집합을 의미.서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조서로소 집합 자료구조는 두 종류의 연산을 지원1.합집합: 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산2.찾기: 특정한 원소가 속한 집합이 어떤 집합인지

그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건최소한의 비용으로 구성되는 신장 트리를 찾아야할때 어떻게 해야 할까예를 들어 N개의 도시가 존재하는 상황에서 두 도시

학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1 개의 팀이 존재한다. 이때 선생님은 '팀 합치기'연산과 '같은 팀 여부 확인'연산을 사용할 수 있다.'팀 합치기' 연산은 두 팀을 합치는 연산이다.