devkty 님의 블로그

오늘은 화요일로 퀴즈를 푸는 날입니다.9:30 ~김정민 주니어 코치님을 뵀다. 숙소 2층에 사시나보다. 갑작스럽게 만나서 당황스러웠지만, 이런저런 얘기를 했다.(문제가 너무 어려워서 다 못풀었다… 그러면 어려운건 건너뛰고 해보시라)카페를 간다고 하니 가서 빵이랑 커피를 사주셨다. 너무 감사드린다… 아침에 배고파서 머리 안돌아가는데, 코치님은 따로 아침을 안드신다고 한다. 나중에 뭐라도 사드려야겠다.오늘은 문제수를 많이 풀어야해서 어려운 문제는 과감히 스킵했다. 나중에 포스팅하겠다.12번 (10828) 스택그냥 스택을 구현하라는거랑 다름이 없다. 난 간단할 줄 알았는데, 생각보다 어려웠다. 명령어를 리스트 형식으로 인식해서 명령어를 나누는 생각이 주 핵심인 것 같다. 또한 파이썬은 스택이 따로 없으므로 리..

스택스택은 데이터를 임시 저장할 때 사용하는 자료구조. 데이터의 입력과 출력 순서는 후입선출 방식입니다.스택에 데이터를 넣는 작업은 push, 스택에서 데이터를 꺼내는 작업은 pop이라고 합니다. 데이터를 차곡차곡 채우고, 꺼내는 작업은 맨위부터 수행합니다. pop되는 윗부분을 top이라고하고, 아랫부분(마지막)을 bottom이라고 합니다.stk: 스택배열푸시한 데이터를 저장하는 스택 본체인 list형 배열. 인덱스가 0인 원소는 스택의 바닥(bottom)이라 합니다.capacity: 스택의 크기스택의 최대 크기를 나타내는 int형 정수. 이 값은 배열 stk의 원소 수인 len과 일치합니다.ptr: 스택 포인터스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값. 스택이 비어있으면 ptr은 0이고, 가득 ..

오늘은 유윤선 코치님과 함께 커피챗을 했습니다. 정말 다양한 정보와 진로에 관한 상담을 해주셨고, 많은 도움이 되었습니다. 오늘도 어김없이 8983 사냥꾼, 2630 색종이만들기, 1629 곱셈 백준 문제를 풀어보았습니다. 6번 (8983) 사냥꾼https://www.acmicpc.net/problem/8983원래는 어려워보여서 다른문제를 풀다 다시왔다. 근데 생긴 코드와 달리 해석을 해보니 간단한 문제였다.import sys# 1. 입력 받기data = sys.stdin.read().split()M, N, L = map(int, data[:3]) # 사대 개수, 동물 개수, 사정거리 (인덱스 0~2까지)shooters = sorted(map(int, data[3:M+3])) # 사대 위치 재정렬(3..

오늘은 분위기 전환을 위해 본가에 다녀왔다. 그래서 갔다와서 11시부터 1시반까지 가장 긴 증가하는 부분 수열을 이진탐색으로 풀어보았다. 5번 (11053) 가장 긴 증가하는 부분 수열DP로 풀수도 있으나 이번 주차는 해당 문제를 이진탐색으로 푸는 것이 목표이므로 그렇게 풀어보도록 노력하겠다.이와 같은 문제를 풀기위해선 LIS 개념을 알 필요가 있다고 한다.LIS: (Longest Increasing Subsequence) : 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.https://namu.wiki/w/최장 증가 부분 수열의 예시를 참고하면 이해하기 수월..

9:30출근했다. 어제 못풀었던, 잠 들기 전까지 날 괴롭힌 공유기 설치 문제를 알아보았다.3번 (2110) 공유기 설치https://www.acmicpc.net/problem/2110n개의 집에 x들의 집합들로 있는데, 그 사이에 C개의 공유기를 설치해야한다. 공유기 간 거리를 최대한 멀리 두어 설치해야한다. 공유기를 설치했는데 대수가 적으면 거리를 줄인다. 대수가 많다면 거리를 늘린다. low는 최소거리, high는 가장 먼 두집의 거리, mid값을 정해서 공유기 설치하고 집 위치는 소트로 재정렬해야한다.# 입력단N, C = map(int, input().split())arr = []for _ in range(N): # 입력값을 배열에 넣는다. arr.append(int(input())..

