사용한 풀이법 : heap풀이 과정최소값과 그 다음값을 탐색, 계산 후 다시 삽입 => 해당 연산이 조건을 충족할 때 까지 반복되어야 함. 이를 위한 자료구조가 바로 최소힙!1. heapify 메서드를 통해 scoville 리스트를 최소힙으로 초기화2. 항상 최소값을 뽑아내는 heappop 연산을 통해 min1, min2를 설정    이때, min1이 k이상이거나, 더 이상 뽑아낼 원소가 없을때는 반복문 종료3. 삽입할 원소를 계산 후, 힙에 push4. 연산이 완료 될 때마다 +1한 answer를 리턴 풀이 코드import heapqdef solution(scoville, K): answer = 0 heapq.heapify(scoville) while True: min1 =..

해시(Hash)  해시 개념해시란 해시 테이블에 Key와 Value를 매핑해서 데이터를 저장하는 자료구조이다. 주로 데이터 탐색, 삽입, 집계등의 연산을 할때 유용하며, 인덱스 값이 숫자가 아닌 문자열이나 튜플을 때도 유용하다. 하지만 최댓값과 최솟값을 찾는 문제는 자료구조 전체를 탐색해야 하기 때문에 효율성이 떨어진다는 단점이 있다.해시 (Hash) : 임의 값을 고정 길이로 변환하는 것해시 테이블 (Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조해싱 함수 (Hashing Function) : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수해시 값 (Hash Value) 또는 해시 주소 (Hash Address) : Key를 해싱 함수로 연산해서, 해쉬..

트리  트리정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조로, 순환하는 길이 없는 그래프라고 말할 수 있다.루트 노드 (root node) : 트리의 최상단 노드리프 노드 (leaf nodes) : 트리의 최하단 노드 내부 노드 (internal nodes) : 루트와 리프 사이에 위치한 노드부모 (parent) 노드와 자식 (child) 노드 : 정점의 바로 위 노드가 부모 노드, 바로 아래 노드가 자식 노드 (부모의 부모는 조상노드, 자식의 자식은 후손 노드)노드의 수준 (level) :  root로 부터 각각의 노드까지 도달하기 위해 거쳐야하는 간선의 수 (root = level 0)노드의 차수 (degree) : 자식 노드의 수트리의 높이 (height) 또는..

연결 리스트연속된 공간에 데이터를 저장하는 방식인 리스트와는 다르게 연결 리스트(linked list)는 연속적이지 않는 공간에 데이터를 줄줄이 엮어서 저장한다. 연결 리스트는 일반적인 리스트보다 특정 원소의 삽입/ 삭제가 수월하다는 장점이 있지만, 특정 원소를 탐색하는 시간이 길고 요구되는 메모리 공간이 더 크다는 단점이 있다. 따라서 각각의 상황이 요구하는 자료구조를 제대로 파악해서 적절하게 사용하는 능력을 키우는것이 중요하다.연결 리스트의 종류는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다.단일 연결 리스트 - 각 원소가 자신의 다음 원소 주소를 들고 있는 구조이중 연결 리스트 - 각 원소가 자신의 이전, 다음 원소 주소를 들고 있는 구조                       ..

난이도 : 실버2소요시간 :  27m사용한 풀이법 : DP풀이 과정입력받은 문자열을 정수형 리스트 arr[]로 변환dp[]에는 해당 인덱스에서 가질 수 있는 최대값을 넣는다dp[i-1]+arr[i]가 음수일 경우 최대값 생성에 방해가 되므로 해당 dp값은 0으로 초기화원래는 여기서 풀이를 끝낼라했는데 모두 음수일 경우를 고려안하게 생각나서 dp첫번째 조건문 뒤에 arr값을 dp값으로 초기화 해주는 코드 추가 ⇒ 내가 생각해도 좀 후진 코드..ㅎ원래는 max(dp)를 하려했으나 위 코드 추가되면서 max(arr)로 변경다른 풀이입력받은 문자열을 정수형 리스트 arr[]로 변환현재합과 최대합 연산용 변수 선언arr을 돌면서 해당 인덱스와 해당 인덱스에 현재합을 더한 것중 max를 현재합에 대입다시 max연산..

난이도 : 실버2소요시간 : 48m사용한 풀이법 : DP풀이 과정dp용 리스트 선언각 인덱스에는 1로만 표현했을경우의 개수를 넣는다. 즉, 인덱스 번호를 그대로 대입!루프를 돌면서 DP탐색 시작인덱스 번호보다 작은 제곱 수 중에서 가장 큰 값을 찾는다.현재 인덱스 번호에서 해당 제곱 수를 뺀 인덱스 번호에 +1을 한 후, 대소비교를 진행한다.ex) dp[10] = dp[10-33]+1 = dp[1]+1 (11 + 3*3, 2개!)+1을 하는 이유는 앞선 dp[]값에 제곱 수의 경우가 하나 추가되는 것이기 때문작성 코드import mathN = int(input())dp = [x for x in range(N+1)]for i in range(1, N + 1): for j in range(1, int(..

난이도 : 실버3소요시간 : 31m사용한 풀이법 : DP풀이 과정dp용 리스트 선언 후 0으로 초기화dp 리스트는 인덱스 숫자가 1이 되기까지의 최소연산횟수를 저장하는 용도2~n+1까지 루프 실행dp[i] = dp[i-1]+1 : i번째 수는 i-1번째 수의 dp값에 +1을 한것을 디폴트로 둔다만일 i가 2나 3으로 나누어 떨어진다면, i에 2를 나눈 몫의 수에 해당하는 dp값과 디폴트값을 비교하여 최소값을 선택한다 작성 코드n=int(input())dp = [0]*(n+1)for i in range(2,n+1): dp[i] = dp[i-1]+1 if i%2 == 0 : dp[i] = min(dp[i],dp[i//2]+1) if i%3 == 0: dp[i] = m..

난이도 : 실버3소요시간 :  23m사용한 풀이법 : DP풀이 과정dp[1] = 1 => 1 dp[2] = 1+1, 2 => 2 dp[3] = 1+1+1, 1+2, 2+1, 3 => 4 dp[4] = 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1 => 7위의 식을 잘 보면 1로 시작하는 건 곧 1+3 인거라서 3을 이루는 덧셈의 경우의 수, 즉 dp[3]만 알면 됨 2로 시작하는건 2+2라서 dp[2]만 알면되고 3으로 시작하는건 dp[1]만 알면 됨.dp[5]를 예시로 들어보자1+…. 일때는 4를 이루는 경우들만 알면 됨 ⇒ dp[4] == dp[5-1]2+…. 일때는 3을 이루는 경우들만 알면 됨 ⇒ dp[3] == dp[5-2]3+…. 일때는 2를 이루는 경우들만 알..

난이도 : 실버1소요시간 :  1h 17m사용한 풀이법 : DP풀이 과정풀이과정(백트래킹)각 요소[i][j]는 대해서 [i+1][j],[i+1][j+1]만 더할 수 있음해당 위치에서 이동가능한 경로를 인자로 해서 함수 재귀 진행인자가 n과 같아지면 결과갑 리스트에 삽입모든 경우의 수 탐색 후 리스트의 max를 출력하면 정답!!이긴 한데 메모리 초과 뜸풀이과정(DP)위에꺼에서 아래꺼를 더하는 방식이 아닌 아래꺼에서 위에 값을 참조해오는 것으로 변경=>메모리 손실 방지참조 방식은 총 3가지행의 첫번째 인자일 경우, 바로 위 행의 첫번째 인자값에 더하면 됨 ([i-1][0])행의 마지막 인자일 경우, 바로 위 행의 마지막 인자값에 더하면 됨 ([i-1][-1])행의 중간일 경우, 바로 위의 인자값과 왼쪽 대각..

난이도 : 실버2소요시간 :  57분사용한 풀이법 : dfs_재귀, bfs_큐풀이 과정입력받은 n값에 대한 탐색용 배열 생성 후 false 초기화bfs, dfs 각각의 방문 탐색용 배열 생성 후 false 초기화m에 대해 반복문 돌리면서 입력된 값들에 해당하는 인덱스 값 True 변환각각의 행의 값들 중 True값은 연결된 엣지의 번호를 뜻함ex) 1번 행의 3,4열이 true이면, 1-3/1-4 연결된 것!bfs는 큐를 이용한 풀이python 특성상 queue보다 deque가 효율적이라서 deque사용dfs는 재귀를 이용한 풀이스택으로 할라다가 실패함ㅎ..작성 코드from collections import dequen,m,v = map(int, input().split(' '))g=[[False]*(n..

난이도 : 실버2소요시간 :  58분사용한 풀이법 : 백트래킹풀이 과정1. 현재 원소 위치와 총합을 매개변수로 하는 func()정의2. 현위치 변수가 n과 같고, 총합이 s와 같은 경우에 카운트 후 리턴3. 조건 미 충족 시, func() 재귀4. 재귀는 다음 위치의 수를 더하는 경우와, 더하지 않는 경우 두가지로 진행5. S가 0일 때, 모두 더하지 않은 경우를 카운트에서 제외시켜야 함.작성 코드#include using namespace std;int n, s;int arr[30];int cnt = 0;void func(int cur, int tot){ if(cur == n){ if(tot == s) cnt++; return; } func(cur+1, tot+arr[cur]); ..

난이도 : 골드5소요시간 :  47분사용한 풀이법 : bfs풀이 과정1. color 입력 받는 동시에 배열에 삽입2. for문 돌면서 미방문한 곳 발견 시 bfs() 호출3. bfs()함수에서는 호출 된 부분의 색과 동일한 곳만 탐색4. 탐색이 끝나면 normal++ 후 bfs 재호출5. color배열 탐색 종료 후, 적록색약 버전 카운트위해 vis[][] 0으로 재초기화6. color배열의 'G'를 'R'로 대치7. bfs()호출 및 blind++과정 반복8. normal과 blind 각각 출력작성 코드#include #include #include using namespace std;queue > Q;char color[101][101];int vis[101][101];int dx[4]={1,0,-1..