알고리즘 문제풀이

용액을 리스트를 통해 입력 받고 오름차순으로 정렬한다.l = 0, r = n-1 을 할당해주고 두 포인터 방식으로 while문을 통해 인덱스가 l인 값과 r인 값의 합을 비교, answer 리스트에 l,r 의 초기값 할당flag에 리스트의 가장 첫 값과 마지막값의 합의

이분 탐색을 사용하였다.trees 리스트에 나무 높이들을 입력받음나무 높이 순대로 오름차순 정렬start = 0, end에 트리 높이 들의 합 할당while문의 종료조건은 start<=end첫 중간값은 (start+end)//2 로 설정result = 0으로 할당

ㄴㅇㄹ

문제

수열이 있다. 이 수열을 큰 수부터 작은 수의 순서로 정렬하라.(입력 조건)1.첫째줄에는 수의 갯수 N이 주어진다. (1 ≤ N ≤ 500)2.둘째줄부터는 N+1번째 줄까지 N개의 수가 입력된다. (각 수는 1 이상 100,000 이하의 자연수이다.)(입력 예)3152

N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.입력첫 번째 줄에 학생의 수 N이 입력된다. (1<= N <= 100

동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다동빈이는 최대 K 번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소

문제전자 매장에는 부품이 N개 있다.어느날 손님이 M개 종류의 부품을 구매하려고 한다.이 때 매장에서 손님이 사려고 하는 부품이 있는지 yes와 no 형태로 구하라.예시입력 :array = 9, 3, 7, 9, 2target = 5, 7, 9결과 : no yes yes

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.절단기에 높이 H를 지정하면

이 문제도 보자마자 실행시간은 2초인데 입력값이 큰거로 보아 이진탐색을 사용해야 될 것같아 먼저 이진탐색으로 풀이를 진행했다. 1\. n,k를 입력받는다. 2\. 리스트를 입력받고 정렬한다.(이진탐색을 사용하는 문제지만 리스트 안의 값들이 기준이 되지 않기 때문에 정

내 풀이 (시간초과) 처음 문제를 풀때 각 전화번호를 문자열로 입력받고 입력받은 문자열들을 문자열 길이로 정렬을 먼저 하였다. 그 뒤 각 문자열을 비교해가며 접두어가 있는지 없는지 확인해봤는데 시간초과로 틀렸다.. 시간 초과로 틀린 코드 중간에 불필요한 과정들을 전부

풀이파이썬의 정렬 라이브러리를 사용하면 매우 쉽게 풀 수 있다.나는 가장 처음 정렬해야 되는 국어점수가 내림차순이라 reverse=True를 써서 정렬해서 뒷부분의 이름 순 정렬에서 오류가 나서 몇 번 오답을 제출했다. 문자열은 -를 붙여서 정렬 순서를 바꾸지 못한다는

처음에 그냥 생각나는 대로 코드가 쳐지는 대로 문제를 풀었다. 단순히 입력받고 전체 집의 위치 마다 안테나를 설치해가며 거리를 비교했다. 그 후 설치한 위치마다의 안테나와 집의 거리 차이를 리스트에 저장한 뒤 거리 순으로 정렬 후 집의 위치별로 정렬해서 가장 앞의 값을

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

고정점(Fixed Point)이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a = {-15, -4, 2, 8 ,13}이 있을 때 a2 = 2이므로, 고정점은 2가 됩니다.하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며,

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

우선 입력되는 배열이 굉장히 크다. 제한시간은 1초라는 걸 생각하면 정렬과 더불어 이분탐색을 사용해야 된다는 것을 알 수 있다. 저번에 푼 이코테\_정렬되어있는 배열에서 특정 수의 개수 구하기에서 사용했던 파이썬의 이분탐색 라이브러리인 bisect를 사용하면 굉장히 쉽

우선 입력값이 n부터 100만 사이이다. 시간제한은 1초 이내이므로 탐색 중에서 이분탐색을 떠올렸다. start는 0부터 end는 신청 예산중 제일 높은 금액을 할당한 뒤 전형적인 이분탐색을 진행하면 답을 구할 수 있다.정답 코드

일단 내 풀이는 틀렸다. 이분 탐색을 이용하여 start에 위치한 값과 end에 위치한 값, 그리고 그 둘의 중간에 있는 mid에 위치한 값의 크기가 가장 작을 때를 찾는 로직을 짰으나 처참히 틀리고 말았다. 여러 반례들을 찾아가며 확인했을 때 전부 답을 출력했기에

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

이 문제는 크루스칼 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제이다.1\. union-find 함수를 구현하여 지역들과 각 지역들을 연결한 간선 그리고 각 간선들의 크기를 저장한다.2\. 그 후 각 간선들의 크기를 오름차순으로 정렬한다.3\. 크루스칼 알고리즘으로 최

처음에 풀이 할때는 check 변수를 두고 일일이 크레인 리스트를 돌려가며 확인했다. 결과는 오답을 받았는데 이는 무작정 작은 것들 먼저 크레인과 비교하다 보니 큰 것과 작은 것들을 섞어 넣었을 때 더 최적의 결과를 내는 경우를 무시하는 결과를 가져왔기 때문이었다.

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

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다.

이것이 코딩테스트다에 수록되어있는 미로찾기 문제와 유사한 문제로 BFS를 이용하면 풀 수 있다. 이처럼 그래프에서 간선의 비용이 동일할 때 BFS를 이용하면 최단거리를 찾는 문제의 해답에 쉽게 접근할 수 있다. 1\. 특정 도시 x를 시적으로 BFS를 수행한다. 2\

우선 문제 자체는 전체 연구소 지도에 벽 3개를 세워 바이러스가 퍼지는 공간을 최소화 하는 문제이다. 언뜻 보기에 쉬워보였지만 생각보다 애를 먹었다. BFS를 이용해서 벽을 세운 뒤의 안전구역을 세는 건 손쉽게 작성했지만 벽을 세우는 부분에서 막혀버렸다. 결국 다른

bfs를 사용해서 문제를 풀면 되지만 바이러스가 퍼지는 순서가 정해져 있으며 정해진 시간만큼만 퍼진다는 조건 때문에 조금 까다로웠다.1\. 가장 초기상태의 바이러스 위치들을 입력받는다. 2\. 바이러스 숫자, x좌표, y좌표를 입력받고 바이러스 숫자에 맞춰 정렬한다.3

처음 문제를 봤을 때 이게 왜 DFS/BFS 문제야? 하고 의아해했다. 문제만 놓고 보면 처음에는 그냥 그리디 문제인가 싶었지만 찬찬히 생각해보니 DFS/BFS 방식으로 풀 수 있겠구나 싶었다. 우선, 연산의 개수는 + 와 - 두가지 밖에 없다. 그렇다면 각 매번

문제 풀이 이

어째서 알고리즘 분류에서 이 문제가 정렬 문제로 분류가 되었는지 의문이 생기는 그런 문제였다. 풀이는 단순 무식하게 정렬 한 뒤 수를 묶는 경우의 수를 모두 코드에 작성하면 된다. 정렬보다는 그리디 문제라고 생각한다.

생각보다 푸는데 시간이 좀 걸렸다. 이 문제를 품에 있어 bfs를 적용하기까지 생각하는 시간이 좀 오래 걸린 셈이다.그냥 단순히 모든 층의 경우에 버튼을 누르는 최솟값을 구하는 과정을 반복하다보면 답이 나오지 않겠나라고 생각하니 풀린 문제.

전형적인 bfs 문제다. bfs로 계속해서 노드를 탐색하고 visit 배열에 노드를 방문하기 위해 거친 edge의 개수를 저장해가며 탐색하면 쉽게 답을 구할 수 있다.

DP문제는 풀이 방식을 떠올리기가 너무 어려운것 같다.이 문제는 시간제한이 있어 문제에 나와있는 소스코드를 그대로 사용하려고 하면 시간초과가 난다.(본인이 그렇게 날로먹으려다 실패했다.) 시간을 최대한 줄이기위해서 우선 구해야하는 것이 무엇인지 먼저 보았다.재귀적인 방

이 문제도 dp문제이다. dp 문제는 참 풀이를 떠올리기 너무 어려운 것 같다. 혼자 풀다가 정 안되서 다른 분의 풀이를 참고하여 문제를 풀었다. https://mong9data.tistory.com/68 해당 블로그 분의 풀이가 굉장히 상세하게 잘 쓰여져

개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있ㄷ으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을

정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.1) X가 5로 나누어떨어지면, 5로 나눈다.2) X가 3으로 나누어 떨어지면, 3으로 나눈다.3) X가 2로 나누어 떨어지면, 2로 나눈다.4) X에서 1을 뺀다.정수 X가 주어졌을때, 연산

