티스토리

버그기록센터

검색하기

블로그 홈

버그기록센터

winwin-k9.tistory.com/m

버그는 에프킬라로

구독자: 0

방명록 방문하기

주요 글 목록

블로그 전환 현 티스토리 블로그에서 velog로 블로그를 이동하려고 합니다. 마크다운을 지향하는 본인으로써 티스토리보다 velog가 더 편리하다는 것을 알아버렸습니다. 좀 더 깔끔하고 읽기 좋은 버그기록센터가 되겠습니다. https://velog.io/@winwink9/posts winwink9 (버그기록센터) / 작성글 - velog velog.io 공감수 0 댓글수 2 2024. 7. 22.
성능 개선을 진행해보자3 Paging 적용하기성능을 좀 더 올리고 싶었는데 프론트 개발자와 협의 하에 페이징을 적용하기로 하였다.위에서 적용하고자하는 JPA 의 DTO 직접 조회보다 더 깔끔하게 처리할 수 있다.public Page findAllByOrderByModifiedDateDesc(Pageable pageable) { QueryResults result = queryFactory .select(Projections.fields(AllBookMarkResponseDto.class, bookMark.id.as("id"), bookMark.modifiedDate.as("date"))) .. 공감수 0 댓글수 0 2024. 7. 17.
성능 개선을 진행해보자 2 IndexbookMark의 modifiedDate에 대한 컬럼에 내림차순 인덱스를 만들어준다.@Table(name = "book_mark", indexes = { @Index(name = "idx_modified_date_desc", columnList = "modifiedDate DESC")}) 그러나 실행계획을 분석해보면 인덱스를 타지 않음을 알 수 있었다. 강제로 인덱스를 타도록 쿼리 힌트를 주었다. EXPLAIN SELECT * FROM book_mark FORCE INDEX (idx_modified_date_desc) ORDER BY modified_date DESC; 실행결과는 아래와 같다. 보시다시피 속도가 반절이상 빨라진 것을 볼 수 있다.그러나 문제점은 queryDSL.. 공감수 0 댓글수 0 2024. 7. 7.
서버 과부하를 아라보자 서버 과부하서버가 리소스를 소진하여 들어오는 요청을 처리하지 못할 때 발생한다. 이 때 서버는 사용자의 요청을 처리하지 못해 응답 없음이 뜨게된다.보통 서버의 CPU 사용량이 80, 90%에 도달하면 메모리가 부족하여 계속해서 스와핑이 발생하면 과부하 상태가 된다.모니터링을 이용한 자원할당이러한 과부하 분제를 CPU, 메모리, 대역폭과 같은 자원 할당을 수행한다.모니터링을 하는 이유는 서버 과부하로 인한 서버 중지에 대한 대처가 가능하기 때문이다. 어떤 페이지 요청에 트래픽이 얼마나 발생했는지 등을 모니터링을 통해 파악할 수 있기 때문이다.AWS 오토스케일링을 이용하면 cloudWatch가 계혹해서 모니터링을 진행하여 서버 대수를 자동으로 늘려주는 작업을 한다. 또한 netdata를 이용하는 것도 가능하.. 공감수 0 댓글수 0 2024. 7. 5.
성능 개선을 진행해보자 1편 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 성능 개선하기서론현재 bookMark에 100만개의 데이터를 넣어놓았다.이에따라 연속 독서기록량을 체크할 때 성능이 매우 좋지 않았다.전체 책갈피 조회 쿼리를 다시 점검해보았는데, 약 8s 정도로 시간이 다소 걸리는 것을 확인할 수 있었다.시간을 좀 더 개선시켜보는 것이 목표이다.쿼리 DSL로의 변경전체 책갈피 리스트를 조회하는데 JPA를 이용하여 다음과 같은 메소드를 사용하고있다.public Map> showAllBookMarkList() { List list = bookMarkRepository.findAllByOrderByModifiedDateDesc().stream() .map(A.. 공감수 0 댓글수 0 2024. 7. 3.
Need to specify how to reconcile divergent branches를 아라보자 기존 git pull의 문제점 : 세 가지 전략으로 나뉘게 된 배경git pull --help에서 설명하는 내용git pull --help에서는 아래처럼 설명한다.In its default mode, git pull is shorthand for git fetch followed by git merge FETCH_HEAD. 번역하자면, 디폴트모드에서는 git pull이 git fetch, 즉 git merge FETCH_HEAD의 작업에 대한 간단명령어(속기)라는 말이다.다시 말해 git pull의 내부 동작이 git merge FETCH_HEAD처럼 동작한다는 말이다. 따라서 이 디폴트모드에서는 git pull을 수행했을 때 git merge에 대한 불필요한 commit이 자동으로 생긴다. 기존 gi.. 공감수 1 댓글수 0 2024. 6. 28.
[프로그래머스] 숫자게임 문제xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.각 사원은 딱 한 번씩 경기를 합니다.각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.만약 숫자가 같다면 누구도 승점을 얻지 않습니다.전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순.. 공감수 0 댓글수 0 2024. 6. 28.
프록시와 로드밸런싱을 아라보자 Load Balancing서버가 처리해야 하는 업무를 여러 대의 서버로 나누어 처리하는 것. 한대의 서버로 부하가 집중되지 않도록 트래픽을 관리하여 각 서버가 최적의 퍼포먼스를 보일 수 있도록 하는 것.서비스 규모가 늘어나면 이를 분산하기 위한 방법으로 두가지 방법이 있다.Scale - UpCPU, 메모리 등 하드웨어 기능을 업그레이드한다. 비용이 기하급수적으로 증가한다. 하나의 서버에 웹 서비스를 제공하므로 서버 장애시 가용성에 문제가 발생한다.Scale - out저렴한 노드를 여러개를 하나의 클러스터로 구성하는 방식. 하나의 노드에 문제가 발생해도 웹 서비스가 중단되지 않는다. 만약 이를 통해 트래픽 대처를 한다면, 여러 대의 서버로 트래픽을 분산하기 위한 로드 밸런싱이 필요하다.로드밸런싱 방식은 아.. 공감수 0 댓글수 0 2024. 6. 26.
[프로그래머스] 부대복귀 문제강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sources의 원.. 공감수 1 댓글수 2 2024. 6. 18.
[BOJ] 소트게임 문제홍준이는 소트 게임을 하려고 한다. 소트 게임은 1부터 N까지 정수로 이루어진 N자리의 순열을 이용한다. 이 게임에선 K가 주어진다. 어떤 수를 뒤집으면,그 수부터 오른쪽으로 K개의 수를 뒤집어야 한다. 예를 들어, 순열이 5 4 3 2 1 이었고, 여기서 K가 3일 때, 4를 뒤집으면 5 2 3 4 1이 된다. 반드시 K개의 수를 뒤집어야하기 때문에, 처음 상태에서 2나 1을 선택하는 것은 불가능하다.입력으로 들어온 순열을 오름차순으로 만들려고 한다. 게임을 최대한 빨리 끝내고 싶을 때, 수를 최소 몇 개 선택해야 하는지 구해보자.풀이숫자를 뒤집어서 정렬된 숫자를 만들어야한다.숫자를 뒤집는 방법규칙은???규칙은 없다. 즉, 모든 경우를 탐색해야 한다.따라서 BFS를 이용하여 탐색하는 것을 생각하였다.. 공감수 0 댓글수 0 2024. 6. 16.
git 다른 브랜치 커밋 가져오기 branch를 파서 힘들게 작업했는데기획이 바뀌거나 하는 이유로 반영할 수 있는 커밋이 한두 개밖에 되지 않을 때가 있다이럴 때 원하는 커밋 한두 개만 가져와서 dev branch에 반영해보자 git에서 cherry-pick이라는 걸 사용할 수 있다 ① branch가 두 개 있다고 가정하자 feature/signupfeature/signin feature/signin branch에 있는 커밋 하나만 가져오려고 한다 ② commit 커밋 id 가져오기 git checkout feature/signingit log --abbrev-commit `````commit 89c1234`````89c7823 형태 => 커밋 ID를 가져온다 @ git의 commit id는 SHA1 알고리즘으로 만들어진 해시.. 공감수 0 댓글수 0 2024. 6. 14.
[BOJ] 문제 추천 시스템 Version 1 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 문제문제 추천 시스템 Version 1, 문제 링크풀이적절한 자료 구조를 이용해야 한다.문제의 조건대로 정렬 상태를 유지하면서 가장 첫번재 요소와 가장 마지막의 요소를 자유롭게 추출할 수 있어야한다.여러가지의 자료구조를 생각해보았다.DequeueDequeue는 앞과 뒤의 요소를 자유롭게 추출할 수 있다.그러나 정렬상태를 계속해서 유지할 수 없다는 단점이 있다.List인덱스를 통해 요소의 편리한 접근이 가능하다.Dequeue와 마찬가지로 정렬 상태를 계속 유지할 수 없다.PriorityQueue우선순위 조건을 선언한 후, 최대힙, 최소힙 두가지를 사용하면 풀이 가능하다.TreeSet우선순위 조건 선언으로 정렬상태 유지가능, 및 .. 공감수 0 댓글수 1 2024. 6. 14.
소켓을 아라보자 포트네트워크 프로토콜에서 프로세스를 식별하기 위해 사용되는 번호.소켓컴퓨터 네트워크에서 프로세스간 통신을 가능하게 하는 추상화 개념. 리눅스 커널의 관점에서는 소켓은 통신을 위한 끝점이고, Unix프로그램 관점에서는 해당 식별자를 가지는 열린 파일.각 소켓은 IP주소와 포트 번호로 이루어진 소켓 주소를 가진다.소켓은 라이브러리? 시스템콜?소켓은 라이브러리와 시스템 콜 두가지 개념을 포함한다.소켓 라이브러리소켓 프로그래밍을 위한 API를 제공하는 라이브러리. 소켓 라이브러리는 프로그래밍 언어별로 제공되며, 개발자는 이러한 라이브러리를 사용하여 소켓을 생성하고 관리한다. 2. 소켓 시스템 콜 OS 수준에서 소켓 기능을 제어하기 위한 시스템콜. 소켓 시스템 콜은 OS 커널에 의해 제공되며, 네트워크 연.. 공감수 0 댓글수 0 2024. 6. 11.
[BOJ] 웜홀 문제때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.)웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다.여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.풀이그래프를 이용한 탐.. 공감수 0 댓글수 0 2024. 6. 11.
[BOJ] 파티 문제N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.풀이출발지 -> 도착지 -> 출발지의 거리를 탐색하면서 비용이 가장 큰 사람을 구하면 된다.각 노드별 모두의 최단 겨리를 알아야.. 공감수 0 댓글수 1 2024. 6. 8.
전송계층을 아라보자 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 전송계층송신자, 수신자를 연결하는 통신 서비스를 연결하는 통신 서비스를 제공하며, 연결 지향 데이터 스트림, 신뢰, 흐름제어를 제공하며 애플리케이션과 인터넷 계층 사이의 데이터가 전달될 때 중계 역할을 한다.전송계층은 논리적으로 연결된, 종단간의 호스트에 신뢰성 관련 기능(ex) 흐름제어, 혼잡제어, 오류제어)를 제공한다. 데이터링크는 물리적으로 연결된 호스트 사이의 전송으로 묶여있는 호스트나 노드의 오류제어 흐름제어 회선제어를 제공한다.흐름제어송신측과 수신측 사이의 데이터 처리 속도를 제어하기 위해 데이터 처리 속도를 조절한다.따라서 버퍼 오버플로우를 방지할 수 있다. 슬라이딩 윈도우 기법을 이용하여 슬라이드 크기만큼 패킷을.. 공감수 0 댓글수 0 2024. 6. 4.
[BOJ] DSLR " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 문제네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다.n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이.. 공감수 0 댓글수 0 2024. 6. 2.
[BOJ] 가장 가까운 세 사람의 심리적 거리 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 문제여러분은 요즘 유행하는 심리검사인 MBTI에 대해 들어보았는가?MBTI(Myers-Briggs Type Indicator)는 C.G.Jung의 심리유형론을 근거로 하여 Katharine Cook Briggs와 Isabel Briggs Myers가 보다 쉽고 일상생활에 유용하게 활용할 수 있도록 고안한 자기보고식 성격유형지표이다. (출처: 위키백과)MBTI는 아래와 같이 네 가지 척도로 사람들의 성격을 구분한다.외향(E) / 내향(I)감각(S) / 직관(N)사고(T) / 감정(F)판단(J) / 인식(P)각 척도마다 두 가지 분류가 존재하므로, MBTI는 총$2^4 = 16$가지 유형이 있음을 알 수 있다. 일반적으로 MBTI.. 공감수 0 댓글수 0 2024. 6. 1.
[BOJ] 회의실 배정 문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.풀이숫자가 너무 난잡하게 나열되어 있어서 우선 정렬을 하기로 하였다.회의 시작 시간 오름차순, 끝나는시간 오름차순으로 정렬을 하였다. 회의실을 배졍하는 기준은 다음고 같이 잡았다.이전에 배정한 회의 종료 시간이 넣을 회의 시작시간보다 작거나 같.. 공감수 0 댓글수 0 2024. 5. 24.
[BOJ] 랜선 자르기 문제집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가.. 공감수 0 댓글수 0 2024. 5. 24.
[프로그래머스] 리코쳇 로봇 문제리코쳇 로봇이라는 보드게임이 있습니다.이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.다음은 보드게임판을 나타낸 예시입니다....D..R.D.G.......D.DD....D...D....여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것.. 공감수 0 댓글수 0 2024. 5. 18.
빈 등록과 주입을 아라보자 Spring Bean 등록하기컴포넌트 스캔과 자동 의존관계 설정스프링 부트에서 사용자 클래스를 스프링으로 등록하는 가장 쉬운 방법은 @Component를 사용하는 것이다.@contorller, @service, @reposiotory는 모두 @Component를 포함하고 있다.해당 어노테이션으로 등록된 클래스는 스프링 컨테이너에 의해 자동으로 생성되어 스프링 빈으로 등록된다.자바 코드로 직접 등록수동으로 스프링 빈을 등록하려면 자바 설정 클래스를 만들어 사용해야 한다. 스프링 부트가 아닌 그냥 스프링을 사용하면 XML파일을 이용하여 빈을 등록해야 한다. 설정 클래스를 만들고, @Configuration을 클래스 선언부 위에 추가하면 된다.이후 특정 타입을 return 하는 메소드를 만든 후, @B.. 공감수 0 댓글수 1 2024. 5. 15.
[프로그래머스] 연속된 부분 수열의 합 문제비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.부분 수열의 합은 k입니다.합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.풀이완전탐색을 해야 한다고 생각했다.따라서 처음에는 단순에 반복.. 공감수 0 댓글수 0 2024. 5. 14.
[프로그래머스] 디펜스 게임 문제준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.준호는 처음에 병사 n명을 가지고 있습니다.매 라운드마다 enemy[i]마리의 적이 등장합니다.남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.무적권은 최대 k번 사용할 수 있습니.. 공감수 0 댓글수 0 2024. 5. 14.
[BOJ] 나무꾼 이다솜 문제이다솜은 나무꾼이다. 이다솜은 산신령이 준 금도끼와 은도끼를 이용해서 나무를 열심히 했다. 나무가 끝난 후에 나무들을 쳐다보면서 내가 왜 나무를 하면서 살까 생각하다가, 나무가 엄청나게 값어치가 있다는 것을 알고 나무를 팔러 시장에 가기로 했다.지역 목재상에서 이다솜의 나무를 사려고 했지만, 너무 길이가 제멋대로여서 나무를 사는 것을 거절을 했다. 목재상의 조건은 일단 팔려고 하는 나무의 길이를 전부 같게 만들어 오라는 것이었다. (나무의 길이는 자연수로) 이다솜은 나무를 하나씩 여러 번 팔려고 했지만, 지역 목재상의 주인은 한 사람에게 평생 단 한번의 판매 기회를 제공하다고 했기 때문에, 이다솜은 근처 작업장으로 가서 나무를 자르기로 했다.작업장에서 나무를 한 번 자를 때는, C원이 든다. 그리고,.. 공감수 0 댓글수 0 2024. 5. 9.
[BOJ] 이진검색트리 문제이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.이진 검색 트리를 전위 순회한 결과가 주어졌.. 공감수 0 댓글수 0 2024. 5. 7.
[BOJ] 줄어들지 않아 문제어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.예를 들어, 1234는 줄어들지 않는다.줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.풀이먼저 규칙을 파악해야 했다.2차원 배열을 기준으로 파악해보자.행을 자릿 수, 열을 자릿수중 가장 큰 수 라고 했을 때 다음과 같은 규칙이 발생한다.1111123456361015211번째 자릿수는.. 공감수 0 댓글수 1 2024. 5. 1.
[BOJ] 언더프라임 문제자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자.풀이해당 범위까지 소인수 분해 후 에 길이를 구해서,해당 길이에 대한 소수 판별을 계속해서 구하는 것은 시간초과가 발생한다. 따라서 특정 범위까지의 소수 판별 여부를 적어두면, 소수 판별을 반복해서 구할 필요가 없어진다.따라서 에라토스테네스의 체를 이용하여 b.. 공감수 0 댓글수 1 2024. 4. 28.
[ BOJ] 가장 가까운 공통 조상 문제루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.image예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요풀이처음에는 부모의 노드를 찾아야 하니 탐색을 진행해야 한다고 생각했다.따라.. 공감수 0 댓글수 0 2024. 4. 26.
[BOJ] 노드 사이의 거리 문제$N$개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.풀이노드간의 거리를 구해야 하는 문제이다.우선 노드간의 비용을 이차원 배열을 이용하여 나타내주었다.이차원 배열에서 BFS 탐색을 진행하여 비용을 계산하였는데, 비용 계산하는 부분이 만만치 않았다.다른 자료를 참고한 결과int[] distance = new int[N + 1]와 같은 배열을 BFS동작 초기 시 하나 선언하여탐색시의 비용을 누적해준다.for (int i = 1; i 누적한 결과를 그대로 저장하고 다음 poll시 가져올 수 있으므로 거리를 누적해서 더할 수 있다.BFS말고도 플로이드 워셜을 이용하여 한번에 비용을 나타내는 것도 가능하다.https://github.com/Win-9/A.. 공감수 0 댓글수 1 2024. 4. 26.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.