Redddy's Devlog

🔈 문제 +---+ | D | +---+---+---+---+ | E | A | B | F | +---+---+---+---+ | C | +---+ 주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.A, B, C, D, E, F에 쓰여 있는 수가 주어진다.지민이는 현재 동일한 주사위를 N3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N×N×N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오. 📝입력 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의..

데이크스트라 알고리즘 (Dijkstra Algorithm) 최단 경로 알고리즘은 주어진 그래프에서 가장 빨리 도달할 수 있는 길을 찾는 알고리즘이다. 노드를 연결하는 간선에 비용 있어 간선의 갯수가 같다고 하여도 실제 이동시간은 다를 수 있기에 그런 것들을 잘 체크해주어야 한다. 데이크스트라 알고리즘은 음의 간선이 없을 때 정상적으로 작동한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계에서 음의 간선이란 존재할 수 없다. 때문에 GPS 소프트웨어의 기본 알고리즘으로 채택되기도 한다. 데이크스트라 알고리즘의 동작 원리는 인접한 노드중에 가장 비용이 적은 노드를 선택하여 움직이기에 그리디 알고리즘으로 분류된다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화 한다. 방문하지 않은..

🔈 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오. 📝입력 입력..

🔈 문제 안녕하세요~ 저는 오늘 다이나믹 프로그래밍(동적 계획법)을 설명하기 위해 등장한 욱제예요! 다이나믹은 이름이 엄청 거창하지만 사실 이름에 비해 개념은 간단하답니다. 다이나믹의 기본 아이디어는 바로 이전에 계산한 값을 사용해서 (= 이미 계산된 값을 사용해서, 어려운 말로 메모이제이션 한다고 해요) 반복되는 똑같은 연산 횟수를 줄이는 거예요. 예를 들어서, 5번째 피보나치 수열을 구하는 F(5)의 동작 과정을 살펴볼게요. 같은 함수가 불필요하게 많이 호출되는 것을 볼 수 있죠? F(2)와 F(3)을 미리 구해놓고 F(4)를 구할 땐 미리 구해둔 F(2)와 F(3)의 값을 이용하면 불필요한 호출을 줄일 수 있어요. 조금 엄밀하게 이야기 해볼게요. 수학적으로 피보나치 수열은 F(n) = F(n-1) ..

🔈 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇..

🧩문제 해석 이제 이런 문제들을 딱 보면 그래프 관련 문제라는 걸 바로 알아차릴 수 있게 되었다. '빙산 한 덩이가 주어졌을 때'가 조건에 들어가있으니, 무조건 빙산은 주어진다. 그러면 이제 빙산에서 얼음의 위치와 그 얼음 주위 환경을 살피면 된다. 그리고 빙산이 쪼개졌는지 BFS를 통해 확인한다. 🔉 풀이 전 잡담 앞서 말한 문제 해석을 알고리즘으로 구현해내는데에는 성공했다. 첫번째 제출에는 런타임 에러(RecursionError)가 발생했다. 이는 재귀함수가 너무 깊이 들어갈 경우 발생한다. 이땐 당황하지 말고 sys 모듈을 불러와 sys.setrecursionlimit(n) 을 적어주면 된다. 여기서 n은 최대 깊이를 의미한다. sys.setrecursionlimit(10**4) 을 넣어줌으로써 런..

🧩문제 해석 갖고 랜선들을 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를 제대로 다뤄보지 못하여 오늘부터 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 - 파이썬 📕 문제 풀이 후위 표기식으로 문자가 주어졌을 때 연산을 하여 값을 출력한다. 후위표기식이란? 후위표기식은 컴퓨터..