이 문제는 문제를 푸는데는 오래 걸리지 않았지만 문제를 이해하는데 시간이 좀 오래 걸렸다. 각 기업들은 숫자로 구분되고 자체적인 통신센터가 존재한다.각 기업의 서버들을 네트워크로 연결하여 단일 통신센터에서 관리가능하게 구성하기로 하였는데 그 방법은 다음과 같다.1\.

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다.태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다.이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.예를 들어, 2X3 크

문제N가지 종류의 화폐가 있다.이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.예를 들어 2원, 3원 단위의 화폐가 있을

어려운 문제였다. 벽을 부수며 이동하였을 때 벽을 부순 경우와 부수지 않았을 경우를 어떻게 나누어야 하는지 한참을 고민했는데 결국 스스로 해결하진 못했다..다른 풀이를 참고한 결과 visited 배열에 벽을 부쉈을 경우를 추가하여 3차원 배열로 만들어 해결할 수 있었다

간단하게 dfs를 이용해서 풀면 된다. 입력되는 값을 인접리스트 방식으로 입력 받고 dfs 함수를 돌리면서 현재의 노드가 어디와 연결되어 있는지를 root 배열에 저장하면 된다.

BFS를 사용하면 쉽게 풀 수 있는 문제이다.각 영역들의 좌표를 이용하여 직사각형이 그려진 영역은 1로 채우고 나머지 영역은 0으로 채워둔다.0으로 채워져 있는 영역의 넓이를 구하고 더 구하지 못할 때 리스트에 추가하는 방식으로 각 영역의 넓이를 리스트에 채우면 된다.

