알고리즘 스터디
[백준] 준비운동 Part1. 튼튼한 기본기1
https://covenant.tistory.com/224 코딩테스트 대비를 위한 백준 문제 추천 코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고 covenant.tistory.com 원래 풀던 프로그래머스 연습 kit가 끝나서 백준으로 넘어가기로 했다. 위 글을 참고하여 순서대로 쭉 풀기로 결정했다. 이번 주는 준비운동part의 브론즈 문제만 풀기로 해서 쉬운 편이다. 1. 약수구하기 https://www.acmicpc.net/problem/2501 def f(a,b): n = 1 cnt = 0 while a >= n: if a %..
[프로그래머스] 그래프 3. 방의 개수
문제 원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다. ex) 1일때는 오른쪽 위로 이동 그림을 그릴 때, 사방이 막히면 방하나로 샙니다. 이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요. 제한사항 배열 arrows의 크기는 1 이상 100,000 이하 입니다. arrows의 원소는 0 이상 7 이하 입니다. 방은 다른 방으로 둘러 싸여질 수 있습니다. 입출력 예 arrowsreturn [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 입출력 예 설명 (0,0) 부터 시작해서 6(왼쪽) 으로 3번 이동합니다. 그 이후 주어진 arrow..
[프로그래머스] 이분탐색 2. 징검다리
문제 https://programmers.co.kr/learn/courses/30/lessons/43236# 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 풀이 이분탐색이라고 카테고리가 주어지지 않았다면 몰랐을 것 같다. 어떤 값을 이분탐색할지 고민해봤다. 선형적인값을 선택해야 하기 때문이다. 리턴값(최소값의 최대값)을 선택하려했는데 검증방법이 딱히 떠오르지 않아 이게 맞나? 고민하다 (https://deok2kim.tistory.com/122) 이분이 리턴값을 기준으로 했다는 것을 보고 좀 더..
[프로그래머스] DFS/BFS 4. 여행경로
문제 https://programmers.co.kr/learn/courses/30/parts/12421 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 카카오 문제를 풀다보니, 구현력을 요구하는 문제가 생각보다 많았다. 내가 생각하기에 깔끔한 풀이가 아니더라도 그걸 끝까지 구현해 내는 것이 관건인 문제들이 많았다. DFS/BFS 카테고리에 있었지만 DFS/BFS 의 풀이는 생각나지 않았고 다른 풀이가 떠올랐는데, 정답이 아닐 것 같다고 생각했지만 일단 구현해보기로 했다. 처음에는 단순하게 알파벳순으로 정렬하여 출발지점에서 도착할 수 있는 곳들 중 알파..
[프로그래머스] 탐욕법 6. 단속 카메라
문제 https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이 들어온 지점으로 정렬 나간 지점으로 정렬 나간 지점을 기준으로 반복문: 나간 지점 전에 들어온 지점들 방문처리 count += 1 들어온 지점 모두 방문했으면 반복문 탈출 근데 뭔가 짜다보니까 visited 안만들어도 되겠다는 생각이 들어서 그냥 해봤다. def solution(routes): answer = 0 start = [] end = [] for r in routes: start.append(r[0]) end.append(r[1]) start.so..
[프로그래머스] 힙 3. 이중우선순위큐
문제 https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 풀이 힙 카테고리에 있어서 힙으로 만들어 풀어야겠다고 생각했다. 힙은 최소, 최대 힙 중 하나로 만들어져야 하는데 문제에서는 최대와 최소를 모두 삭제할 수 있어야 했다. 그래서 최대 힙, 최소 힙 총 2개를 만들고 만약 최대값 삭제 시 최대 힙의 값을 최소 힙에서 검색해서 삭제하는 방식으로 풀어야하나? 싶었는데 로직이 깔끔하지 못한 느낌이고 비효율적일 것 같았다. 이런저런 고민을 해보다가 그냥 힙 버리고 냅다 풀어보기로 했다. def solution(operations): q = [] for o in operations: op = o..
[프로그래머스] 깊이/너비 우선 탐색 3. 단어 변환
문제 https://programmers.co.kr/learn/courses/30/lessons/43163?language=python3 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 풀이 처음엔 dfs나 bfs나 상관 없겠거니 싶었는데 dfs로하면 hit -> hat 대신 hit -> jit -> jat -> hat 같이 최소 단계가 아닌 개수를 반환하게 되어 bfs로 변환했다. 반복문을 돌며 begin에서 1개만 바꿔 만들 수 있는 단어를 스택에 넣음 몇번째 단..
[프로그래머스] 동적계획법 3. 등굣길
문제 https://programmers.co.kr/learn/courses/30/lessons/42898# 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 전체를 -1로 초기화 puddles 를 0으로 만든다. 첫번째 행부터 순회하며 각 경우의 수를 저장한다. def solution(m, n, puddles): grid = [[-1] * m for _ in range(n)] if m > 0: # (1,0) (0,1) 초기화 grid[1][0] = 1 if n > 0: grid[0][1] = ..