브루트포스의 기본은 슬라이딩 윈도우(sliding window)

1. 문제 1120번: 문자열 (acmicpc.net) 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 2. 풀이 생각보다 어렵다... 첫번째 문자열에 앞에 알파벳 넣어보고... 혹은 뒤에 알파벳 넣어보고... 두번째 문자열과 길이가 같아질때 비교해서 서로 다른 문자의 개수 세보고... 그러면 26개 알파벳 리스트 만들어서 중복조합으로 길이 차이만큼 뽑아서 앞 뒤로 넣어보고 비교해보나..?? 두 문자열 길이의 차이가 k이면.. k개 모두 임의의 알파벳 26개 앞에 넣어보..

• format_list_bulleted 슬라이딩 윈도우
• · 2023. 1. 28.
• textsms

성실하게 시뮬레이션 구현하기.. -로봇 청소기-

1. 문제 14503번: 로봇 청소기 (acmicpc.net) 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 주어진 조건에 따라 움직이는 로봇 청소기가 청소하는 영역의 수를 구하는 문제 2. 풀이 어렵게 생각하지 말고 항상 성실하게 구현하면 풀린다는 마음가짐으로 먼저 문제에서 좌표가 무엇을 뜻하는지를 정확하게 읽어야한다 "지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다." 그러면 (r,c)는 내가 생각하는 좌표로는 (y,x)를 뜻..

• format_list_bulleted 구현,시뮬레이션
• · 2022. 11. 3.
• textsms

잊을만하면 순열조합 연습하기 -치킨배달-

1. 문제 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 어떤 집과 모든 치킨 집 사이 거리의 최솟값을 해당 집의 치킨 거리라고 부르고 모든 집의 치킨 거리의 합이 해당 도시의 치킨 거리이다. 최대 m개의 치킨 집만 선택해서 가능한 도시의 치킨 거리의 최솟값은 2. 풀이 항상.. 문제를 잘 읽어야한다 "어떤 집과 모든 치킨 집 사이 거리의 최솟값을 해당 집의 치킨 거리" 이것부터 제대로 보질 못했는데.. 빨리 봐서 다행이긴해 조합을 구현한..

• format_list_bulleted 브루트포스
• · 2022. 10. 30.
• textsms

DFS로 블록을 만드는 예술적인 방법? -테트로미노-

1. 문제 14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 이차원 배열에 주어진 블록중 하나를 놓아봐서 거기에 적힌 수의 합의 최댓값을 구하는 문제 2. 풀이 항상 이걸 어떻게 해?라고 두려워하지말고 어렵게 생각하지 말고 성실하게 완전탐색을 구현하면 풀린다는 생각으로 심플하게 5가지 블록의 회전,대칭 모든 가능한 경우를 만들어서 모든 좌표에 대해 조사해보면 진짜로 최댓값이 나오긴 해 근데 변수를 어디서 초기화해야하는지, 그런 실수가 쉽게 나오더라 블록의 회전,대..

• format_list_bulleted DFS BFS 정복기
• · 2022. 10. 30.
• textsms

완전탐색 순열과 조합 연습장2 -앞자리에 0이 못오게 하기-

1. 문제1 2529번: 부등호 (acmicpc.net) 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net k개의 부등호가 주어질때, 0~9까지에서 k+1개의 수를 1번씩만 선택해 주어진 부등호 순서를 모두 만족시킬때 이들을 하나로 합친 수의 최댓값과 최솟값을 구하는 문제 2. 풀이 10개중에 k+1개를 선택하는 순열을 검사해서 부등호를 모두 만족시키는지 검사해보고 조건을 만족시키면 최댓값과 최솟값을 갱신한다 어차피 각 수는 1개씩만 사용가능하니까 숫자를 문자열로 다뤄도 될 것이다 숫자문자열끼리 비교하면 맨 앞자리부터 크면..

• format_list_bulleted 브루트포스
• · 2022. 10. 30.
• textsms

경이로운 그리디 알고리즘1 -만들 수 없는 합의 최솟값-

1. 문제 자연수로 이루어진 어떤 수열이 주어질때, 이 수열의 모든 부분수열의 합을 생각해보자 이때 불가능한 합의 최솟값을 구해본다면? 예를 들어 s = [5,1,2]이면, 1,2,3,5,6,7,8은 만들 수 있는데 4를 만들 수가 없다  2. 알고리즘 2-1) 수열을 오름차순으로 정렬한다 2-2) sum = 0로 초기화한다 2-3) 수열을 하나씩 순회해서 그것을 x라고 하자.  sum+1을 만들 수 있는지 확인해본다.  2-4) sum+1 >= x이면 sum+1까지 만들 수 있다. 그러면, sum + x를 sum으로 갱신한다. 2-5) sum+1  이것만 보면 아무리 생각해도 와닿지는 않는다 어떻게 보면 경이롭기까지하다.  진짜 이게 가능한건가? 여러가지 풀이를 보면서 이해해보도록 노력하자  3. 예시..

• format_list_bulleted 그리디 알고리즘
• · 2022. 10. 30.
• textsms