코딩테스트_파이썬

IEEE754 표준에는 실수형을 저장하기 위한 4바이트, 혹은 8바이트의 고정된 크기의 메모리를 할당하므로, 실수형을 표현하는 데에 있어서 정확도가 떨어집니다.그렇기에 0.6 + 0.3는 0.9이지만, 0.89999... 로 값이 나옵니다.왜나하면 2진수에서 0.9를

상근이는 요즘 설탕공장에서 설탕을 배달하고 있습니다. 그는 사탕가게에 정확히 N킬로그램의 설탕을 배달해야 하며, 설탕은 3킬로그램과 5킬로그램 봉지에 담겨 있습니다. 상근이는 최대한 적은 봉지를 들고 가고자 합니다.상근이가 설탕을 정확하게 N킬로그램 배달하기 위해 필요

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

거스름돈 1260원을 가장 적은 갯수의 잔돈으로 나눠주려면 어떻게 해야 하는 가? 시간 복잡도 화폐의 종류가 k라고 할 때, k 번 반복하므로 O(k)이다. 1이 될때까지 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는

Queue는 이미 대학교에서 배웠구, 이미 잘 알고 있는 내용이지만, 그때의 나는 이미 알고리즘을 안 써 본지 너무 오래되기도 했구... 코테를 공부하고 있는 시점이니. 다시 큐에 대해서 정리하는 방법을 적어본다.Queue는 기본적으로 선입선출되는 자료구조이다. 그렇기

두 수 $a$와 $b$가 있을 때, $a$를 $b$로 나눈 나머지를 $r$이라고 할 때, $GCD(a, b) = GCD(b, r)$입니다.이 과정을 반복하여 나머지가 0이 될 때의 $b$가 최대 공약수입니다.다음과 같은 방법으로 구현할 수 있습니다.혹시 까먹을 거 같아

깊이 우선 탐색(Depth First Search, DFS)이란 말로써, 가장 깊은 곳부터 먼저 탐색하고, 차례대로 낮은 순을 찾아가는 방법이라고 보면 된다.업로드중..

너비 우선 탐색(Breadth First Search, BFS)은 그래프 탐색 알고리즘의 하나로, 시작 노드에서 인접한 노드들을 먼저 탐색한 다음, 그 다음 단계의 노드들을 탐색하는 방식입니다. BFS는 주로 최단 경로를 찾거나, 레벨 순서대로 노드를 방문할 때 유용합

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

stack[::1]에 대한 설명 stack[::1]는 파이썬에서 리스트나 배열을 슬라이싱하는 방법 중 하나입니다. 여기서 stack은 리스트, 배열, 또는 다른 시퀀스 타입을 의미합니다. 슬라이싱 구문은 start:stop:step 형식으로 구성되며, ::1은 다음

출처 : 실전문제, 이것이 코딩테스트다 with 파이썬본 문제는 BFS를 바로 체험해볼 수 있는 문제라고 한다. 전체적인 원리도 이해가고, 어떻게 해야 할지는 알겠지만, 역시 어떤 경우에 BFS를 사용해야 할지를 모르겠다. 해당 부분은 조금 더 코드를 작성해보고, 연

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.첫째 줄

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로

오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든

Python을 사용하여 알고리즘 문제를 풀 때, 입력을 받는 방법은 성능에 큰 영향을 미칠 수 있습니다. 특히 대량의 데이터를 처리해야 할 때, 기본 input() 함수보다 더 빠른 방법이 필요한데, 그 해결책 중 하나가 바로 sys.stdin.readline입니다.

안녕하세요! 오늘은 Python에서 자주 발생하는 재귀 오류(RecursionError)와 이를 해결하는 방법에 대해 이야기해볼게요. 재귀 호출이 너무 깊어지면 이 오류가 발생하는데요, 여러 가지 해결책이 있습니다.Python의 기본 재귀 깊이는 1000으로 제한되어

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로

오늘은 파이썬에서 문자열을 다룰 때 매우 유용한 strip() 메서드에 대해 알아보려고 합니다. 이 메서드는 사용자가 입력한 데이터나 파일에서 읽어온 문자열의 앞뒤 공백을 쉽게 제거해줍니다. strip() 메서드는 문자열의 양쪽 끝에 있는 공백을 제거해줍니다. 기본적으

문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다.선택정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다.구현 방식은 오차가 있을 수 있지만, 전체 연산 횟수는N + (N-1) + (N-2) + ...

이 모듈은 우선순위 큐를 구현하는 데 유용하게 사용되는데요, 특히 최소 힙(min-heap) 구조를 쉽게 만들 수 있습니다. 파이썬의 heapq 모듈은 리스트를 기반으로 힙을 구현합니다. 이 모듈을 사용하면 데이터를 효율적으로 관리하고, 가장 작은 원소를 쉽게 찾고

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.지훈이와 불은 매 분마다 한칸씩 수평또는 수직

이 자료는 이코테 2021 강의 몰아보기에서 참고하여 작성했습니다.순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이진 탐색은 시

N개의 정수 A1, A2, …, AN이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A1, A2, …, AN이 주어진다. 다음 줄에는 M(1

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.목재절단기는 다음과 같

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터

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

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.첫째 줄에 테스트 케이스의 개수 T가 주어진다.

45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다

해당 포스트는 (이코테 2021 강의 몰아보기) 7. 최단 경로 알고리즘를 참고한 자료입니다.가장 짧은 경로를 찾는 알고리즘을 의미합니다.다양한 문제 상황한 지점에서 다른 한 지점까지의 최단 경로한 지점에서 다른 모든 지점까지의 최단 경로모든 지점에서 다른 모든 지점까

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하

첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.처음에

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.상근이는 오직 자기 자신

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는

서로소 집합(Disjoint Sets) 란 공통 원소가 없는 두 집합을 의미.서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조서로소 집합 자료구조는 두 종류의 연산을 지원.합집합(union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는