Redddy's Devlog

🧩문제 해석 F = 스타트링크 건물 층의 총 계수 S = 현재 강호의 위치 G = 스타트링크의 위치 U = 위로 올라가는 엘레베이터 층의 간격 D = 아래로 내려가는 엘레베이터 층의 간격 위 사항들이 주어졌을 때, 현재 강호의 위치에서 스타트링크의 위치로 엘레베이터로 가려 할 때, 누른 버튼의 최소값을 출력하는 문제이다. 만약 도달할 수 없다면, 계단 이용하라는 문장을 출력한다. 모든 층을 돌아다닐 필요가 없고 목표층에 도달하면 엘레베이터를 멈추면 되니까 BFS가 효율적이다. 📕 풀이 BFS로 풀었다. 이동할 수 있는 층은 [현재 위치 + U, 현재 위치 -D] 를 통해 유추하였고, 이 데이터가 F 안에 있고, 방문한 적이 없다면, 그 층으로 방문하였다. 💻 코드 from collections impor..

🧩문제 해석 체스 판의 크기와 현재 나이트의 위치 그리고 목표 위치가 주어졌을 때 최소 이동 횟수를 출력하는 프로그램! 📕 풀이 나이트의 이동 가능 경로는 다음과 아래의 그림과 같다. 최소 이동 횟수를 구하려면 이전에 방문 했던 곳은 지양한다. 그리고 체스판에서 벗어나는 위치도 제외한다. 이 두가지를 지키면서 BFS 탐색을 하였다. 칸을 모두 방문하는 것이 아니라 목표 위치에 도달하면 탐색을 멈출 것이기에 DFS 보다 BFS가 더 효율적이다. 💻 코드 import sys from collections import deque input = sys.stdin.readline # 나이트 이동 경로 dx = [-2,-1,1,2,2,1,-1,-2] dy = [1,2,2,1,-1,-2,-2,-1] def bfs()..

🧩문제 해석 떡 하나 주면 안잡아 먹지!~ 에서 아이디어를 얻은 문제 같다 ㅋㅎㅎ 문제가 재밌었다. 호랑이가 오늘 먹을 떡의 갯수는 1일전하고 2일전에 얻은 떡을 더한 갯수이다. 이 글을 보면 바로 피보나치 수열이라는 것을 눈치챘을 것이다. n번째 날 먹은 떡에 갯수 k가 주어졌을 때 첫째날하고 둘째날에 먹은 떡에 갯수를 출력하는 문제이다. 📕 풀이 피보나치라는 것을 파악하자 문제 풀기는 쉬워졌다. 첫째날에 먹은 떡의 갯수가 a, 둘째날에 먹은 떡의 갯수를 b라고 할 때 아래의 표를 살펴보자. 날짜 1 2 3 4 5 6 떡의 갯수 a b a+b a+2b 2a+3b 3a+5b 첫째날에는 a개, 둘째날에는 b개, 셋째날에는 첫째날과 둘째날을 더한 a+b개를 먹었다. 그리고 네째날에는 둘째날과 셋째날을 더한 ..

🧩문제 해석 갖고 랜선들을 k개의 같은 길이의 랜선으로 자르되, 자른 랜선쪼가리들은 다시 사용할 수 없다. 이때 만들 수 있는 최대 길이의 랜선을 구하는 문제이다. 📕 풀이 숫자 범위가 심상치 않다. 갖고 있는 랜선의 수가 백만개이고, 랜선이 길이는 2^31-1 보다 작은 자연수이다.ㅎ 일반적으로 접근했다가는 시간초과날 것이 분명하다. 이 문제는 이분탐색으로 풀어야 한다. 첫번째 아이디어! 가지고 있는 랜선중 최소값을 찾는다. 최소값 랜선을 end 값에 두고 이분탐색을 한다. 탐색 값들을 리스트에 저장하고, 최종적으로 그 리스트의 최대값을 출력한다. 최소값랜선을 end 값에 둔 이유는 최대값랜선을 end 값에 둔다 하여도 결국에는 최소값랜선에 올 것이라고 생각했다. 물론 맞는 말이긴 하다. 그러나 생각하..

🧩문제 해석 채팅방에서 사용한 임티갯수를 출력하면 되는 문제였다. 사람들은 새로운 사람이 들어왔을 때 임티를 사용하고 그 다음은 일반 대화를 이어나간다. 즉, 새로운 들어왔을 때 사용한 임티 갯수를 전부 더해주면 되는 문제이다. 📕 풀이 dict() 자료형을 사용하여 문제를 풀었다. 새로운 사람이 들어오면 dict()의 값들을 리셋해주었다. 💻 코드 import sys input = sys.stdin.readline cnt = 0 # 임티갯수 변수 user = {} # 이름과 임티사용을 확인할 변수 for i in range(int(input().rstrip())): # 채팅방의 기록수만큼 for문을 돌린다 # 채팅내용입력받음 s = input().rstrip() # 새로운 사람이 들어왔을때 if s =..

