Redddy's Devlog

🧩문제 해석 갖고 랜선들을 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 =..

※ 그래프 사진은 직접 그려서 추가예정! 갤럭시 탭이 오면 그걸로 그려야지ㅎ.ㅎ DFS와 BFS는 모두 그래프 탐색 알고리즘이다. 코딩테스트를 준비하다보면 어느 순간 만날 수 밖에 없는 알고리즘이다. DFS DFS는 Depth-first Search의 약자로 깊이 우선 탐색을 의미한다. 그래프의 가장 깊은 곳 우선으로 탐색을 하는 알고리즘이다. 스택 자료구조를 사용하여 그래프를 탐색한다. DFS의 탐색과정은 다음과 같다. 탐색 시작 노드를 스택에 넣고, 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그중 가장 작은 값의 인접 노드를 스택에 넣고 방문처리한다. 만약 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때가지 반복..

그래프 : Graph DFS나 BFS는 모두 그래프 순회 알고리즘, 그래프 탐색 알고리즘이다. 그렇다면 그래프에 대해서 자세히 짚고 넘어가자. 우선 알고리즘에서의 그래프는 우리가 흔히 사용했던 막대그래프나 주식그래프 같은 형태가 아니다. 그래프는 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다. 노드와 노드가 간선으로 연결되어 있다면 두 노드는 인접해있다고 한다. 그래프 탐색은 하나의 노드를 시작으로 인접한 노드를 방문하는 것을 말한다. 그래프를 표현하는 방법은 크게 두가지가 있다. 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결관계를 표현하는 방식 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현하..

😀 서론 DFS를 제대로 다뤄보지 못하여 오늘부터 DFS, BFS 문제 하나씩은 풀 예정이다! 그래서 도전해본 문제는 "바이러스" 전에 스터디때 도전하였다가 실패한 문제이다. 그때는 DFS와 BFS의 개념을 잘 몰랐기에 실패하였으나, 이제는 다르다!ㅎㅎ 📕 풀이 주어진 컴퓨터의 수로 리스트 컴프리헨션으로 그래프를 만들고 그 후에 주어지는 인풋 값을 각자 위치에 넣어준 뒤 DFS를 돌렸다. 💻 코드 import sys input = sys.stdin.readline # dfs 정의 def dfs(graph, v, visited): visited[v] = True for i in graph[v]: if not visited[i]: dfs(graph, i, visited) com = int(input().rs..

😀 서론 사실 저번주에 후위표기식 관련 문제를 풀었었다. 요기! 개념은 이해했으니 날로먹을 생각으로 골드 3에 도전했다가 보기좋게 실패했다ㅎ.ㅎ 위의 문제하고 이번 문제의 차이점은 순서이다. 후위 표기식2번 문제는 후위표기식을 중위표기식으로 바꾸어 값을 계산하는 거였다면, 이번 문제는 중위표기식을 후위표기식으로 바꾸기만 하면 되는 것이었다! 중위표기식을 후위표기식으로 변경 후위표기식을 중위표기식으로 바꾸고 값을 출력 이렇게 봤을 때 후자가 더 어려울 것 같지만,, 중위표기식을 후위표기식으로 바꾸려면 괄호치는 작업을 해야한다. 이게 난관이었다... [백준] 1935번: 후위 표기식2 - 파이썬 📕 문제 풀이 후위 표기식으로 문자가 주어졌을 때 연산을 하여 값을 출력한다. 후위표기식이란? 후위표기식은 컴퓨터..

📕 풀이 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. 피연산자가 들어..