Redddy's Devlog

그래프 : 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. 피연산자가 들어..

🎶 서론 어렸을 때 유행했던 노래 왓더뽞쎄에서 영감을 얻은 문제같다ㅋㅋㅋ 오랜만에 다시 노래 들어보니 여전히 재밌고 힙한 노래다. 약간 다른의미로 천재랄까 🧩문제 해석 주어진 문자열중에서 몇개의 단어들을 제거하면 되는 단순 파싱문제였다. 📖 풀이 1. 녹음된 소리를 문자열로 받는다. 2. 다른 동물들의 울음소리를 ano_ani 라는 set에 저장한다. 3. 녹음된 소리중 ano_ani에 있으면 여우의 소리가 아니고 다른 동물의 소리란 것을 의미하니 그것을 제외하고 출력한다. 💻 코드 import sys input = sys.stdin.readline ano_ani = set() t = int(input().rstrip()) for i in range(t): record = list(map(str, inp..

친구랑 둘이 닥스2 개봉일날 바로 심야로 달렸다! 23시 영화였는데 코로나 이후 처음으로 보는 심야영화였다 그리고 with 팝콘!! 완다 진짜 간지철철이다. 드림워킹할 때 완다는 그냥 가만히 있어도 내뿜는 카리스마가 장난아니었다. 아메리칸 차베즈라는 새로운 등장인물도 나왔는데 앞으로가 기대되는 캐릭터였다 (이름은 맘에 안들지만ㅎ) 좀비닥스랑 찐닥스랑 싸울 때 음악이 나왔는데 중간중간에 꽤 유명한 클래식 곡들의 모티브가 조금씩 울려 펴졌다. 멀티버스 이동씬도 CG 입히느라 엄청 많은 시간이 들었을 것 같다. 드론이 잠깐 보이는 구간도 있었는데 아마 과학이 발달한 멀티버스였을까?ㅎㅋ 아아 그리고 그 일루마니티 그룹(?)이라고 해야하나 그분들은 완다한테 픽픽 죽어대니까 뭔가 왜 등장시켰지라는 의문을 남겼다. ..

🔗 문제링크 : 분수찾기 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 📕 문제 풀이 문제 풀이 하기전에 조금 주저리 주저리 하자면,,, 요즘 조금 바빠서 글 올리는 빈도수가 조금 줄었다. 그래도 하루에 하나씩은 올리려고 노력하고 있움!!! 파스칼의 삼각형(?) 과 비슷한 방향으로 움직이는데 한번은 오른쪽으로, 한번은 왼쪽으로 이런식으로 반복한다. 그리고 분수의 숫자들은 분자 + 분모 값이 하나씩 증가한다. 이 점을 이용하여 코드를 짰다. 💻 코드 div = [i for i in range(1, 4473)] n = int(input()) cnt = 1 for d in div: if n - d