알고리즘_문제풀기

문제 링크문제에서 수열을 만들 수 있다고 주어져있어서, 각 숫자를 초항으로 해서 만들 수 있는 숫자들을 전부 제외해주는 방식으로 문제를 풀었다.

문제링크이전에 k만큼 이동했다면 k-1,k,k+1로 이동할 수 있다는 조건에서 수열의 합 공식을 이용하기로 결정했다. 행성에 도착하기 위해서 이동거리를 줄여하는 점이 어디인지를 먼저 생각했다. 전체 거리의 제곱근 sqrt(거리)만큼까지는 이동하는 거리를 점점 증가시켜주

문제 링크코드를 작성하기 전에 제일 먼저 주어진 요구사항을 파악했습니다. 문제에 적힌 조건대로만 풀어주면 되는 문제여서 그대로 구현하자고 생각했습니다.앞자리 숫자를 front, 뒷자리 숫자를 back이라 두고 연산을 시행한 횟수를 count에 담기로 했습니다.

문제 링크그림 1. H = 6 이고 W = 12 인 H × W 호텔을 간략하게 나타낸 그림문제의 조건을 보면 손님들은 걸어서 가장 짧은 거리에 있는 방을 선호한다. 즉, 1호에 해당하는 방들이 다 배정된 다음에 2호에 해당하는 방들이 배정되며, 방은 1층부터 꼭대기층

문제 링크중학교 때 배운 원과 원 사이의 위치 관계를 이용해서 풀면 되겠다고 생각했다.출처 : https://mathbang.net/101출처 : https://mathbang.net/101정말 간단한 수학에대한 구현이여서 막히거나 고민없이 구현했다.

수 정렬하기2맨 처음에는 array.sort()를 이용해서 해결을 했었다.근데 직접 구현을 해보는 것도 좋을 것 같아서 merge sort를 이용해서 구현을 해보기로 했다.merge sort를 고른 이유는 여러가지 정렬 알고리즘 중에서 퀵정렬과 병합정렬이 빠른데, 퀵정

BOJ10773제로0을 부른 경우에 가장 최근에 쓴 수를 지운다는 문장에서 스택을 사용하면 되겠다는 생각을 했다.차례대로 입력을 받으면서 0인 경우에 stack에서 pop하고 0이 아닌 경우에 stack에 push했다.입력이 끝나면 내장함수인 sum을 이용해서 총합을

오큰수N개의 데이터에대해서 순서대로 하나씩 오큰수를 찾는 방식을 사용했다. 정답을 저장할 ans_array를 -1로 초기화해서 오큰수가 없는 경우에는 별도의 처리없이 -1을 출력할 수 있게했다.stack에는 수열의 index를 저장한다. stack을 사용한 이유는 오른

숫자 카드 2가지고 있는 카드의 숫자를 key로 하고 카드의 개수를 value로하는 사전 자료형을 이용해서 문제를 해결했다. 그 이유는 list보다 사전 자료형이 검색이 더 빠르기 때문이다. 즉, 몇 개 가지고 있는지 알아보고싶은 숫자카드를 정렬하는 것보다는 사전 자료

랜선 자르기자를 수 있는 최대 길이를 찾아야해서 완전 탐색을 해보려했다.가장 작은 값부터 가장 큰 값까지 길이를 하나씩 증가시키는 알고리즘을 가장 먼저 떠올렸고, 그 연산을 더 빠르게 할 수 있는 방법을 생각하면서 binary search를 이용하기로 결정했다.whil

DFS와 BFSDFS는 스택 BFS는 큐를 이용해서 풀기로 결정했다.각 그래프는 빠른 조회를 위해서 딕셔너리를 이용해서 저장했다.DFS와 BFS가 처음에는 이해가 어려웠는데 아래의 절차대로 생각을 하면서 문제를 푸니까 금방 풀렸다.방문할 노드를 큐/스택에서 꺼낸다.vi

단지 번호 붙이기지도에 있는 모든 점들을 시작점으로 하면서 각 점들에서 dfs를 해보자는 생각을 했다.반복문말고 recursion을 이용해서 dfs를 구현해보기로 결정했다.재귀의 스택 깊이가 너무 깊어지면 안되니까 sys.setrecursionlimit를 걸어줘서 해결

숨바꼭질bfs를 이용해서 문제를 풀기로 결정했다. 완전 탐색을 이용해서 전부 구해보면서 답을 찾는 방식을 사용했다.현 위치에서 -1, +1, \*2 한 위치를 다 보는 것이기 때문에, 각 노드마다 자식을 3개로 가지는 트리 구조를 생각했다.이전 단계에서 다음 단계로 넘

