www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 이번에는 이 문제를 풀어볼게요. 세그먼트 트리를 이용해서 최솟값과 최댓값을 구하는 문제입니다. 이론파트에서 너무 누적합 얘기만 해서 찔렸거든요 헣헣 저번에 작성해뒀던 틀에서 조금의 수정으로 풀어보겠습니다. + 연산 대신에 min 연산과 max 연산으로 고치면 되겠네요. 그러면 짜잔~ import math import sys def input(): return sys.stdi..
전체 글
세그먼트 트리에 대한 글은 이미 많습니다. 심지어 다들 구체적으로 설명해주고 계십니다. 그런데 세그먼트 트리를 단지 구간합 트리라고 알고 계시는 분들이 생각보다 많이 계신 이유로 오해를 정정하고자 포스팅해보겠습니다. 세그먼트 트리가 없다면? 세그먼트 트리(구간 트리)는 주어진 쿼리에 대해서 빠르게 응답하기 위한 자료구조입니다. 배열 A가 주어져있고 A의 start~end 구간까지의 합을 구하려고 합니다. for문으로 answer+=A[i]를 돌리면 되겠죠. 그런데 만약 이 구간내 값이 변동이 된다면 어떨까요?? 총 M번 반복한다고 가정했을때, 수정 연산(O(1))+ 합산 연산 = O(NM)의 시간복잡도가 발생합니다. 세그먼트 트리 도입 여기에 세그먼트 트리를 사용한다면 어떻게 변할까요?? 수정 연산 = ..
| 백기선님의 자바 라이브 스터디 8주차 주제!! 인터페이스란? 추상클래스에 대해서 다뤘었죠. 인터페이스는 추상화를 극대화한 추상클래스라고 볼 수 있습니다. 추상클래스와의 차이점을 언급해볼게요. 추상클래스는 추상메서드 + 일반 메서드나 필드를 가진다면, 인터페이스는 Only 추상메서드, 상수만 가질 수 있습니다. 추상클래스는 "is-a : ~는 ~이다" 의 개념이고 인터페이스는 "has-a : ~는 ~를 할 수 있다." 라는 내용도 기억해두시면 좋습니다. 개인적으로 이 인터페이스는 자바의 다형성을 이용하는 방식으로 코드의 수정을 줄이고 유지보수성을 높인다고 생각합니다. (변경에는 닫혀있으며 확장에는 열려있다) 인터페이스 정의하는 방법 추상클래스랑 인터페이스랑 구분이 있어야 컴파일하는 과정에서 문제를 캐치..
programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 2021년 상반기 웹 백엔드 개발 데브 매칭에 출제된 문제입니다. 그때도 푼 기억이 있는 문제인데, 다시 풀려니까 코드를 더럽게 짰다만 기억나고 디테일한 부분은 기억이 안나서 다시 풀어봤습니다. 문제 요약 lottos는 내가 보유한 로또 번호 win_nums는 당첨 로또 번호입니다. lottos 배열의 0은 지워져서 알 수 없는 ..
이 문제에 대한 질문을 한 3번정도 봐서 미래에 또 같은 문제로 고생하실 분들이 검색을 통해서 찾으셨으면 하는 바람에 적어봅니다. Java file outside of source root 라면서 실행을 할 수 없을때의 해결법입니다. 원인 또한 다양한데 아래 사진처럼 프로젝트 폴더의 상위 폴더를 기준으로 열렸을 경우의 해결법을 다룹니다. 이 경우에는 해결 방법도 간단해요. root directory 맞춰서 프로젝트를 다시 열어주면 되는거거든요. File - Open - 프로젝트명으로 경로를 제대로 찾아서 열어주세요. 그러면 해결이 됩니다. 진행이 얼마 되지 않은 프로젝트라면 새로 다시 만들면 되지만 어느정도 진행한 프로젝트라면 날리기가 아깝죠. 너무 걱정하지 마시고 원인을 먼저 제대로 파악하신 뒤에 차근..
programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 오늘의 문제입니다. 수식 문자열이 주어지면 (+,-,*)연산의 우선 순위를 능력껏 수정해서 최대값을 계산하라는 문제입니다. 문제 접근 저 같은 경우에는 일단 "100+200"이 있으면 100,+,200 씩 나누도록 분리했습니다. test = expression.replace('-',' - ').replace('+',' + ').replace('*',' * ').split()..
ps 거의 한 달만인가요 허허 토요일에 코딩테스트가 있어서 급하게 벼락치기로 준비해봅니다. 합격하면 좋고 합격을 못하더라도 예전보다만 제발 잘 봤으면 좋겠습니다. 어쨋든 오늘 풀 문제는 2021년 카카오 공채 코딩테스트 1번 문제였던 신규 아이디 추천 문제입니다. programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 문제 접근 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳..
| 백기선님의 자바 라이브 스터디 7주차 주제 패키지란? 자바에서 패키지는 클래스나 인터페이스를 구분짓는 폴더(디렉토리) 개념입니다. 우리가 D드라이브 → 사진 폴더 → 음식 or 인물 등등 구분지어서 정리하듯이 묶어서 관리하는데 사용됩니다. 위의 예시를 굳이 패키지스럽게 표현하자면 D.사진.음식 이런 느낌이겠네요. package com.example; 소스에서 가장 맨 윗줄에 위치하고 있으며 딱 한 줄만 필요합니다. 패키지 이름과 소스 코드가 위치한 폴더의 이름이 동일해야합니다. 따라서 중간에 패키지 이름(폴더 이름)을 변경한 경우 소스 코드에서도 수정이 필요합니다. 패키지 이름은 java로 시작해서는 안된다고 합니다. 아마도 java나 javax라는 패키지가 자바 기본(확장) 패키지라서 그런가봅니다...