쑥로그

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net BFS로 쉽게 풀 수 있는 문제였다. 다만 조금 애먹었던 점이 메모리 초과 부분이었다. 익히 알고있는데로 BFS로 풀면 메모리 초과 문제가..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 마지막날까지 최대로 일할 때 얻을 수 있는 최고 수익을 구하는 문제. 처음에는 그리디인가 싶어서 그리디로 풀려고했지만, 결국 이건 답이 있는 문제기 때문에 다이나믹 프로그래밍으로 풀었다. 해법은 일단 일을 하기 시작하면 그 소요 기간만큼은 일할 수 없다는걸 가정하는것. 0. 퇴사날 이후로는 일을 할 수 없기 때문에 그 날에 걸리는 일들은 전부 -987654321로 처리했다. 1. 일 수를 돌면서 2. 그날 일을 한다면 소요기간만큼 건너 뛰고 그 다음 날부터 모든 일에 일을 할 수 있으므로 그날 일했을때 얻을수 있는 비용과 비교해서 최..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 풀이방법은, {10, 20, 10, 30, 20, 50} 일 때 10 10 20 10 20 30 10 20 50 10 20 30 50 이렇게 이전에 갔던 길을 저장하고 있는 것이다. 처음에 재귀로 풀었다가 시간초과가 났다. 재귀도 결국 이전에 계산 했던 값을 가지고 들어가는 거니까 상관없을 거라 생각..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속된 합중에서 가장 큰 값을 구하는 문제이다. 여기서 키포인트는 한 개 이상의 연속된 값 중에서 찾는 것이다. 문제 속 예제를 생각해본다면, 인덱스 0 0+1 0+1+2 0+1+2+3 ... 0+1+2+3+...+8+9 이다. 0+1, 0+1+2 등 공통된 부분이 자꾸 더해지므로 재사용하는 것이 좋다. 처음엔 이 값들을 배열에 저장하고 있을까 하다가 결국 합이라서 그렇게까지 할 필요가 없을 것 같았다. 왜..

1주차 분할정복 문제로 울타리 자르기 문제를 풀었다. https://algospot.com/judge/problem/read/FENCE algospot.com :: FENCE 울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 algospot.com 아이디어가 잘 떠오르지 않아서 고생했다. 원래같으면 fo..

기간 : 2019년 8월 21일 ~ 2019년 10월 31일 (총 72일) 목표 : 알고리즘 개념을 다시 정리한다 + 알고리즘 26문제 + 하루 1시간 체크 : 삼성 알고리즘 시험 사용 알고리즘 사이트 : acmicpc.net, swexpertacademy.com, algospot.com 공부 참조 : 종만북, zerocho.com, swexpertacademy.com, 코딩인터뷰 방향 : git에 개념과 알고리즘을 커밋하고 공유한다. 시간복잡도와 공간복잡도를 함께 계산하고, 더 나은 방향을 논의한다. 커리큘럼 (13챕터) 분할 정복 설명 + 퀵정렬 본문제 1. 난이도 하. 쿼드 트리 - www.acmicpc.net/problem/1992 본문제 2. 난이도 중. 울타리 잘라내기 동적 계획 1 설명(메모..

기존부터 알고리즘은 꾸준히 풀고있었지만 최근 들어와서 안풀고있다. 여러 이유가 있긴 하지만 그래도 최소한으로 지키고 있던 1주일 2문제는 무너진지 오래 ㅜㅜ 그래서 아예 커리큘럼을 짜서 움직이면 어떨까 해서 어제부터 부지런히 작성중인데, 구체적이지 않아서 영 맘에 들진않는다. 하지만 일단 시작해보는걸로 한다! 1주차 - 분할정복 분할정복의 개념과 장점, 문제를 봤을 때 분할정복으로 풀어야 하는 포인트를 러프하게 정리해보았다. 커리큘럼-- 1. 개념 설명 2. 대표적인 예제 설명 - 퀵 정렬 3. 다른 예제 풀어보기 - 쿼드 트리 4. 숙제 https://github.com/mychum1/shelf/blob/master/com.ksko.algorithm/src.main.java/basic/divideAnd..