전형적인 dfs 문제이다. dfs 방식을 이용하여 주어진 두 사람 중 한명만 각 가족구성원과의 관계를 리스트에 저장한 뒤 출력하면 된다.

저 지그재그 순서를 처음에 이해를 잘 못해서 헤맨 문제이다.직접 일일이 그려가며 풀어보면 금방 풀 수 있는 문제였다. 배열 상에서 지그재그로 그려가면 각 대각선에 포함되는 분수들이 보이는데 첫번째는 1/1, 두번째 줄은 1/2, 2/1, 세번째 줄은 3/1, 2/2,

이 문제는 파이썬의 replace 함수를 통해 아주 간단하게 풀 수 있다.문제에 있는 크로아티아 알파벳들을 배열에 저장해둔 뒤 입력된 단어에서 크로아티아 알파벳 배열에 포함된 것들은 자릿수가 하나인 알파벳으로 바꾼 뒤 문자열의 길이를 출력하면 된다.이때, dz= 를 배

간단하게 현재 위치에서 앞 뒤는 같은 색이 되지 않는다 생각하고 풀면 쉽게 풀린다.

문제

이 문제는 스스로 풀지 못했다. 처음에 풀이는 단순히 가장 큰 자릿수에 위치한 알파벳들부터 높은 숫자를 채우는 방식대로 풀려하였으나 정답이 아니었다.자세한 풀이는 다음의 블로그를 참고하였다.https://seongonion.tistory.com/111?cate

