221. Maximal Square https://leetcode.com/problems/maximal-square/ Maximal Square - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 조건 및 풀이 1과 0으로 이루어진 2차원 배열이 주어졌을 때, 1로만 채워진 최대 크기의 정사각형을 구하는 문제. 떠올릴 수 있는 가장 간단한 방법은 모든 경우의 수를 다 구해보는 brute force 방식이다. 이렇게 풀더라도 문제를 통과할 수는 있다고 한다. 맨 좌측 상단부터 크기가 1, 2.... 2021. 7. 13. 1423. maximum points you can obtain from cards https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/ Maximum Points You Can Obtain from Cards - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 조건 및 풀이 배열의 양 끝 숫자 중 하나를 포함하는 길이 k의 연속된 부분 배열 중 그 합이 최대가 되는 부분 배열을 찾는 문제. 배열의 길이가 N이라고 할 때, N - k에서부터 k개 요소의 합을 구한 다.. 2021. 7. 12. [BOJ 17822] 원판 돌리기(C++) https://www.acmicpc.net/problem/17822 시뮬레이션 + bfs(?) 로 풀리는 간단한(?) 문제. 다음과 같은 방법으로 풀 수 있다. 1. 원판을 돌린다. 이 때 반시계방향으로 k번 돌리는 것은, 시계 방향으로 M-k번 돌리는 것과 같기 때문에 시계 방향으로 돌리는 것만 구현했다. 효율적인 방식은 아니지만 빠르게 구현하기 위해서(^^;)... 2. 각 지점에서 bfs를 돌면서 인접한 수가 같은지 확인한다. 같은 수는 모두 0으로 바꾸어준다. 2-1. 인접한 수가 모두 다르다면 전체 수의 평균을 구한 다음 조건에 따라 1을 더하거나 빼준다. 3. T회 반복한다 전체 코드 더보기 전체 코드 #include #include using namespace std; int N, M, T,.. 2019. 12. 2. [BOJ 15686] 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 처음으로 1시간 내에 문제를 풀어봤다 ㅠ0ㅠ 삼성에 여러번 기출로 등장한 DFS 문제라서 쉽게 풀 수 있었다. 문제 분류는 브루트 포.. 2019. 4. 13. [BOJ 16236] 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net https://www.youtube.com/watch?v=761ae_KDg_Q 문제 푸는 내내 이 노래가 머릿속에 맴돌았다 아기상어.. 2019. 4. 9. [BOJ14889] 스타트와 링크 완전탐색 문제로 모든 경우의 수를 다 고려해야 하는 문제 두 팀의 능력치 차이만 구하면 되므로, 첫번째 사람은 무조건 스타트 팀에 속한다고 가정하고 2~N번째 사람을 DFS를 돌려서 답을 구할 수 있다 teamA(직관적이지 못한 변수명이다ㅠㅠ) 배열의 각 요소를 해당 사람이 A팀에 속했는지 여부라고 둘 수 있다. 만약 세 사람이 있다고 하면(| 아래는 각각의 상태에서 다시 DFS로 탐색할 경우) (0)() | (01)(), (02)(), (03)() | (012)(), (013)(), (014)() ... 같은 라인에서는 for문을 사용해서 한 명씩 할당한다. 할당한 다음에는 다시 탐색을 시작해 다음 사람을 정하고 정확히 인원수의 절반을 A팀에 할당했다면 능력치 합을 구하는 base case로 넘어가도록.. 2019. 3. 28. 이전 1 2 다음
