알고리즘/알고리즘 문제 풀이

[프로그래머스 Lv.2] 모음사전 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제는 단순히 수학적으로 개수를 계산해 푸는 방법이나 등비수열의 합을 이용해 해당 자리에 어떤 모음이 위치하는지에 맞춰 풀이할 수도 있으나 쉽게 생각하기 어려운 방법이었다.그래서 재귀를 활용하여 실제로 A, E, I, O, U를 사용한 모음사전을 생성하고 이를 전체적으로 순회하면서 일치하는 단어가 나타나는 그 인덱스 + 1을 반환하는 방식으로 문제를 풀이하였다. 물론 이 방법은 앞서..

[프로그래머스 Lv.2] 하노이의 탑 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12946 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이그 유명한 하노이의 탑을 풀기 위한 방법을 순서대로 배열에 넣어 출력하면 되는 문제이다.재귀를 활용해 풀이하면 되는 문제인데, 재귀 문제가 모두 그렇듯이 재귀 과정에서 어떤 연산을 거쳐야 하는지 정의해야 하고, 종료 조건도 정의해야 한다.우선 재귀 과정을 거치면서 어떤 연산을 거쳐야 하는지 고민을 해봐야 한다. 연산에서의 규칙을 찾을 수 있게 "/"로 단계를 분리해서 적어보면 아래와 같..

[프로그래머스 Lv.2] 이진 변환 반복하기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/70129 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이def solution(s): _iter = cnt = 0 # _iter: 이진 변환의 횟수, cnt: 제거된 0의 수 while s != "1": # s가 "1"이 될 때까지 반복 number = 0 # s에 존재하는 1의 갯수 for n in s: # s 전체를 한 글자씩 순회하며 if n == "0": #..

[프로그래머스 Lv.2] 문자열 압축 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이반복되는 패턴을 찾을 것이기 때문에 가장 긴 반복되는 패턴의 길이는 무조건 전체 문자열의 길이의 절반 이하 일 수밖에 없다. 그렇기에 전체 문자열의 길이의 절반부터 길이 1까지 반복하며 반복되는 패턴의 수를 체크하고 압축 시의 길이를 체크하면 된다.def solution(s): length = len(s) # 문자열의 길이 answer = 1001 # 최대 문자열의 길이가 1..

[프로그래머스 Lv.2] 짝지어 제거하기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12973 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이레벨 2 문제임에도 아이디어를 생각하는 것이 상당히 까다로운 문제였다.문자열의 길이가 1000000개이기 때문에 파이썬이 초당 2000만 번의 연산을 한다는 것을 생각하면 O(n^2) 이하의 알고리즘으로 풀어야 한다.그렇기에 O(n)이나 O(nlogn)으로 풀 수 있는 방법을 생각해야 하고, 그 방법으로 스택을 사용하였다.아래의 코드와 같이 진행하면 O(n)의 시간복잡도를 보여 시간 내..

[프로그래머스 Lv.2] 튜플 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이주어진 문자열을 가공하여 배열의 형태로 변환한 후, 이 배열의 각 원소들을 사용하여 가장 많이 튜플 후보군에 나타난 순서를 파악한다. 그리고 최종적으로 그 순서대로 배열에 담아 출력하면 된다.def solution(s): number_dict = {} # 튜플 후보군에 특정 숫자가 몇 번 나타나는지 저장할 딕셔너리 for tuple in s[2 : -2].split("..

[프로그래머스 Lv.2] 행렬의 곱셈 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12949 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이행렬곱을 구현하면 되는 단순한 문제이다. 행렬곱의 경우 아래와 같은 방식으로 계산한다.이런 계산 방식을 코드로 구현하면 된다.def solution(arr1, arr2): answer = [] for m in range(len(arr1)): # 피연산자(arr1)의 각 행 별로 계산 arr = [] for r in range(len(arr2[0..

[프로그래머스 Lv.2] 거리두기 확인하기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제는 BFS로도 풀 수 있으나 배열의 크기가 5 X 5로 상당히 작으며 또한 맨해튼 거리가 2 이내인 경우가 아래의 6가지 경우 밖에 없기에 이 경우만 조건문으로 체크해 주면 더 간단하게 풀이가 될 것이라고 판단하여 BFS를 사용하지 않았다.아래가 사람인 경우두 칸 아래가 사람이며 중간에 파티션이 없는 경우오른쪽 대각선 아래가 사람이며 중간에 파티션이 없는 경우왼쪽 대각선 애라개 ..

[프로그래머스 Lv.2] 삼각 달팽이 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/68645 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이2단계 문제이기에 코드 자체의 구현 난이도는 어렵지 않으나 풀이를 위한 아이디어를 생각하는 것이 난이도에 비해 어려웠다.아이디어는 피라미드 모형으로 되어있는 예시의 배열을 아래처럼 좌측으로 붙여 정렬을 시키는 것이었다.이렇게 좌측으로 정렬함으로써 배열을 채워나가는 로직을 생각하는 것이 훨씬 쉬워진다.배열의 절반인 삼각형을 이루는 칸을 벗어나거나, 배열에 이미 값이 채워진 경우 채워가는 ..

[프로그래머스 Lv.2] 행렬 테두리 회전하기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/77485?language=python3 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이우선 아래와 같이 우측으로 행렬의 테두리를 회전하도록 풀이해 보았다. 하지만 아래 풀이대로 진행하면 시간 초과가 발생한다. rows와 columns가 100이고, queries도 10000 이하이므로 풀이 로직 상에서는 시간 초과가 발생하지 않을 것이라고 생각하였으나 시간 초과가 발생하여 상당히 당황스러웠었다.시간 초과 발생 코드import copydef ..