간단한 그리디 문제이다.로프들을 하나씩 추가해 나가면서 들 수 있는 중량의 값을 갱신해나가면 되는데 w 중량의 물체를 k개의 로프로 들어올릴때 각 로프가 감당하는 무게는 w/k라는 점을 생각해서 코드를 작성하면 된다.

이 문제는 두 가지 방법으로 풀 수 있다.투 포인터 방법과 이진탐색 방법인데 투 포인터 방식은 간단하게 생각하면 금방 떠올릴 수 있다. 처음과 끝에서 시작해서 값을 비교해가며 답을 찾아가면 된다.이진 탐색으로 푸는 방법은 사실상 투포인터 방식과 비슷한데 용액의 i번째

이 문제는 두가지 풀이법이 있다. top-down 방식으로 b를 a로 만들어가는 방식과 bottom-up 방식으로 a를 b로 만드는 bfs방식이 있다.문제에서 a를 b로 만들어가는 방식에는 x2 연산과 끝자리에 1을 붙여가는 방식이 있다. 즉, b가 짝수이거나 끝자리가

파이썬의 heapq 라이브러리를 사용할 줄 안다면 쉽게 풀 수 있는 문제이다.heapq는 최소 힙 구조를 제공해주며 우선순위 큐라고 생각하면 된다.먼저 각 수업들의 시간을 입력받고 시작시간을 기준으로 정렬해준뒤 heapq에 넣어가며 끝나는 시간보다 먼저 수업이 시작되면

한참을 해맨 문제. 문제만 보고 간단할줄 알고 막 덤벼들었다가 시간을 많이 소비했다. 측정가능한 구간을 상정하는데 한참을 생각하다 잘 안되서 풀이를 찾아보고 너무도 명확한 풀이를 발견해 해당 블로그를 참조하면 될 듯 싶다.https://aerocode.net/

위상 정렬에 대해 익숙하지 않아 문제를 푸는데 애를 많이 먹었다. 위상 정렬에 대해 공부를 진행한 뒤 다시 푸니 의외로 쉽게 풀렸다.

그리디 방식으로 풀면 쉽게 풀 수 있다. 테이플의 길이 양옆으로 0.5씩 즉 테이프의 길이가 각 구멍 사이의 길이보다 1만큼만 더 크면 모두 막을 수 있기 때문에 각 구멍 간 길이를 비교하며 테이프의 길이와 같거나 클때 마다 테이프를 하나씩 더 쓰면 된다.

시간제한이 0.1초로 매우 짧아 자료구조를 적절히 활용해야 하는 문제이다. 단순하게 생각해서 중간값만 계속 계산해내면 되니 heapq를 2개 만들어 활용하면 된다.즉, 계속해서 중간값보다 작은 값을 저장하는 큐 하나와 그 반대되는 경우의 큐 하나를 만들어 저장하면 작은

파이썬의 heapq모듈을 사용하면 쉽게 풀 수 있는 문제.

스택을 활용하는 문제이다. 괄호의 종류는 2개이므로 하나하나 검사해가며 풀면 된다. 이때 곱하기가 있으므로 (가 나오면 2를 해주고 \[가 나오면 3을 해준다. 하나씩 스택에 넣어가며 검사하고 검사 중 짝이 되지 않는 경우는 0으로 만든뒤 반복문을 탈출하면 된다.짝이

풀이를 참고하였다 다음의 블로그에 자세히 설명되어 있으니 참고https://hongcoding.tistory.com/44

각 작업들은 순서대로 배포되어야 한다는 조건이 있으므로 생각보다 간단하게 풀 수 있다. 남은 작업량을 계산해주고 speed로 나눈 뒤 소수점이 생기면 무조건 올림하여 작업일을 구한다. 최초의 작업일을 설정해주고 다음의 작업일들을 계산하면서 기존 작업일보다 작거나 같은

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다