본문 바로가기

분류 전체보기131

[백준] 2110번 공유기 설치 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/2110 이분 탐색 문제인 것을 알고 푸니까 쉽게 보였지만, 모르고 푼다면 구상하기에 꽤 어려울 것 같은 문제이다. [문제] 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x_1, ..., x_N이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이.. 2023. 2. 15.
[백준] 1654번 랜선 자르기 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/1654 어렵지 않은 이분 탐색 문제였다. [문제] 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되.. 2023. 2. 15.
[백준] 10816번 숫자 찾기 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/10816 이분 탐색을 이용한 문제이다. [문제] 숫자 카드는 정수 하나가 적혀 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. [입력] 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이.. 2023. 2. 15.
[백준] 1920번 수 찾기 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/1920 쉬운 이분 탐색 문제였다. [문제] N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. [입력] 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다. [출력] M개의 줄에 답을 출력한다. 존재하면 1을, 존재하.. 2023. 2. 14.
이진 탐색 - 정렬된 배열에서 특정 수의 개수 구하기 [문제] N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1,1,2,2,2,2,3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. [입력] 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. (1 2023. 2. 14.
이진 탐색 - 떡볶이 떡 만들기 이 문제는 백준 나무 자르기 문제와 동일한 문제로 아래 링크에서 채점이 가능합니다. https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net [문제] 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다... 2023. 2. 14.
이진 탐색 이론 bisect이진 탐색이란, 기존의 하나하나 검사하는 탐색 방법보다 더 빠른 탐색 알고리즘이다. 원래대로라면 길이가 N인 배열에서 어떠한 원소를 찾고자 한다면, 처음부터 N개의 원소를 하나하나 검사해보는 방식으로 탐색을 한다. 따라서 기존의 탐색 시간복잡도는 O(N)이다. 하지만 배열이 정렬되어 있다는 가정 하에 이진 탐색은 더 빠른 시간복잡도를 보장한다. 이진탐색이란? 이진탐색이란 정렬되어있는 배열에서 특정 값을 찾는 방법이다. 찾고자 하는 값을 target이라고 할 때, 배열의 중간 위치의 값이 target보다 작은지 큰지를 검사한다. 배열을 반으로 나눈 후 중간 위치의 값이 target보다 작다면 뒤의 배열에서 같은 방식으로 탐색을 반복하고, 크다면 앞의 배열에서 같은 방식으로 탐색을 반복한다. 길이.. 2023. 2. 13.
정렬 이론 이것이 코딩테스트다에 있는 정렬은 다음과 같다. 선택정렬 삽입정렬 퀵정렬 계수정렬 1. 선택정렬 선택정렬은 가장 작은 값을 선택해 앞으로 보내는 과정을 반복하여 배열을 정렬해준다. 예를 들어 [3, 2, 5, 1, 4]라는 배열이 있다면, 이 배열에서 가장 작은 값인 1을 맨 앞의 3이랑 위치를 바꿔준다. [1, 2, 5, 3, 4]에서는 이미 정렬된 1을 제외한 [2, 5, 3, 4] 중 가장 작은 데이터인 2를 맨 앞으로 보낸다. (2가 이미 맨 앞의 숫자라 달라진 점은 없다.) 그 다음엔 [1, 2, 5, 3, 4]에서 이미 정렬된 1, 2를 제외한 [5, 3, 4] 중 가장 작은 데이터인 3을 맨 앞의 5랑 바꾼다. [1, 2, 3, 5, 4]에서 같은 방식으로 남은 5, 4의 위치를 바꿔주면 완.. 2023. 2. 13.
감자조림 오늘은 하이퍼마켓에 갔다가 감자를 너무 싸게 팔길래 바로 업어왔다. 그치만 너무 많이 사버려서 오늘 당장 뭔가 해먹어야겠다 생각했다. 처음엔 감자전을 해보려다가 감자를 갈 수가 없어서 포기... 검색 좀 하다가 감자조림으로 땅땅땅~ 사실 원래는 딱히 업로드할 생각이 없었는데 먹어보니까 너무 맛있어서 업로드 하는 것이다! 그래서 중간과정 사진이 없음 ㅜㅅㅜ (순서랑 재료만 좀 끄적이겠음) 재료 감자 2개, 당근 1/3개 양념 : 물 150ml, 진간장 5, 올리고당 3, 설탕 1, 미원 0.3?, 백종원표 매운소스 약간 레시피 재료 준비 감자, 당근 토막썰기 - 당근은 감자보다 더 작게 썰고, 감자는 찬물에 담궈두기 양념 재료 모두 섞어놓기 1. 팬에 식용유 두르고 강불에 감자만 투하 냄비에다가 하면 큰일.. 2023. 2. 10.

티스토리툴바