본문 바로가기
728x90

전체 글115

[백준_11279] 우선순위 큐, 최대 힙 [백준_11279] 우선순위 큐, 최대 힙 최대 힙을 이용해 원하는 값을 출력하는 우선순위 큐 문제를 풀어보았다. 내 코드 - 모듈 없이 do it! 책대로 풀었는데 시간초과가 떳다.... 남들은 더 간단하게 했는지 input()만 sys.stdin.readline()으로 고쳐주면 통과 된다는데 이 방식으론 통과가 안된다. 그래서 옆에 친구한테 물어보니 모듈을 쓰면 된단다 =.=;; 그래도 원리 이해한 거에 의의를 두는 걸로 import sys def heap_sort(a): def down_heap(arr, left, right): # left : 기준, right가 n-1 가장 마지막 leaf tmp = arr[left] parent = left #left 뺴고 다 heap 구조 가정 while pa.. 2021. 8. 16.
[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.
[SW사관학교 정글] WEEK00_Project_로그인 방식 [SW사관학교 정글] WEEK00_Project_로그인 방식 로그인을 위한 기술은 세션, 쿠키, JWT를 위한 방법이 있다. 기본적으로 HTTP(HyperText Transfer Protocol) 통신의 특징은 접속 후 접속을 끊는 Connectionless(비 연결)와 상태정보를 보관하지 않는 Stateless(비 상태유지)이다. 그러므로 HTTP 요청시 이전 요청에 대한 정보와 무관하다. 그래서 로그인 기능을 사용하기 위해서는 요청 주체에 대한 '인증'이 필요하다. 이 인증을 통해 사용자 A와 B에 대하여 서버에서 클라이언트에 다른 화면을 보낸다. 1. 계정 정보를 요청 헤더에 넣는 방식 장점 : 빠르게 인증 테스트 시도 가능 단점 : 계정 정보에 대한 접근이 매우 쉬워 보안 매우 취약. 2. Ses.. 2021. 8. 9.
[SW사관학교 정글] 찬찬히 나를 돌아보는 시간 [SW사관학교 정글] 찬찬히 나를 돌아보는 시간 지나온 과거에 대한 성찰, 5개월 동안 내가 어떤 것을 얻어가고 싶은지, 어떤 자세로 임하고 싶은지, 정글2기가 끝난 후 나의 모습은 어땠으면 좋겠는지 생각해보기 희망 초, 중, 고, 재수 시절을 떠올려 보면 주어진 것을 참 열심히 하는 아이였던 것 같다. 항상 더 좋은 교육, 더 좋은 기회, 더 좋은 공부법을 생각하며 치열하게 고민하고 한편으로는 불만도 품었지만, 정작 발을 내딛고 있는 현실에서는 별말없이 성실히 해냈다. 미래에는 어떠할 것이라는 기대감을 나타내는 '희망' 이라는 단어를 좋아했다. 그 시절에는 대학만 들어가면 모든 걸 보상받고 행복할 것이라는 희망을 갖고 하루하루를 즐겼던 것 같다. 이러한 과정에서 내가 스스로 기획하고 학습하는 습관이 생.. 2021. 8. 8.
[백준_2908] 하, 상수 [백준_2908] 하, 상수 Q) 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 개를 칠판에 써주었다. 그 다음에 크기가 큰 수를 말해보라고 했다. 상수는 수를 다른 사람과 다르게 거꾸로 읽는다. 예를 들어, 734와 893을 칠판에 적었다면, 상수는 이 수를 437과 398로 읽는다. 따라서, 상수는 두 수중 큰 수인 437을 큰 수라고 말할 것이다. 두 수가 주어졌을 때, 상수의 대답을 출력하는 프로그램을 작성하시오. 함수를 썼으면 좀 편했을텐데... 첫 번 째 코드 내장함수를 거의 안쓰고 다 풀어서 코드를 적었다. 너무 기니 다음부터는 함수를 쓰는걸로.... .. 2021. 8. 7.
[백준_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.
728x90

티스토리툴바