본문 바로가기

알고리즘10

알고리즘 7일차 지난 주에서 못풀엇던 문제들은 다시 풀었음. 현재 진행하는 문제들 경우 못 쫒아가고 있어서 차근차근 풀고 있음. 11399_0314.py https://www.acmicpc.net/problem/11399 N = int(input()) P = list(map(int, input().split())) P.sort() total_time = 0 accumulate_time = 0 for time in P: accumulate_time += time total_time += accumulate_time print("total_time", total_time) print(total_time) 2606_0314.py(DFS) https://www.acmicpc.net/problem/2606 N = int(inpu.. 2024. 3. 14.
알고리즘 6일차 아래의 문제를 풀다가 https://school.programmers.co.kr/learn/courses/30/lessons/42840 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이는 다음과 같다. answers = [1, 3, 2, 4, 2] def solution(answers): one = [1, 2, 3, 4, 5] two = [2, 1, 2, 3, 2, 4, 2, 5] three = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] score = [0, 0, 0] winner = [0, 0, 0] for index, i in enume.. 2024. 3. 13.
Queue,DEQ,원형큐 Queue 특징 - 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 뺀다. - 이와 같은 속성에 따라, 가장 먼저 들어간 자료를 가장 먼저 빼게 된다. - 이 속성을 선입선출(FIFO , First In First Out) 이라고 부른다. - 기본적인 자료구조이기 때문에 거의 모든 언어의 표준 라이브러리에서 구현체 제공 ex) 놀이공원이나 음식점에서의 줄 등 개념 데이터를 삽입하는 곳을 Rear(후방), 데이터를 추출하는 곳을 Front(전방)이라고 합니다. 특징 때문에 리스트로 작성하여 만들시 아래와 같은 문제가 생긴다. 리스트의 경우 인덱스 값이 정해져 있다. index 1 2 3 4 5 6 7 value 5 7 6 4 2 9 7 여기서 5가 사라지면 인덱스 값도 앞으로 당겨줘야한다. DEQ (Dou.. 2024. 3. 12.
병합정렬 일단 반으로 나누고 나중에 합쳐서 정렬하면 어떨까? 리스트를 반으로 나눕니다. 왼쪽 부분과 오른쪽 부분을 각각 병합 정렬을 사용하여 정렬합니다. 정렬된 왼쪽 부분과 오른쪽 부분을 병합합니다. 예시에는 시작에서 리스트에서 전부 나누었습니다. 1번에서는 7,6을 비교하여 정렬을 했습니다. 2번에서는 6,7 과 5,8를 비교하여 정렬했습니다. 3번에서는 5,6,7,8과 1,3,5,9비교 하여 정렬했습니다. 2024. 3. 11.
삽입정렬 숫자를 '적절한 위치'에 삽입해보면 어떨까? 다른 정렬들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 필요할 떄만 위치를 변경합니다. 위의 글들을 보면 ‘적절한 위치’,’필요할 때’ 같은 글 때문에 제대로 이해가 안됩니다. 예시를 보면 이해에 도움이 됩니다. 맨 처음부터 시작하여 각 원소를 차례대로 확인합니다. 현재 확인하는 원소가 이미 정렬된 리스트의 마지막 원소보다 크면, 삽입할 위치를 찾습니다. 삽입할 위치를 찾으면, 그 위치부터 마지막 원소까지 한 칸씩 뒤로 이동시킵니다. 빈 공간에 현재 확인하는 원소를 삽입합니다. 1. “1”은 가장 앞에 있기 때문에 삽입할 공간이 없습니다. 2. “10”은 1과 비교해서 a,b 중 ‘적절한 위치’에 삽입하면 됩니다. (b에 삽입합니다.) 3. “5”는 1과.. 2024. 3. 11.
버블정렬 옆에 있는 값과 비교해서 더 적은 값을 앞으로 보내면 어떨까? 1. 맨 처음부터 인접한 두 원소를 비교합니다. 2. 앞쪽 원소가 뒤쪽 원소보다 크면 두 원소를 교환합니다. 3. 마지막 원소까지 반복하여 1, 2 단계를 수행합니다. 4. 마지막 반복에서는 정렬이 되어있기 때문에 변화가 없습니다. 위의 이미지를 확인하면 마지막 ‘40’은 정렬되어있기 때문에 교환이 일어나지 않는다. 이보다 많은 횟수로 비교하는 정렬하는것이 있을까?라는 생각이 들고 비효율적이라고 생각이 든다. 2024. 3. 11.

티스토리툴바