거의 알고리즘 일기장

https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 www.acmicpc.net 1. 풀이방법 이 문제의 풀이방법은 세가지이다. 1) 세그먼트 트리를 이용하여 최소높이, 최소높이 인덱스를 빠르게 ..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 www.acmicpc.net 1. 풀이 방법 이 문제는 테스트케이스도 너무 많고 중간에 수열이 계속 바뀌어서 무식하게 풀면 시간초과가 난다. 그러므로 세그먼트..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 1. 풀이 방법 일반적인 dfs풀이 + dfs가 몇번 호출되었나 세어주면 된다. 주의할 사항은 y, x순 입력이 아니라 x, y순 입..

https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다. 아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다. 반면 아래는 올바 www.acmicpc.net 1. 풀이방법 풀이방법 자체는 간단하다. 1) 스티커를 0도, 90도, 180도, 270도 순으로 돌리며 만약 스티커를 붙일수 ..

https://algospot.com/judge/problem/read/SORTGAME algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. 그런데, 같은 수열도 두 가지 이상의 방식으로 정렬할 수 있다. 예를 들어 3 4 1 2 는, 3 4 와 1 2 를 각각 뒤집어 4 3 2 1 을 만든 뒤, 전체를 뒤집어 정렬할 수도 있지만, 4 1 2 를 먼저 뒤집고, 3 2 1 을 다시 뒤집으면 algospot.com 조건 1) 테스트케이스 (1 ~1000) 2) 수열의 길이 (1 ~ 8) 3) 한 수열에 두가지 이..

https://programmers.co.kr/learn/courses/30/lessons/1832 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이방법 이 문제에서 고려해야 할 조건은 1) 우측과 아래만 이동 가능하다. 2) citymap이 0일때는 자유롭게 이동가능, 1일때는 이동금지, 2일때는 직진만 가능. 3) %MOD를 계산시마다 해줄것. 1), 2)의 조건을 쉽게 풀기 위해서 dp배열을 왼쪽에서 오는 데이터 ( fromL ), 위쪽에서 오는 데이터 ( fromT ) 두개로 선언하고 각 조건들에 따라 맞춰서 계산해주면 된다 2. 코드 #i..

진짜 너무멍청하다.. 이제라도 알아서 다행이다.

https://www.acmicpc.net/prfoblem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다. www.acmicpc.net 1. 풀이방법 ex) 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 표가 이렇게 되어있다고 하자. 1) 저 벽으로 감싸져 있는 공간끼리 빨간색은 1번 그룹, 파랑은 2번, 주황은 3번, ..

https://programmers.co.kr/learn/courses/30/lessons/17676 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 방법 이 문제는 고려할게 크게 3가지 였다. 1) 문자열 처리방법 2) 처리시간은 시작시간과 끝시간을 포함 3) string을 double형으로 바꿀때 정밀도 때문의 약간의 오차 1)같은 경우는 그냥 2016-09-15 hh:mm:ss.sss로 인덱스가 고정적이여서 그냥 처음에는 인덱스로 받아와서 풀었었는데 여러 풀이를 찾다보니 밑의 함수를 만들어서 푸는 편이 깔끔한거 같다. vectorstrtok..

https://programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 처음에 완전탐색으로 하나하나 풀었었다. 하지만, 완전탐색으로는 (5*5)+(5/5) 같은 케이스를 도저히 풀어내지 못하겠어서 어떤 블로그를 참고했다. 1. 풀이방법 n = 5일때 cnt value 1 5 2 55 5*5 5+5 ... 3 555 55*5 55+5 ... ... 이 풀이방법은 vectordp에 5 55 555 같은 이어붙인 수들은 따로 넣고 나머지 계산부분들은 for(int i = [..