알고리즘 문제풀이
1.[알고리즘 문제풀이] 프로그래머스 - 체육복
TIL (2022.01.29) ➕ 오늘 푼 문제 프로그래머스 - 체육복 ➕ Java 코드 Java에서의 집합 연산과 Python에서의 집합 연산이 달라서 애를 먹었다. 이 알고리즘에서 간과하기 쉬운 부분은 리스트가 정렬되어 있어야 한다는 점이다. 정렬된 상태에서
2.[알고리즘 문제풀이] 프로그래머스 - 조이스틱
프로그래머스 - 조이스틱상하 이동A ~ N : 다음 문자로 이동 (ch - ‘A’)M ~ Z : 이전 문자로 이동 ( ’Z’ - ch + 1)A에서 Z로 이동하는 횟수 +1을 해줘야 한다.min( ch - ‘A’, ’Z’ - ch + 1) 으로 계산할 수도 있다.좌우
3.[알고리즘 문제풀이] 프로그래머스 - 큰 수 만들기
TIL (2022.02.04) ➕ 오늘 푼 문제 프로그래머스 - 큰 수 만들기 ➕ 아이디어 단순 구현 - O($n^2$) > 이 방법을 사용하면 Python에서 통과하지 못한다. 그리고 $n^2$은 효율성 측면에서도 좋지 못하다. k개를 빼는 문제이지만 le
4.[알고리즘 문제풀이] 프로그래머스 - 구명보트
프로그래머스 - 구명보트핵심 아이디어는 리스트를 정렬해서 가장 큰 값과 가장 작은 값을 같이 태우는 것이다.가장 큰 값의 경우, 가장 작은 값이랑 함께 탈 수 없다면 혼자서 보트를 타야 한다.이 경우 혼자서 보트를 타고 다음 큰 값과 가장 작은 값을 함께 태울 수 있는
5.[알고리즘 문제풀이] 프로그래머스 - 섬 연결하기
프로그래머스 - 섬 연결하기가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘최소 비용 신장 트리에서는 사이클이 발생하면 안됩니다. 애초에 모든 노드를 이어 붙이기만 하면 되는데 사이클이 발생할 이유가 없
6.[알고리즘 문제풀이] 프로그래머스 - 단속카메라
프로그래머스 - 단속카메라기존에 적어놨던 포스팅이 날라가서 나중에 다시 정리하겠습니다ㅠㅠ
7.[알고리즘 문제풀이] 프로그래머스 - K번째 수
프로그래머스 - K번째 수지문 그대로 구현하면 되는 문제이다! 배열을 (i-1, j) 범위로 자른다.자른 배열을 오름차순으로 정렬한다.k번째 수를 결과 리스트에 추가한다.파이썬으로는 너무 쉽게 구현되는 문제라 넘어가도록 하겠다. 자바에는 문자열을 자르고 복사하는 함수가
8.[알고리즘 문제풀이] 프로그래머스 - H-Index
프로그래머스 - H-Index인용 횟수에 따라 citations 를 오름차순으로 정렬한다.반복문을 돌며 해당 논문의 인용 횟수(quotation_count)와 그 이상 인용된 논문의 개수(thesis_count)를 구한다.quotation_count : 현재 citat
9.[알고리즘 문제풀이] 프로그래머스 - 모의고사
프로그래머스 - 모의고사각 학생들의 문제를 찍는 최소 패턴을 찾아, 그 패턴을 계속 반복한다.여기서는 최소 패턴의 길이의 나머지 값을 해당 문제에서 찍은 번호의 인덱스로 삼는다.각 학생별로 점수를 구한다.최대 점수를 가지는 학생들을 오름차순으로 정렬하여 반환한다.아이디
10.[알고리즘 문제풀이] 프로그래머스 - 소수 찾기
프로그래머스 - 소수 찾기최대 범위 (1000000 미만)까지의 소수 목록을 구한다 (→ 아리스토테네스의 체)아니면 numbers의 길이 만큼 소수 목록을 구해도 된다.numbers로 만들 수 있는 숫자 목록을 구한다. (순열)⭐ 순열 구현 방법현재까지 고른 숫자들을
11.[알고리즘 문제풀이] 프로그래머스 - 카펫
프로그래머스 - 카펫전체 타일 수를 구한다.(total = brown + yellow)가로(width)는 세로(height)보다 크거나 같으므로, 가로와 세로는 다음과 같이 나타낼 수 있다.height = 1부터 total / 2까지의 수들width = total
12.[알고리즘 문제풀이] 프로그래머스 - 완주하지 못한 선수
프로그래머스 - 완주하지 못한 선수참가자들을 탐색하며 key = 이름, value = 인원수 로 갖는 해시를 만든다완주자들을 탐색하며 해시의 key 목록에 있다면 인원수를 줄인다. 인원수가 0이라면 해시에서 제거한다.문제 조건에 따라서 미완주자는 한명이다. 따라서 해시
13.[알고리즘 문제풀이] 프로그래머스 - 전화번호 목록
프로그래머스 - 전화번호 목록전화번호 목록을 문자순으로 정렬한다.문자순으로 정렬하는 이유는 바로 옆에 있는 숫자하고만 비교하기 위해서이다.만약에 접두어가 되는 관계가 있다면, 그 둘은 앞부분이 같기 때문에 정렬했을 때 바로 옆에 올 수 밖에 없다.각자 바로 옆에 있는
14.[알고리즘 문제풀이] 프로그래머스 - 위장
프로그래머스 - 위장의상의 종류를 key로, 의상 이름을 value로 둔 해시를 만든다.value는 해시 이름 대신 해시 개수로 둬도 좋다.모든 key를 탐색하며, 해당 값에서 선택할 수 있는 모든 경우의 수를 누적하여 곱해준다.각 key 마다는 value 중 한 개를
15.[알고리즘 문제풀이] 프로그래머스 - 베스트앨범
프로그래머스 - 베스트앨범다음과 같은 해시를 생성한다.key = 장르, value = 수록된 곡들의 목록(고유번호) → playlistkey = 장르, value = 수록된 곡들의 재생 횟수 합 -> playcount재생 횟수의 내림차순으로 장르를 정렬한다.전체 장르를
16.[알고리즘 문제풀이] 프로그래머스 - 기능개발
프로그래머스 - 기능개발각 기능별로 소요일을 큐에 담는다.큐에서 소요일을 하나씩 빼면서이전 소요일(before)이 현재 소요일(now)보다 크거나 같다면, 이전 기능이 아직 끝나지 않았으므로 기다렸다가 같이 배포같이 배포하는 기능(count) 개수 증가적다면 따로 새로
17.[알고리즘 문제풀이] 프로그래머스 - 프린터
프로그래머스 - 프린터큐에 프린트 물의 인덱스와 우선순위를 함께 저장한다.큐에 원소가 2개 이상인 동안,큐에서 원소를 뽑는다.남은 큐에서 우선순위가 최대인 값을 뽑는다.최대 우선순위가 현재 원소의 우선순위보다 크다면, 다시 큐에 넣는다.아니라면 인쇄하고(answer +
18.[알고리즘 문제풀이] 프로그래머스 - 다리를 지나는 트럭
TIL (2022.02.23) ➕ 오늘 푼 문제 프로그래머스 - 다리를 지나는 트럭 ➕ 아이디어 > 큐에 트럭을 추가할 수 있다면 트럭 무게를, 추가할 수 없다면 대신 0을 추가하는 과정을 반복한다. 큐에 있는 트럭의 무게 합이 0인 경우 반복을 종료한다. (이
19.[알고리즘 문제풀이] 프로그래머스 - 주식가격
프로그래머스 - 주식가격핵심 아이디어는 스택에 (현재 값을 기준으로) 값이 떨어지지 않은 주식의 인덱스를 저장하는 것이다. 매 반복마다 현재 값보다 큰 주식이 있다면, 즉 가격이 떨어진 주식이 있다면 스택에서 제거하며 정답을 갱신해준다.각 주식이 가질 수 있는 최대 기
20.[알고리즘 문제풀이] 프로그래머스 - 신고 결과 받기
프로그래머스 - 신고 결과 받기report에서 중복을 제거한다.아이디별 신고 받은 횟수를 담는 해시(report_count)를 만든다key: 아이디 / value : 신고 받은 횟수report 를 반복하며, 유저가 신고한 ID가 신고 받은 횟수가 k 번 이상이면 유저
21.[알고리즘 문제풀이] 프로그래머스 - 빛의 경로 사이클
프로그래머스 - 빛의 경로 사이클문제를 이해하기 어려워 지문부터 정리해보자면 다음과 같다.경로 사이클이란?시작점에서 출발한/나간 방향과 동일한 방향으로 시작점에 도착하는/들어오는 경우, 경로 사이클이 형성된다.시작점이 아닌 경우, 같은 지점을 같은 방향으로 들어왔다면
22.[알고리즘 문제풀이] 프로그래머스 - 타겟 넘버
프로그래머스 - 타겟 넘버이 문제의 핵심은 DFS/BFS 유형의 문제라는 것을 알아차리는 것이다.DFS/BFS는 둘 다 탐색 알고리즘이기 때문에, 조건에 맞는 값을 찾는데도 사용할 수 있다.이 문제에서 numbers 의 숫자들은 각각 더하거나 빼는 2가지 선택이 가능하
23.[알고리즘 문제풀이] 프로그래머스 - 피로도
프로그래머스 - 피로도dungeon 함수에서 방문할 수 있는 모든 던전의 경우의 수를 다 따져 최대값을 구한다.k: 현재 피로도now: 남은 던전 목록count: 지금까지 방문한 던전 수재귀 함수(dungeon)의 로직남은 던전 목록을 순회하며 방문 가능한 던전을 뽑는
24.[알고리즘 문제풀이] 프로그래머스 - 전력망을 둘로 나누기
➕ 오늘 푼 문제 프로그래머스 - 전력망을 둘로 나누기 ➕ 아이디어 > 전력망 네트워크를 2차원 배열로 표현하고, BFS로 포함된 송전탑의 개수를 구하면 된다. wires를 순회하며 전력망 네트워크를 2차원 배열로 표현한다. arri = 1 / arrj
25.[알고리즘 문제풀이] Codility - BinaryGap
Codility - BinaryGap이진수로 변환한 숫자에서 가장 긴 연속된 0의 길이를 구하는 문제이다.start 와 end 변수를 통해 양쪽 끝에 있는 1의 위치를 담고 있는 변수이다.start, end 를 -1로 초기화하고, start 가 -1이라면 제일 처음 만
26.[알고리즘 문제풀이] Codility - CyclicRotation
Codility - CyclicRotationA 배열을 K번 회전했을 때 결과를 출력하는 문제이다.주어진 예시로 회전했을 때 결과를 보면 다음과 같다.패턴을 보면 K가 1씩 증가할 때마다 뒤에 있는 숫자가 맨 앞으로 하나씩 오고 있다. 이는 맨 뒤에서 K번째 숫자부터
27.[알고리즘 문제풀이] Codility - OddOccurrencesInArray
Codility - OddOccurrencesInArray배열에서 짝이 안맞는 숫자 값 하나를 반환하는 문제이다. 배열이 크기 때문에 효율적으로 구하는 방법을 알아내는 게 중요하다.배열 A 를 정렬한다. (오름차순/내림차순은 상관 없다.)answer 를 A 의 가장 마
28.[알고리즘 문제풀이] Codility - FrogJmp
Codility - FrogJmpX에서 Y보다 크거나 같은 곳으로 점프하고 싶다. 한번에 D만큼 점프할 수 있다고 했을 때, Y보다 크거나 같은 좌표에 도달할 수 있는 최소 점프 횟수를 구하라.방정식 풀이라고 생각하면, 간단한 수식으로 해결할 수 있다.어렵지 않게 풀