Algorithm

[JAVA] 백준 2042 : 구간 합 구하기

문제 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 해결방법 안녕하세요 ! 글은 쓰고 있지 않지만 꾸준히 알고리즘을 풀이하고는 있는데 최근에 세그먼트 트리를 하게 되면서 기본 구조를 알 수 있는 문제는 기록을 해두면 좋을 것 같아서 오랜만에 글을 작성해 봅니다. 세그먼트 트리는 누적합의 다음 형태라고 볼 수 있는데 누적합의 경우 구간의 합은 O(1)에 구해지지만 중간에 값이 업데이트가 될 경우 O(N)만큼 시간이 소모되기 때문에 업데이트 횟수가 많다..

[JAVA] Programmers : 문자열 나누기

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결방법 조건에 맞게 문자열을 분리하고 분리된 횟수를 찾는 문제 처음 읽은 글자와 다른 글자의 수가 서로 일치될 때 분리를 해야한다. 예를 들어 "aaabbaccccabba" 의 경우 a가 기준이 되어서 aaabbacc 일때 a의 개수가 4개이고 a를 제외한 bbcc가 4개여서 이 타이밍에 분리가 된다. 즉 기준 문자와 다른 문자 수가 일치가 되지않으면 계속 분리하지않고 진행이 된다. 아까 위의 예시로 추가적으로 설명을 작성하면 aaabb인 상태에서는 a의 개수가 3개이고 a를 제외한 bb는 2개여서 분..

[JAVA] 백준 12764 : 싸지방에 간 준하

문제 12764번: 싸지방에 간 준하 첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000 www.acmicpc.net 해결방법 대기하는 인원 없이 모두가 싸지방에 오자마자 컴퓨터를 이용하는데 필요한 컴퓨터의 개수를 구하고 각 자리별로 사용한 인원을 구하는 문제이다. 총 3개의 우선순위 큐를 활용했다. waitQ -> 대기인원 : 시작 시간이 적은 사람부터 먼저 꺼내서 확인하기 위함 playerQ -> 이용인원 : 현재 싸지방을 이용 중인 사람 comQ -> 사용가능한 컴퓨터 : 사용 가능한..

[JAVA] 코드트리 : 2개의 사탕

문제 코드트리 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제가 보이지 않으면 https://www.codetree.ai/frequent-problems 여기서 찾아볼 수 있다. 이번 문제는 따로 코드를 모듈화 하지 않고 일자로 나열해서 작성해서 가독성이 매우 좋지 않지만 코드 트리에서 자바 풀이를 따로 제공하지 않아 도움이 될까 하여 업로드한다. 해결방법 옛날에 필통으로 하던 구슬 미로 찾기 게임이 생각나는 문제였다. 구슬 대신 사탕을 기울여서 EXIT라고 적힌 밖으로 빨간색 사탕만 빼내야하는데 밖으로 빼내기 위한 최소 횟수를 찾는 문제이다. 전형적인 시뮬레이션 문제라고 할 수 있는데 시뮬레이..

[JAVA] Programmers : 등산코스 정하기

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오랜만에 글을 작성한다. 그 동안 꾸준히 알고리즘은 학습하고 있었지만 글 작성을 할 여유가 없어서 작성하지 못했는데 이 문제는 해결 방법을 공유해두면 좋을 것 같아서 작성해보려고 한다. 문제읽기 XX산은 n개의 지점으로 이루어져있는데 각 지점은 1 ~ n 까지 번호가 붙어있고 해당 지점들은 출입구, 쉼터, 산봉우리 중 하나이다. 각 지점으로 이동할 때 등산로를 이용해야하는데 이 때 등산로별로 소요되는 시간이 다르다. 이 때 각 지점에 방문할 때마다 휴식을 취할 수 있는데 휴식 없이 이동해야하는 시간 중 ..