일주일이 지나고, 새로운 주차가 시작되었다. 새로운 팀원분들과 새로운 마음으로 시작하겠다.이번주의 새로 배울 내용은 이분 탐색, 분할 정복, 스택, 큐, 우선순위 큐, Linked List, 해시 테이블 이다.이진 검색 알고리즘퀵소트하고 개념이 비슷하다. 어떤 수 x를 찾을 때 인덱스에서 1/2되는 지점을 기준인 pc로 잡는다. 그 후 x에 대해 pc와 비교해 가까운 구간만 검색 범위로 줄인다. 줄여진 범위에서 pc를 1/2 지점으로 재지정한 다음 전처럼 x와 pc를 비교하여 가까운 구간만 검색 범위를 줄인다. 언젠간 두개까지 남을 것이고 해당되는 x가 있으면 검색에 성공하고 한개까지 남았는데도 못찾으면 검색을 실패한 것이다. pl과 pr은 퀵소트처럼 왼쪽, 오른쪽 검색 시작 위치.여기서 복잡한 개념이 ..

여기에서는 Week01의 핵심 내용을 정리해보았다.들어가기 앞서 파이썬의 숫자는 0, 1, 2, 3 … 순으로 간다. 0을 포함함을 잊지말자.대표 연산자: 덧셈 ( + ) · 뺄셈 ( - ) · 곱셈 ( * ) · 나눗셈 ( / ) · 거듭제곱 ( ** ) · 몫( // ) · 나머지( % )배열배열은 따로 흩어진 변수를 하나로 묶어서 사용할 수 있게 하며 코드를 쉽고 효율적으로 작성 가능합니다. 파이썬에서 배열은 크게 데이터 컨테이너라는 리스트와 튜플로 구현할 수 있습니다.리스트는 원소를 변경할 수 있는 뮤터블 list형 객체입니다. [,,]로 쉼표로 구분하여 생성가능하며 []만 사용하여 빈 리스트를 생성할 수도 있습니다. list(range(3,13,2)) → [3, 5, 7, 9, 11]를 통해 특..

전에 백승현 코치님이 말씀하신 퀵소트를 주로 쓰는 이유가 무엇인가? 에 대해→ 퀵 정렬의 루프는 대부분 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있습니다. 메모리 참조가 지역화되어 있어 CPU 캐시의 히트율이 높아지기 때문입니다.라고 답했다. 이걸로는 쉽게 이해하기 어려워 알기 쉽게 다시 알아봤다. 먼저, 퀵소트는 배열에서 작은 파티션으로 나누면서 정렬한다. 이 과정에서 서로 가까운 데이터만 다루면서 진행한다. 이 개념을 머리에 기억하자.컴퓨터는 CPU라는 연산장치와 RAM이라는 임시저장소가 있다. 대게 CPU에서 계산하기위해서는 RAM에서 데이터를 끌어다가 계산한다. 이 과정에서 성능이 떨어진다. 그러나 CPU는 최근 계산한 내용이나 자주 사용하는 데이터를 “캐시”라는 작은 저장 공간에 저장해..

https://github.com/prtky/JungleBackjoon해당링크를 들어가면 코드와 주석만 보실수 있습니다.오늘은 한주의 마지막날이다. 왜냐하면 정글에서 새 주차는 금요일부터 시작이기 때문이다. 사실 일요일 같은 느낌이라서 일찍 갈려했는데, 새벽 1:30에 벨로그를 작성하고 있다.오늘은 한주를 마무리했기 때문에 코치님들과의 티타임을 가졌는데 거기서 나온 질문이 도움이 될 것 같아 정리했다.코딩 테스트 시 주의할 점은?패키지를 쓰면 나중에 면접 시에 물어볼 수 있다. 예를 들어 콤비네이션을 함수가 아닌 코드로만 구현할 수 있는가? 그러니 패키지 함수도 돌아가는 이론은 알아야한다.이번주의 백트래킹이나 재귀함수 같은경우 100퍼센트 이해못하고 담주로 넘어갈 수도 있는데, 그럴 경우 오늘같은 날에 ..

https://github.com/prtky/JungleBackjoon해당링크를 들어가면 코드와 주석만 보실수 있습니다.34번 (10819) 차이를 최대로해당 문제는 N개의 정수로 이루어진 배열에 대해 앞의 수와 바로 뒷 수의 차가 제일 커야한다. 문제 이해도 잘안됐고, 코드 작성에 어려움이 있어 GPT와 블로그들의 도움을 받아 클론 코딩하며 이해했다.from itertools import permutations # itertools라는 라이브러리의 permutations 순열함수를 임포트해서 쓴다.# 주어진 배열 arr에 대해 |A[i] - A[i+1]|의 합을 계산하는 함수이다.def difference_sum(arr): total = 0 # 합을 저장할 변수의 초깃값을 0으로 한다. ..