생각하는 아져씨

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 문제를 읽다보면, 구현 같지만 구현과 BFS/DFS 알고리즘이 혼합된 것 같다. 문제 속에서 '최소 몇 단계' 라는 말이 있었기 때문에 BFS로 접근하면 되겠구나 생각이 들었다. BFS는 최단거리가 보장되는 경로를 탐색할 수 있기 때문이다. 그래서 코드 작성하기 전 과정을 적어보면 다음과 같이 풀 수 있다. ''' 최소 단계를 거쳐 begin -> target으로 변환 변환할 때 마다 ..

https://school.programmers.co.kr/learn/courses/30/lessons/70129 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오랜만에 프로그래머스 풀어보기 ✌️ 요즘 알고리즘만 풀었더니 구현 문제를 잘 못푸는 것 같아서 연습 겸 풀어본다. 접근 방법 구현이니까 문제에서 하라는 대로 코드를 구현한다. 이진변환 반복하라고 하니까..반복해본다. 이진변환 함수 생각안나서 직접 함수로 구현했다. 다 풀고 찾아보니 아주 간단한 함수였던 것..! 😂 bin()으로 해결하면 된다. 풀이 def solution(s): ''' 1. x에..

https://school.programmers.co.kr/learn/courses/30/lessons/42884 접근 방법차량의 진출 순서를 기준으로 정렬하고, 앞에서부터 카메라를 설치해간다.그리디 알고리즘을 활용할 수 있다. 예시에서 카메라는 다음과 같이 설치될 수 있다. 하지만 최대한 많은 차가 겹치도록 하기 위해서는 중간 보다는 진출 또는 진입시점에 설치하는게 좋다.풀이에서는 진출 시점에 카메라를 설치했다. 자동차의 진출 시점에 카메라를 설치하는 과정을 살펴보면 다음과 같다. 풀이def solution(routes): routes.sort(key = lambda x: x[1]) # 진출 시점을 기준으로 정렬한다. camera = routes[0][1] # 가장 첫번째 차량의 진출 시점을 카메라 한..

2559번: 수열https://www.acmicpc.net/problem/2559문제 정의어떤 정수의 수열이 주어졌을 때, 연속적인 며칠 동안의 숫자의 합이 가장 큰 값이 무엇인지 알아보는 문제이다. 접근 방법Naive 한 방법온도 리스트를 순회하면서 K만큼 해당하는 부분 리스트의 합을 구한다. → 최대 O(N2)O(N^2)O(N2) 이다.그 합들 중에서 가장 큰 부분 합을 리턴한다. 최대 O(N) 이다.따라서 시간 초과 발생하므로, 누적합을 이용해 효율적으로 풀 수 있다. 누적합을 이용한 방법온도 리스트를 순회하면서 누적합을 구해서 prefix_sum 리스트에 저장한다.K만큼 해당하는 구간 리스트의 합은 누적합의 성질을 이용해서 구할 수 있는데, 예를 들어 (5, 6, 7, 8)의 합을 구하고 싶다면..

10814번: 나이순 정렬https://www.acmicpc.net/problem/10814 문제 정의온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 접근 방법정렬 기준이 나이 → 가입순서 이므로, 나이가 젊은 것부터 해당되는 이름을 출력하면 된다.대신 가입순서도 따져야 하므로, 들어오는 순서 그대로 저장해야 한다. 딕셔너리를 활용해 나이를 key, 이름 리스트를 value로 설정했다.문제 해설들어오는 입력을 key를 나이로, value를 이름 리스트로 설정한다.나이 순으로 출력해야 하므로 딕셔너리의 key 리스트를 정렬하고,그 리스트를 순회하면서 해당되는 ..

1717번: 집합의 표현https://www.acmicpc.net/problem/1717문제 정의초기에 n+1개의 집합 {0}, {1},… {n} 이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. 접근 방법0이면 두 원소를 합하고, 1이면 두 원소가 같은 집합인지 확인하므로, 유니온파인드 자료구조를 활용할 수 있다. 문제 해설집합의 각 원소에 대한 부모 노드를 초기화 한다. 처음에는 각 원소가 부모노드가 된다.입력에 따라 0이면 두 원소를 합한다. 이 때 부모의 노드를 찾아서 작은 쪽의 노드가 큰 쪽의 부모가 되게끔 부모노드를 업데이트 해주면 된다.1이면 두 원소의 부모노드를 찾아서 같다면 YES, 다르다면..