📕 풀이 A와 B와 C가 공백을 두고 입력된다. 우리는 (A^B)%C 값을 출력하면 된다. 단 A,B,C 는 모두 2,147,483,647 이하의 자연수이다. 수의 범위가 방대하다. 때문에 21억번 곱한다면 O(N)이여도 시간초과가 날 것이다. 그래서 나머지 분배법칙과 지수법칙을 사용하여 답을 구하였다. 📖 지수법칙 (A^m)^n = (A^(m * n)) 📖 나머지 분배 법칙 (AxB) % C = (A%C) * (B%C) % C 우선 지수 법칙을 사용하여 분할 정복을 한다. 2 ^ 32 의 값을 계산하는 방법은 2를 32번 곱하는 방법도 있지만 지수법칙을 사용하여 (2^16)^2 16번 곱한 것을 제곱하는 방식으로 하면 총 17번의 연산으로 줄일 수 있다. 이 방법을 계속 사용하면 10번, 연산 7번만에..

📕 풀이 제목처럼 집합을 사용해서 풀면 되는 문제이다. 처음에는 차집합을 이용하여 풀이 하였으나 오답으로 처리되었고, 바로 떠오른 다른 방법은 하나하나 체크해주는 방법이었다. 💻 코드 import sys input = sys.stdin.readline n,m = map(int,input().rstrip().split()) cnt = 0 s = set() check = set() for i in range(n): s.add(input().rstrip()) # 기준이 되는 집합 for j in range(m): word = input().rstrip() if word in s: # 기준 집합에 새로 새로 입력된 문자가 있다면 카운트 cnt += 1 print(cnt) 📎 문제 링크 : 문자열 집합 14425..

📕 풀이 정렬 후 투포인터를 사용하여 a의 값 하나를 b의 값 전부 하나하나 비교해가면서 a의 값이 클때의 갯수를 카운트 해준다. 💻 코드 import sys input = sys.stdin.readline for i in range(int(input().rstrip())): # a와 b의 갯수를 입력받음 a, b = map(int, input().rstrip().split()) # a와 b 정보를 입력받음(생명체 A, B) a_num = list(map(int, input().rstrip().split())) b_num = list(map(int, input().rstrip().split())) # 내림차순 정렬 a_num.sort(reverse=True) b_num.sort(reverse=True) ..

📕 문제 풀이 후위 표기식으로 문자가 주어졌을 때 연산을 하여 값을 출력한다. 후위표기식이란? 후위표기식은 컴퓨터가 연산할 때 사용하는 방법이다. 우리가 연산할 때 사용하는 (3*4+6)/2 이런 식들은 중위표기식이다. 후위표기식과 중위표기식의 차이는 바로 연산자의 위치이다. 연산자란 + , -, *, / 와 같은 것들이고 피연산자는 숫자나 문자로 이루어져있다. 후위표기식을 중위표기식으로 바꾸는 과정에는 스택 자료구조를 사용한다. 반대로도 마찬가지! 중위표기식 5*(3*4+6)/2을 후위표기식으로 바꿔보자!! 중위표기식을 후위표기식으로 변환과정 1. 중위표기식 연산 하나하나마다 괄호를 씌어준다. 5*(3*4+6)/2 => ((5*((3*4)+6))/2) 2. 왼쪽괄호가 들어오면 무시 3. 피연산자가 들어..

⚽ 서론 dict() 형 그러니까 해시를 사용한 집합과 맵에서 새로운 걸 발견해서 글로 남기기로 했다! 🧩문제 해석 포켓몬 이름을 받은 뒤 받은 순서대로 포켓몬 도감에 저장한다. 포켓몬 이름을 문제로 냈을 때 그 포켓몬이 몇번째로 도감에 등록됐는지 출력하고, 수를 입력했을 때는 그 수의 등록된 포켓몬 이름을 출력하면 되는 문제 (걸그룹 마스터 문제랑 비슷한 유형이다) 📖 풀이 처음에는 포켓몬 이름을 입력받으면 key에는 이름을, value에는 수를 저장한 다음 문제를 맞출 때 이름이 들어오면 포켓몬도감[이름] 이런식으로 출력하면 됐지만 수가 입력될 때는 값을 하나하나 찾아야 했다. 즉 key가 입력되면 바로 찾을 수 있지만 value가 입력되고 key 값을 찾으려면 하나하나 다 돌아야 했었다. value..