알고리즘

[프로그래머스 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 ..

[프로그래머스 Lv.2] 교점에 별 만들기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87377 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이레벨 2의 문제답게 크게 어렵지 않게 풀 수 있는 문제라고 생각한다. 아래 사진의 두 일차방정식의 교점을 구하는 공식을 알고 있기 때문에, 문제에 이를 적용함으로써 교점을 구하고 이를 사용하여 교점의 위치에 *을 출력하면 해결이 된다.def solution(line): x_min = y_min = float('inf') # 그려야할 직사각형의 시작 위치를 알기 위한 최소값 x..

[프로그래머스 Lv.3] 풍선 터트리기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/68646 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이dp에서 사용하는 메모이제이션을 통해 최솟값을 저장하는 방법으로 문제를 풀이하였다. 이 문제를 풀이하긴 위해서 풍선을 마지막까지 남길 수 있는 조건이 무엇인가를 알아야 한다.문제의 조건을 간단하게 요약하면 남기려고 하는 풍선의 좌우에 위치한 남은 풍선 중 하나라도 크기만 하면 된다는 것이다.그렇기에 남기려고 하는 풍선의 좌측에 남은 풍선들의 최솟값이나 우측에 남은 풍선들의 최솟값 중 하..