개발하는 개구리

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

🐸 문제 정보 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가 있..