본문 바로가기
728x90

프로그래밍18

[WEEK01] 8/15 TIL_힙 정렬 [WEEK01] 8/15 TIL_힙 정렬 선택 정렬을 응용한 알고리즘인 힙 정렬을 알아보겠다. 힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다. 힙은 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전 이진트리이다. 선택 정렬 먼저 힙 정렬에 알아보기 전에 선택 정렬을 알아보자. 선택 정렬은 '가장 작은 원소부터 정렬하는 방법'이다. 힙 정렬 - 특성 힙(heap) 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리이다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 힙(heap)은 쌓아 놓음을 의미한다. 트리의 가장 윗부분에 위치한 노드를 루트(root)라고 하고 가장 하래에 위치한 노드를 리프.. 2021. 8. 15.
[백준_2470] 중, 이분 탐색, 두 용액 [백준_2470] 중, 이분 탐색, 두 용액 산성 용액과 알칼리성 용액은 각각 양수와 음수의 특성값을 가지고 있다. 두 용액을 섞어 0에 가깝게 만들려고 할 때, 용매 각각의 특성값을 출력하는 문제이다. 이 문제는 처음에도 그렇고 풀고 나서도 그렇고 이분 탐색인지 직관적으로 와닿지 않는다는 게 어려웠다. 처음에 '이전의 start와 end의 합'과 'start index +1', 'end index -1'일 때 각각과 비교해 차이가 더 작은 방향으로 움직여야 한다고 생각했다. 그런데 이렇게 했을 때 문제는 [-95, -4, 3, 100]과 같은 경우 답이 -95, 100으로 출력된다는 점이다. 문제를 푸는 핵심 포인트는 정렬 후 양쪽에서 0의 방향으로 진행하는 부분(이진 탐색) 합이 양수인지 음수인지에 .. 2021. 8. 13.
[백준_2110] 중, 이분 탐색, 공유기 설치 생각 포인트 가장 인접한 두 공유기 사이의 최대 거리를 구해야 하므로 N개의 집의 양 끝에는 공유기가 무조건 설치된다. 그 다음 공유기 설치 위치는 좌표적으로 1번째와 N번째 공유기 중간에 가장 가까운 곳에 위치해야 한다. (순서상 중간이 아니다) 이 부분이 이진 탐색과 연결이 된다. 그럼 중간 좌표와 가장 주변 집의 좌표들 차이의 최솟값을 구해 최소가 되는 지점의 index에 공유기를 설치한다. 그 다음 공유기는 방금 설치한 공유기를 기준으로 1번째와 N번째 공유기 위치와의 거리 중 긴 곳 영역에 설치된다. 이후 반복. 이란 생각으로 풀었는데, 완전 오답 풀이였다.... 일단 이 방식은 딱 중간 가까운 공유기를 설치하기 때문에 공유기 개수가 짝수일 경우에는 오답이다.. 정답 코드를 작성하기 위한 핵심은.. 2021. 8. 13.
[백준_2805] 하, 이분 탐색, 수 찾기 [백준_2805] 하, 이분 탐색, 수 찾기 이분 탐색(Binary Search) 절단기의 높이를 차례대로 높이는 알고리즘으로는 시간 초과가 발생한다. 이 때 사용할 수 있는게 Binary Search(이분 탐색 or 이진 탐색)을 이용해야 한다. 이진 탐색이란 찾고자 하는 target 값을 오름 차순으로 정렬된 list에서, target값과 list의 중간값 비교를 통해 진행된다. 만약 중간값보다 target이 크면 검색 범위를 중간값 이상의 범위에서 다시 찾기 시작한다. 이 때 중간값은 하기와 같은 새로운 중간값을 이용한다. 첫 번 째 코드 import sys input = sys.stdin.readline from typing import Any, Sequence def bin_search(woo.. 2021. 8. 12.
[백준_8958] 하, 기초(배열), OX퀴즈 [백준_8958] 하, 기초(배열), OX퀴즈 Q) "OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수는 3이 된다. "OOXXOXXOOO"의 점수는 1+2+0+0+1+0+0+1+2+3 = 10점이다. OX퀴즈의 결과가 주어졌을 때, 점수를 구하는 프로그램을 작성하시오. 첫 번 째 코드 처음에는 문제를 잘못 이해했다. 잘 읽고 이해하자.. 두 번 째 코드 if 조건문을 이용해 O, X 판별 + N 정수까지의 합 'ssum 함수'를 정의, 이용하여 풀었다. 마지막에 좀 헷갈렸던 게 OXOOOXOO 로 입력했을 때 조건문 루프에서 마지막 OO에서.. 2021. 8. 7.
[SW사관학교 정글] 새로운 시작 퇴사 21.07.31 1년 3개월 동안 잘 다니던 직장을 회사를 뒤로하고 결국 퇴사했다. 좋은 문화를 가진 유망한 외국계 회사라 인정 받으며 열심히 성장한다면 다양한 커리어로 발전시킬 수 있는 좋은 회사였지만, 제조업이라는 한계에 답답했다. 연차와 나이에 따라 진급, 연봉이 어느정도 정해져 있다는 사실이 불만이었다. 물론 대부분의 직장인이 그러하겠지만.. 회사 타운홀 때 학교 선배가 사장으로 강연하고 있는 모습을 보며 어쩌면 나도 사장이 될 수 있지 않을까하는 생각에 잠깐 자극을 받은 것은 사실이지만, 곱씹어 볼수록 도저히 나의 길 같진 않아 보였다. 직장인으로 정년퇴직까지 평생 일하는 '나'는 상상하기 힘들었다. 너무 답답한 느낌, 인생이 아깝다는 느낌을 지울 수 없었다. 잘 하는 만큼 인정받는 일을 .. 2021. 8. 2.
728x90

티스토리툴바