개발하는 개구리

🐸 문제 정보 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 🤖 알고리즘 슬라이딩 윈도우 ⏱️ 풀이 시간 14.58m 📝 풀이 최근에 투포인터랑 슬라이딩 윈도우를 많이 풀어서 쉽게 풀 수 있었다. start = 0, end = k로 시작한다. (어차피 k개는 필수로 들어가야하기 때문) 이때 사이에 있는 1의 값은 미리 카운트하여 선언한다. end가 n이 될 때까지 아래 조건에 따라 인덱스를 움직이며 계산한다. 1의 개수가 k개와 같다면 현재 거리를 res와 비교하여 최솟값으로 저장한다 start 인덱스에..

🐸 문제 정보 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 🤖 알고리즘 누적합 ⏱️ 풀이 시간 13.22m 📝 풀이 그래프를 그려보고 누적합 테이블을 구하는 원리와, 답을 찾는 원리를 알아냈더니 쉽게 풀 수 있었다. 누적합 테이블 구하기 pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] 구간 합 구하기 pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 ..

🐸 문제 정보 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 28.16m 📝 풀이 백트래킹으로 풀면 되는 문제였다. 새로운 배열을 복사해서 전달해주는 방식보다는, 기존 배열 하나에서 재귀 시킨 후 다시 원상 복구 해주는 방식으로 진행했다. 아래 조건만 잊지 않으면 어렵지 않게 풀 수 있는 문제였다. 계란을 첫 인덱스부터 탐색하지만, 이미 깨져있는 경우나 본인인 경우는 패스해주는 것 깰 계란이 없으면 그냥 넘겨줄 것 본인이 이미 깨져있으면 그냥 넘겨줄 것 🧑‍..

🐸 문제 정보 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 🤖 알고리즘 DFS ⏱️ 풀이 시간 07.51m 📝 풀이 MST 같아 보이지만 DFS 문제이다. 입력 값을 바탕으로 양방향 그래프를 만들어주고, 방문했는지 체크할 visited도 만든다. 이후 그래프를 돌면서, 연결된 노드는 모두 방문처리하고, 방문하지 않은 노드에서 다시 dfs를 시작할 경우 결과 값에 1 더해준다. 🧑‍💻 나의 답 # pypy3 import sys input = sy..

🐸 문제 정보 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 36.01m 📝 풀이 문제가 엄청 복잡해보여서... 무조건 시간초과 or 메모리초과 날거라고 생각했는데 다행히 그렇게 복잡한 문제는 아니었다. 영역 구분할 때 초기 값에 uni를 넣어주는 것을 깜빡해서 1트는 실패했다ㅠ 입력값을 BFS 돌면서 영역 구분 구분된 영역을 돌면서, 사방에 바다가 있는 경우 bfs 시작 dist 리스트를 통해, 다른 영역까지의 거리를 1씩 더해줌 만약 돌다가 다른 영역 만나면 현재 저장된 거..

🐸 문제 정보 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 🤖 알고리즘 스택 ⏱️ 풀이 시간 23.55m 📝 풀이 확실히 닉값하는(?) 문제였다. 골드 4 치고는 쉬운... 그림을 그리면서 풀어봤더니 어렵지 않게 이해가 됐다. 우선 입력값을 받되, y값만 신경쓰면 된다. 이 y를 스택에 담아주는데, 아래 세 가지 조건에 따라 res 값 처리가 달라진다. 스택의 마지막 값보다 큰 값인 경우 새로운 건물이므로, res에 1을 더한다 스택의 마지막 값보다 작..

🐸 문제 정보 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 47.05m 📝 풀이 완전 대기업 코테에서 나올 것 같은 문자열 + 빡구현 문제였다...! 좋은 문제인둣...! 조건을 나눠서 그에 맞게 구현하면 되는 문제이다. 각 판에서 x는 5개, o는 4개가 최대이며, 이보다 더 많이 있다면 무조건 invalid x가 먼저 시작하기 때문에, x가 o보다 1개 많거나 같아야한다. x가 o와 같은 개수라면, o가 이기는 경우로 끝나야 유효하다. x가 o보다 1개 더 많다면, ..

🐸 문제 정보 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 22.24m 📝 풀이 공을 양 끝으로 옮긴다는 아이디어는 쉽게 얻을 수 있지만, 역시 이를 구현하는 과정이 어려운 문제였다. 한 번 틀리고 검색의 힘을 빌렸음에도 대부분의 블로그에서 아이디어에 대한 이야기만 하고 있을 뿐 공을 옮기는 수에 대한 이야기는 거의 하지 않고 있었다.. 헷갈린다면 아래 방법을 잘 읽어보면 도움이 될 것 같다. 우선 주어진 입력에서 red와 blue의 개수를 찾..

🐸 문제 정보 4659번: 비밀번호 발음하기 좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtp www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 22.01m 📝 풀이 실버 5임에도 구현이라 체감상 실버 2~3으로 느껴졌다. 문제에서 제시한 조건대로 빡구현하는 되는 문제였다. 모음의 경우 딕셔너리로 설저해놔서 시간복잡도를 줄였다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline gather = {'a': True, 'e': True, 'i': True, 'o': True, 'u': True} while ..

🐸 문제 정보 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 🤖 알고리즘 누적합, 투포인터 ⏱️ 풀이 시간 12.12m 📝 풀이 누적합으로 풀면 간단하지만, 구할 수 없는 경우 0 출력 처리 때문에 약간의 시간 낭비를 했다. 주어진 입력 리스트를 누적합으로 만들고, 투포인터를 돌면서 아래 조건에 따라 처리하면 된다. start와 end 사이의 합이 s보다 크거나 같다면, 길이에 대해 최소값 처리를하고 start를 뒤로 한 칸 이동 start와 end 사이의 합이 s보다 작다면, end를 뒤로 ..