파도반 수열문제를 읽으면서 규칙에 따라서 수열을 만들 수 있다는 생각을 했다.파도반 수열 예시그림을 보니 7번째 삼각형부터는 i번째 삼각형의 한 변의 길이는 i-1번째 삼각형과 i-5번째 삼각형의 한 변의 길이의 합과 같다는 것을 발견했다. 6번째 삼각형까지는 문제에서

RGB 거리가능한 모든 경우를 해보는데, 이전에 계산해놨던 것을 이용하는 메모이제이션을 이용해서 풀면 쉬운 문제였다.min_price라는 배열을 만들고 각 인덱스별로 색깔을 정했다.min_pricei - 이번 집을 빨간색으로 칠할 경우 최소 비용을 저장min_price

문제링크 풀이 전 계획 및 생각 연속된 세 개의 계단을 모두 밟아서는 안된다는 조건과 한 번에 한 계단 또는 두 계단씩 오를 수 있다는 조건에서 점화식을 만들 수 있었다. dp배열에는 i-1번째(인덱스가 0부터 시작)을 밟았을 때, 얻을 수 있는 가장 큰 점수를 저장하

포도주 시식연속으로 놓여 있는 3잔을 모두 마실 수 없는 조건이 중요하다고 생각했다.k번째의 포도주를 마실지 말지를 고려할 때 위의 조건을 감안했을 때 아래의 3가지를 고려하고 그 중 가장 큰 값을 만드는 경우를 선택하면 된다는 생각을 했다.1\. k-2번째 포도주까지

연속합처음에는 음수와 양수가 바뀌는 점을 기준으로 부분합을 구하는 방식과 dp를 이용하는 방법 2가지를 생각했었다.음수와 양수가 바뀌는 점을 기준으로 부분합을 구하는 방식은 '1 2 3 -10 1000' 과 같은 케이스를 처리가 불가능하다는 것을 확인하고 바로 dp를

AC배열을 deque를 이용해서 생성한 다음명령어를 하나씩 수행하면서 R가 나오면 삭제할 위치를 조절해주면서 뒤집지않고도 뒤집은 효과를 낼 수 있게했다.그리고 D가 나오면 현재 단계에서 삭제할 위치에서 값을 pop해서 삭제했다.딱히 없었다.O(N)인 것을 O(1)로 해

나무 자르기left를 0, right를 나무의 최대 길이로 설정하고 자르는 길이를 이분 탐색으로 찾을 생각을 했다.잘린 나무들의 길이의 합이 m보다 크다면 톱날의 높이를 지금보다 높일 수 있다는 의미이므로 이분탐색을 더 진행했다.잘린 나무들의 길이의 합이 m보다 작은

카드dictionary 자료형에 저장하면서 몇 장씩 가지고있는지를 count했다.그리고 난 후에 dictionary의 key의 value들을 하나씩 탐색하면서, 가장 많은 장수의 카드를 찾고, 카드의 장수가 같은 경우에는 숫자가 작은 카드를 선택했다.실제 코딩테스트에서

텀 프로젝트문제를 읽으면서 방향 그래프 구조가 그려져서 이를 활용해서 문제를 풀어야겠다는 생각을 했다.1번부터 n번까지의 학생이 있으면, 1번 학생부터 쭉 확인하면서 진행했다.문제에서 나온 예시로 설명을하면1->324->7->65이런 식으로 한 번 시작해서 새롭게 지명

동전 20원부터 시작해서 메모이제이션을 이용해서 문제를 풀기로 결정했다.문제 조건을 보면 동전의 가치가 목표 가격보다 크게 들어올 수 있고, 같은 가치의 동전이 여러 번 주어질 수 있기 때문에, set 자료형을 이용했고, 목표 가격 k보다 작거나 같은 가치를 가지는 동

개발하는 언어는 Java인데, 코딩테스트 볼 때 주로 사용하는 언어가 Java가 아니라 Python이여서 Java코테를 위한 벼락치기 레퍼런스를 만들어봤습니다.Javaimport java.util.\*;Array길이 고정Listadd, get, size, contain

문제링크 프로그래머스-코딩테스트연습-DP-도둑질 풀이 전 계획 및 생각 n 이 3보다 크니까 k번째 집까지 털었을 때 얻는 수익의 최댓값 = max(k-2번째집까지 턴 수익+k번째 집에 있는 돈,k-1번째 집까지 턴 수익) 의 점화식을 생각해냈다. 인접한 두 집은