아이테킨의 끄적끄적

DFS문제다. DFS/BFS 탐색문제를 계속해서 풀면서 느끼는건 1. 방문했던 곳을 한번더 방문하지 않기 위해서 적절한 표시를 남기는 방법 2. DFS는 재귀를 이용해서 BFS는 큐를 이용해서 푼다. 이 두가지를 고려하면서 문제를 풀기 시작하면 어느정도 풀리는 것 같다. 처음에는 DFS문제이므로 주어진 값들을 그래프로 그려보고 노드라고 보고 문제를 풀어보려고 했었다. 그런데 자기 자신으로 이어지는 노드들을 고려하는게 생각보다는 까다로웠다. 그래서 그냥 그래프, 노드 이런 개념들은 잠시 접어두고 2차원 배열 그 자체로 보고 문제를 풀기 시작했다. 먼저는 dfs함수를 정의했다. 주어진 좌표평면에서 벗어나지 않으면서 숫자가 1인 곳들을 표시하면서 탐색하는 함수를 만들었다. 그리고 표시를 할 때 각 단지별로 서..

dfs/bfs문제다. 문제를 크게 꼬거나 어렵게 만들지 않은 것 같다. dfs/bfs 둘중에 하나만 제대로 구현할 줄 알면 풀 수 있는 문제인 것 같다. 감염된 컴퓨터의 개수를 구하는 문제이므로 탐색문제에서는 시작점으로부터 방문한적이 있는 노드의 수를 카운팅하면 되는 문제이다. BFS를 이용한 풀이 # 2606번 바이러스 - bfs n = int(input()) m = int(input()) graph = [[0]*(n+1) for _ in range(n+1)] for _ in range(m): a,b = map(int,input().split()) graph[a][b] = graph[b][a] = 1 visited = [0]*(n+1) from collections import deque def bfs..

그리디 문제에서 가장 대표적인 거스름돈 동전 문제이다. # 2720 세탁소 사장 동혁 t = int(input()) coins=[25,10,5,1] for _ in range(t): change = int(input()) change_coin = [] for coin in coins: change_coin.append(change//coin) change -= (change//coin)*coin for i in change_coin: print(i,end=' ')

일단 이 문제는 내 스스로 풀지 못했다. 오늘 임계점에 도달했는지 머리가 돌아가기를 거부한 듯 하다. 지금 안하면 영원히 안하게 될거같아서 어쩔수없이 구글찬스를 썻다..ㅎㅎ 단어수학이라는 문제인데 대문자의 영어알파벳 단어를 입력받고 각 알파벳의 자리수만큼 10의 승수만큼 곱해주어 단어들의 수를 정하고 그 합계의 최대값을 구하는 문제이다 아래의 링크에 들어가보면 문제에 대한 설명이 잘 나와있다. https://jokerldg.github.io/algorithm/2021/03/13/word-math.html 백준 1339번 단어 수학 (python 파이썬) - Tech 백준 1339번 단어 수학 (python 파이썬) March 13, 2021 jokerldg.github.io 코드 # 1339 단어 수학 ..

처음엔 문제를 이해하는것부터 난해했다. 도데체 무슨말인가?? S와 N이 한번에 머리속에서 정리되지는 않았다. 한참을 곰곰히 생각하다가 입력받은 수(S)를 만들어주기 위해서 최대로 많이 필요한 서로다른 숫자가 몇개(N)인지? 이걸 물어보는 문제였다. 그리디(greedy)문제이므로 최대한 많은 숫자를 사용하려면 자연수 중 제일 작은 수인 1부터 더해나가는 것부터 생각을 해보았다. 그리고 더할 만큼 더한뒤에 입력받은 숫자를 맞춰주는 수를 찾아서 넣어주고 그 숫자들의 개수를 카운팅하면 되겠다는 생각을 하였다. 처음 시도한 코드에서는 시간초과가 떳다. 시간복잡도가 O(n^2)가 될 것같다. sum_num 에서 반복 한번 그리고 while문에서 반복 한번이 겹쳐서 실행이 되었으니... 다른 방법을 생각해봐야 한다...

