본문 바로가기

분류 전체보기42

Binary Search, Parametric Search 이해하기 알고리즘 문제를 풀다 보면 효율성 기준을 통과하지 못하는 경우가 종종 있습니다 🥲 이번 글에서는 이럴 때 떠올릴 수 있는 알고리즘 중 하나인 이분탐색(Binary Search)과 이와 유사한 Parametric search의 개념을 살펴보고, Parametric Search를 어떻게 풀 수 있을지 알아보도록 하겠습니다. Binary Search (이분탐색) 이분탐색은 쉽게 말하면 배열을 반씩 잘라가며 원하는 값을 탐색해나가는 알고리즘입니다. 중간에 위치한 값과 비교하고 바로 절반을 버리려면 배열이 정렬된 상태여야겠죠? 즉, 이진탐색은 정렬된 배열에서 값을 찾아내는 검색 알고리즘이라고 할 수 있겠습니다. 예를 들어 [1,2,3,4,5,6,7,8,9]라는 배열이 있을 때 9가 어디에 위치했는지 알고 싶다면 .. 2021. 7. 3.
[Python3] 코딩테스트에 자주 쓰이는 Code Snippets 파이썬으로 코딩테스트를 준비하면서 필요한 구문들을 적어두고 있습니다. 공부하면서 계속 업데이트할 예정입니다 1. 입출력 1.1. 입력 sys.stdin.readline() 의 활용 한 개의 정수를 입력받을 때 import sys a = int(sys.stdin.readline()) 정해진 개수의 정수를 한 줄에 입력받을 때 import sys a,b,c = map(int,sys.stdin.readline().split()) ​ map() 은 반복 가능한 객체(리스트 등)에 대해 각각의 요소들을 지정된 함수로 처리해주는 함수. 임의의 개수의 정수를 한 줄에 입력받아 리스트에 저장할 때 import sys data = list(map(int,sys.stdin.readline().split())) ​ map(.. 2021. 7. 2.
알고리즘스터디_4주차(210618 ~210624) 기록 (벨로그에서 티스토리로 기술블로그 이전중입니다.) (원 게시일 : 21년 6월 25일) 4주차에는 백준 문제 연산자끼워넣기, 스타트와 링크, 경사로를 풀었다. 4주차에 배운 내용은 다음과 같다. 경사로 문제는 함수로 구현하지 않아서 코드가 길어졌다. 함수로 최대한 구현해 디버깅하기 쉽고 가독성 좋은 코드를 짜자. for - else 구문을 배웠다. flag 대신 사용할 수 있을 것 같다. 4주차 문제풀이는 여기에. 2021. 6. 29.
알고리즘스터디_3주차(210611 ~210617) 기록 (벨로그에서 티스토리로 기술블로그 이전중입니다.) (원 게시일 : 21년 6월 25일) 3주차에는 백준 퇴사, 연구소, 로봇청소기 를 풀었다. 3주차 스터디 문제풀이 회고 퇴사 문제는 처음 접근할 때 dp느낌이 나서 dp로 풀었는데, 코드를 짜는데 시간이 좀 걸렸다. dp문제를 아직 자유롭게 풀지는 못하는 것 같다. dp문제를 연습을 많이 해봐야겠다. 연구소 문제는 풀다가 브루트 포스 말고 좋은 방법이 없을까 고민하다가 못 풀었는데 브루트포스로 풀어봐야겠다. 로봇청소기 문제는 1주차 알고리즘 스터디에서 배웠던 그래프 순회방식을 활용하여 절대적 방향을 상대적 방향으로 변환하여 풀었다. 3주차 문제풀이는 여기에. 2021. 6. 29.
알고리즘스터디_2주차(210604-210610) 기록 (벨로그에서 티스토리로 기술블로그 이전중입니다.) (원 게시일 : 21년 6월 10일) 2주차에는 백준 문제집 시험감독, 주사위굴리기, 테트로미노 문제를 풀었다. 주사위던지기 문제는 풀고나서 다른 사람들의 풀이를 보니 주사위를 더 세련된 방식으로 업데이트할 수 있을 듯하다. 문제 접근할 때 최적의 방법을 더 고민해보자. 2주차 알고리즘스터디 문제풀이는 여기에. 2021. 6. 29.

티스토리툴바