![]()
Question: https://leetcode.com/problems/roman-to-integer/ Roman to Integer - LeetCode Can you solve this real interview question? Roman to Integer - Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just tw leetcode.com 이게 좋은 풀이인지는 모르겠는데;; 일단 쌩 구현으로 제출해서 accepted 된..
https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 단순하게 벽을 부수는 횟수를 카운트 하다가 오답이 계속 나왔는데 이를 해결하기 위해서 새로 탐색하는 칸이 벽인 경우와 통로인 경우의 가중치를 다르게 주어야 한다. 1) 통로 : 벽을 부수지 않아도 통과하여 이동할 수 있으므로 가중치가 높다. 덱 (deque) 의 앞쪽으로 밀어넣는다 2) 벽 : 벽을 부수어야 하므로 가중치가 낮다. 덱 (deque) 의 뒤쪽으로 밀어넣는다 # ..
이진수로 변환하고 -> 이진수를 표현하는 포화 이진 트리를 만들고 -> 포화 이진 트리를 탐색 하는 총 3가지의 로직을 구현해주면 되는 문제이다. 트리 란 비선형 자료구조들 중에서 자료 간 (= 노드) 계층 관계를 가진 자료구조이다. 포화 이진 트리란 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 노드로 차있는 트리이다. 또한 각 노드들이 2개의 자식 노드들을 가지며, 홀수 개의 자식 노드를 가질 수 없다. 즉, 자식 노드가 0개이거나 2개이다. # 포화 이진 트리를 탐색 def check_tree(binary): root = len(binary) // 2 # mid if root == 0: # leaf node return True if binary[root] == '0': if '1' not in ..
https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이것이 누적합이다 !! 를 보여주는 문제이다 ㅋㅋㅋ 단순하게 구현하면 시간초과가 나므로 누적합을 이용하여 degree 값을 미리 계산해두고 board에 더해주면 된다. def solution(board, skill): answer = 0 n = len(board) # col m = len(board[0]) # row dp = [[0] * (m+1) for _ in range(n+1)] for t,..
![]()
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 와 ~~ 상당히 어려운 재귀인 것 같다 문제를 읽어봤을 때 얻을 수 있는 힌트는 간단하다. 프로젝트 팀이 형성되는 경우는 그래프 구조에서 cycle이 형성되는 상태이다. 따라서 cycle 을 형성하기 위하여 node 들이 이어져있는 관계를 파악해야 한다. 예를 들어서 문제 예시에서 팀을 이루는 (4, 7, 6) 을 살펴보자. 1. visited node 4를 아직 방문하지 않았으므로 4에 대해 방문처리..
https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 1. 첫번째 시도 -> 메모리 초과 발생 256MB int형 == 4Byte 1KB == 1024Byte 1MB == 1024KB 256MB = 256 * 1024KB = 256 * 1024 * 1024B = int형 256 * 1024 * 1024 / 4Byte = 67108864개 [아이디어] 2차원 배열 dp 를 생성하고 여기에 i부터 j 까지..
https://school.programmers.co.kr/learn/courses/30/lessons/214288 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 : 구현 + priority queue 활용하기 import heapq from itertools import combinations_with_replacement from collections import defaultdict def solution(k, n, reqs): answer = int(1e9) # 기다린 시간의 최솟값 type_list = defaultdict(list) ..
https://www.acmicpc.net/problem/6051 6051번: 시간 여행 모범생 현수는 코딩하는 시간을 늘리기 위해 타임 머신을 구매 했다. 현수는 정상적으로 문제를 코딩하거나 (타임 머신을 사용하지 않고), 과거의 임의의 지점으로 시간여행 할 수 있다. 미 www.acmicpc.net 메모리 초과 발생 풀이 .. 나이브하게 풀면 메모리 초과가 발생한다 ㅠㅠ # https://www.acmicpc.net/problem/6051 import sys import copy input = sys.stdin.readline N = int(input()) query = [] log = [[]] # 모든 기록 stack = [] # 가장 최근에 푼 문제 = 스택 맨 위 for idx in range(..
