개발하는 개구리

🐸 문제 정보 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를 뒤로 ..

🐸 문제 정보 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 18.31m 📝 풀이 쉬운 구현 문제였다. 뒤에서부터 순회하면서 아래 조건대로 정답 리스트에 (인덱스 + 1)을 추가해주면 되는 문제였다. 왼쪽에 나보다 큰 사람이 없다면, 정답 리스트 가장 왼쪽에 (인덱스 + 1) 추가 왼쪽에 나보다 큰 사람이 있지만, 내 순서가 정답 리스트의 길이보다 작다면, 내 순서가 될 자리에 (인덱스 + 1) 추가 왼쪽에 나보다 큰 사람밖에 없다면, 정답 리스트 가장 오른쪽에 (인..

🐸 문제 정보 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 🤖 알고리즘 우선순위 큐 ⏱️ 풀이 시간 22.33m 📝 풀이 구현처럼 풀다가 실패해서 검색으로 아이디어를 얻었다. 우선순위 큐로 푸는 문제였고, n*n이기 때문에 큐의 범위를 n만큼 유지한다면 마지막 줄까지 돌았을 때 0번째에 위치한 원소가 n번째 큰 수가 되었다. 오늘은 집중이 잘 안되는 날이다ㄷㄷ 🧑‍💻 나의 답 # pypy3 import sys, heapq input = sys.stdin.readline n = int(input().rstrip()..

🐸 문제 정보 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 🤖 알고리즘 그리디 ⏱️ 풀이 시간 failed 📝 풀이 dp로 풀다가 도저히 모르겠어서 찾아보니 그리디였다........ 그리디로 푸는 방법은 생각보다 간단했다. 직전 전구만 비교하되, 첫 번째 전구의 경우에는 직전 전구가 없기 때문에 첫번째 전구를 건들지 않고 시작한 경우와 / 첫번째 전구를 건들고 시작한 경우 두개로 나눠서 비교하면 되는 문제였다. 🧑‍💻 나의 답 import sys input = sys.stdin..

🐸 문제 정보 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 🤖 알고리즘 스택 (이라고 적혀있지만 구현에 가깝다) ⏱️ 풀이 시간 30.25m 📝 풀이 보자마자 스택 문제인 것은 알았지만, 스택보다는 구현에 가까운 문제였다. 가장 높은 지점을 기준으로, 왼쪽 오른쪽에서 최대값은 의미가 없다는 것을 알아야했다. 때문에 입력 값에서 가장 높은 지점의 인덱스를 찾은 후, 그 지점을 기준으로 왼쪽 오른쪽 각 1회씩 탐색하면서 스택 형태로 값을 더해주면 되는 문제였다. 문제에서 모든 인덱스에 h가 있..

🐸 문제 정보 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 failed 📝 풀이 이번 문제는 점화식을 끝내 찾지 못하고 검색의 힘을 빌려 풀었다. DP는 DP인걸 알아도 점화식이 안떠오르면 손도 델 수 없는게 너무 슬프다... 풀이는 다른 블로그를 참고했다. 간단히 요약하자면 아래와 같다. 기본적으로 1로만 구성된 경우는 각 숫자마다 1개씩 존재함 숫자 2부터는, (본인 - 2)에서 숫자 1로만 구성된 경우가 곧..