∴다이나믹 프로그래밍에 대한 개념정리 및 예제풀이 마지막으로 DP 정복하는것을 향해서!!! 다이나믹 프로그래밍(Dynamic programming, DP)란? 다이나믹 프로그래밍이란 복잡한 하나의 문제를 간단한 여러개의 중복되는 문제로 나누어 같은 방식으로 풀어 답을 구하는 방법을 말한다. 나는 보통 동적(Dynamic)이라는 용어를 보면 '계속해서 움직이는' 이라는 뜻으로 이해했다. 그러나 여기서의 동적(dynamics)이라는 단어는 DP를 이해하는데 직관적으로 도움을 주지 못하는듯 하다. 뒤에서 언급하겠지만 그보다는 '작은 중복문제들을 기억하며 푼다'라는 의미로 받아들이는 것이 좋을 것 같다. 그래서 앞으론 dyanmic programming보다는 DP라고 부르려고 한다. (사실 이렇게 해야 나도 헷..

가장 기본적이고 DFS/BFS 개념문제라고 생각한다. DFS는 깊이우선탐색이라고 하여 그래프 자료구조를 그려놓고 수직의 방향으로 먼저 탐색하는 방법을 말한다. 재귀 혹은 스택 자료구조를 이용하여서 구현할 수 있다. BFS는 넓이우선탐색이라고 하여 그래프에서 수평방향으로 먼저 탐색하는 방법이라고 이해하면 될것 같다. 큐 자료구조를 이용하여 구현한다. # 1260번 # 입력값을 받는 부분 # 인접행렬로 그래프를 표현하였다. n,m,v = map(int,input().split()) graph = [[0]*(n+1) for _ in range(n+1)] for i in range(n+1): a,b = map(int,input().split()) graph[a][b] = graph[b][a] = 1 # DFS구..

수많은 정렬 알고리즘 중 대표적인 5가지 정렬 알고리즘에 대해서 정리해보려고 한다. 버블 정렬(bubble sorting) 선택 정렬(Selection sorting) 삽입 정렬(insertion sorting) 병합 정렬(Merge sorting) 퀵 정렬(Quick sorting) 셸 정렬(shell sorting) 힙 정렬(heap sorting) 우선 시간복잡도 기준으로 나눠보자 O(N²) 버블 정렬 선택 정렬 삽입 정렬 O(N log₂ N) 병합 정렬 퀵 정렬 셸 정렬 힙 정렬 아래에 있는 정렬들이 일단 시간복잡도가 더 빠르니 성능이 좋은 정렬 알고리즘이라 생각해도 될 것 같다. 그러나 언제나 그렇듯 모든 상황에서 아래의 알고리즘이 더 좋다고 단정지을 수는 없다. 1. 버블 정렬(Bubble s..

ㅂㄷㅂㄷ... ㅂㄷㅂㄷ... ㅂㄷㅂㄷ... 이 문제 푸느라 1시간정도 날린것같다... 삽질을 아주 정성스럽게 열심히 했다...ㅠ.ㅠ 어느정도 삽질을 하다가 생각이라는 것을 좀 했어야 했는데 아무생각없이 삽질만 열심히 해버렸다. 다음부터는 더 생각하면서 문제에 접근해야겠다는 교훈을.. # 7568 덩치 n = int(input()) people = [] for i in range(n): people.append(tuple(map(int,input().split()))) # 각 사람별 딕셔너리를 만들어줌. dictpeople = {} for v in people: dictpeople[v] = 1 people.sort(reverse=True) # 몸무게로 내림차순 정렬 rank = 1 for i in rang..

# 2231 분해합 n = int(input()) cons_num = {} for i in range(1,n+1): num = list(map(int,list(str(i)))) num.append(i) cons_num[sum(num)] = [] for i in range(1,n+1): num = list(map(int,list(str(i)))) num.append(i) cons_num[sum(num)].append(i) if n not in cons_num.keys(): print(0) else: print(cons_num[n][0]) 생성자를 역으로 도출하는 방법이 도저히 생각이 안나서 임의의 숫자가 주어지면 그 숫자까지의 생성자를 모두 생성해낸 다음에 딕셔너리와 리스트를 이용해서 답을 구했다. bru..