알고리즘

데이터를 특정한 기준에 따라서 순서대로 나열하는 것데이터 가공시 오름차순이나 내림차순 등으로 정렬하여 사용 가능이진탐색 가능선택정렬, 삽입정렬, 퀵정렬, 계수정렬, 기수정렬, 병합정렬 등

문제 설명 > H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

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

문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요.s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다.str은 길이 1 이상인 문자열입니다.문자를 큰것부터 작은순으로내

문제설명 > 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. > **▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽

문제설명 > 개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. (...) 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 이 얇은 바닥을 1x2, 2x1, 2x2 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.1x2, 2x1, 2x2 덮개왼쪽부터 바닥을 채워나간다고

연산 우선순위가 같은 곱셈과 나눗셈 또는 덧셈과 뺄셈만 있는 식에서는 보통 왼쪽에서 오른쪽 순서로 연산을 한다. 하지만 이런 상황에도 연산 순서에 따라 아래와 같이 두 가지 다른 결과가 나올 수 있다.(6 ÷ 2) × 3 = 96 ÷ (2 × 3) = 1만약 곱셈, 나

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “1

문제설명 > 문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오. 부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba,

A×B를 계산하다 지겨워진 형택이는 A×B를 새로운 방법으로 정의하려고 한다. A에서 한 자리를 뽑고 × B에서 임의로 한 자리를 뽑아 곱한다.가능한 모든 조합 (A가 n자리, B가 m자리 수라면 총 가능한 조합은 n×m개)을 더한 수로 정의하려고 한다.예를 들어 12

문제설명 > 방문 판매원 A는 공중 미래 도시에 있다. 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다. 공중 미래 도

문제설명 접근 풀이

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

문제설명 > 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비

선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있다. 학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과이다. A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 한다.

화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재합니다. 가장 왼쪽 위 칸인 0 위치에서 가장 오른쪽 아래 칸인 N-1 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요. 화성 탐사 기계

문제설명 > 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 <= N <= 20,000)개이며, 1 부터 샌다고 하자. 재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있

문제설명 접근 풀이 배운점

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다. 그러나 만약 어떤 두 집

각 자리가 숫자로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.(단, + 보다 x를 먼저 계산하는 일반적인 방식과 달리, 모

프로그래머스 2021 카카오 채용연계형 인턴십 숫자 문자열과 영단어 파이썬 풀이

순열 라이브러리, 백트래킹을 활용한 문제 풀이

프로그래머스 문제 풀이(파이썬)

아래와 같은 모양의 두 개의 차트가 겹쳐있다고 생각하면 쉽다. 두 차트를 각각 A(구간), B(테스트 구간)라고 했을 때, B 차트가 A 차트보다 더 위에 있는 경우를 생각해보자.

다이나믹 프로그래밍(Dynamic Programming)이란 최적의 해를 구하기에는 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제에서, 메모리 공간을 조금 더 사용하여 연산 속도를 비약적으로 증가시키는 방법 중 하나로 동적 계획법이라고도 한다. 참고자료 동적 계획법 코딩테스트, 기초, 다이나믹 프로그래밍, dynamic progra...

서로소 집합(Disjoint Sets)는 공통 원소가 없는 두 집합을 의미한다.서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.

최단경로(Shortest Path)는 가중치 그래프에서 정점u와 정점v를 연결하는 경로 중 가중치의 합이 최소인 경로로 ‘가장 짧은 경로’를 말한다.

한 전화번호가 또 다른 전화번호를 포함하는 경우가 있다면 일관성이 없다고 볼 수 있다.

위상 정렬(Topology Sort)은 정렬 알고리즘의 일종으로, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 정렬 방법이다.

코딩테스트를 시행할 때 도움이 될만한 나만의 팁이 담긴 코드 노트이다. 이 노트에는 코드 작성 중 간과할 만한 부분이나, 꿀팁들이 담겨있다. 파이썬으로 코딩테스트를 보는데, 시험이 바로 다음날인 사람들에게 도움이 되었으면 한다.

프로그래머스에서 알고리즘 고득점 Kit에 포함되지 않는 문제들은 알고리즘 분류가 표시되지 않습니다. 문제들을 풀면서 나름 분류를 해봤습니다. 알고리즘별로 문제 풀이 하시려는 분에게 도움이 되었으면 좋겠네요. 푸는대로 지속적으로 업데이트 할 예정입니다. 🔗그리디 숫자 게임 스마트 물류(소프티어) 🔗BFS/DFS 최단경로 숫자 변환하기 미로 탈출...

재귀는 늘 새롭다. 이 문제의 경우 분할과 정복 느낌으로 접근해봤다. 이때, 항상 조심해야 할 점이 재귀 함수 내에서 기준점이 되는 좌표를 잘 설정해야 한다는 것이다. 🤔접근 우선 nxn 크기의 배열 원소를 모두 ⭐로 채운다. 재귀함수의 기준점 si, sj는 9등분한 정사각형의 시작점이 된다. 제일 바깥의 중첩 반복문은 9등분한 정사각형의 시작점을 방문한...

처음에 이 문제가 실버4라고..? 문제가 생각보다 까다롭다. Counter를 사용해야 겠다고 가장 먼저 떠올렸다야 겠다고 가장 먼저 떠올렸다. 파이썬의 collections 모듈의 Counter를 사용하면 쉽게 풀이가 가능하다. 이 모듈은 딕셔너리의 메서드를 제공하며, most_common() 함수는 개수(키의 개수)가 많은 순서대로 배열로 반환해준다. 자...

처음에 이 문제가 실버4라고..? 문제가 생각보다 까다롭다. Counter를 사용해야 겠다고 가장 먼저 떠올렸다야 겠다고 가장 먼저 떠올렸다. 파이썬의 collections 모듈의 Counter를 사용하면 쉽게 풀이가 가능하다. 이 모듈은 딕셔너리의 메서드를 제공하며, most_common() 함수는 개수(키의 개수)가 많은 순서대로 배열로 반환해준다. 자...

🤔접근 Union-Find를 공부했다면 문제를 보는 순간 해당 방법으로 접근했을 것이다. 왜냐하면 벽을 허무는 순간 각 동방은 같은 집합에 속하기 때문이다. 그러면 가장 먼저 x번 방부터 y번 방을 허물 때, (x, x+1), (x+1, x+2), ... 로 묶어 x와 y의 부모가 다른 경우에만 합집합(union) 연산을 수행하면 된다는 것을 떠올렸을 것...