Dev Record

자료구조별 연습 0️⃣ Map # 선언방법 dictionary = {} or dict() # 딕셔너리 for 문 # 1. 일반적으로 for문을 돌리면 key값이 순회된다. for key in a: ... # 2. value값을 순회하기위해서는 values()를 사용 for value in a.values(): ... # 3. key와 value를 한꺼번에 순회하려면 items()를 사용 for key, value in a.items(): ... # 4. dictionary에서 in 값은 key값에 한해서 동작 # 5. 딕셔너리의 요소 삭제 a = {'alice': [1, 2, 3], 'bob': 20, 'tony': 15, 'suzy': 30} del a['alice'] >>> {'bob': 20, 't..

자료구조별 연습 0️⃣ 스택 * LIFO * 원소의 추가와 삭제가 O(1), 제일 상단이 아닌 나머지 원소들의 확인과 변경이 원칙적으로는 불가하다. * 파이썬, 자바스크립트의 내장 array는 쉽게 스택처럼 동작할 수 있다. (append, pop / push, pop) 1️⃣ 큐 * FIFO * 원소의 추가와 삭제, 제일 앞/뒤의 원소 확인이 O(1), 제일 앞/뒤가 아닌 나머지 원소들의 확인과 변경이 원칙적으로는 불가능하다. * 원소 변경에 따라 큐의 시작을 가리키는 head, 끝부분을 가리키는 tail이 재조정된다. * 원형큐를 사용하면 큐에서의 삭제가 발생할 때마다 생기는 쓸모없는 공간의 낭비를 줄일 수 있다. * 파이썬에서는 deque을 활용하면 큐처럼 동작할 수 있다. from collecti..

그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디로 얻은 해가 최적의 해를 보장할 수 있는가?에 대한 정당성을 늘 고민할 것 🚀 그리디하게 해결하려고 할 때 다루기 쉬운 자료구조: 배열, 힙, 스택 등 🚀 주요 아이디어: 정렬, 조건에 맞춰 pop 🚀 알고 있는 걸 잘 꺼내자. 문제풀이 ✅ 2839번 설탕배달 (S4) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net def getInput(): return int(input()) def solution(): n = getInput() total = n bucket = 0 # case 1 if n % 5 == 0: return n // 5 while tot..

🥸 문제 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 🥳 해설 및 풀이 input size를 계산해보니 브루트 포스가 가능한 문제였고, 4^8(가능한 경우의 수) * board의 크기 (8 * 8) 정도가 최대 계산 빈도수 정도여서 완전탐색으로 진행할 수 있었다. 전체 경우의 수(4가지 케이스 (동서남북) ** 8(CCTV의 최대 개수))를 어떻게 두면 좋을지 고민했는데, 가능한 경우의 수를 그냥 숫자로 가정하고 4^len(cctv) 만큼 반복문을 돌려줬더니 편하게 계산할 수 있었다. 핵심은 아래..

🥸 문제 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 🤩 해설 및 풀이 s = [] w = [] mx_cnt = 0 curr_cnt = 0 def solution(a): global mx_cnt, curr_cnt if a == n: mx_cnt = max(mx_cnt, curr_cnt) return if s[a]

출처: baaarkingDog님 유튜브 [바킹독의 실전 알고리즘] 내용을 기반으로 정리한 포스팅입니다. 백트래킹 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 현재 상태에서 가능한 모든 선택지를 다 플레이해보는 방법 백트래킹은 상태를 넘나든다. def solution(k): # 현재 k개까지 수를 택했음. if k == m: # m개를 모두 택했으면 for i in range(m): print(temp[i], end=' ') # temp에 기록해둔 수를 출력 print() return for i in range(1, n + 1): # 1부터 n까지의 수에 대해 if not visited[i]: # 아직 i가 사용되지 않았으면 temp[k] = i # k번째 수를 i로 정함 visit..

재귀 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 🚀 절차 지향적 사고와 귀납적 사고 QUESTION: n부터 1까지 출력하는 문제 절차 지향적 사고 func1(3)의 출력 결과가 왜 3 2 1인지를 생각해본다면 이 코드가 동작하는 흐름을 그대로 따라가면 된다. 일단 func1(3)가 호출되면 3을 출력하고 func1(2)를 호출한다. func1(2)는 2를 출력한 후에 func1(1)을 호출할거고 func1(1)은 1을 출력한 후에 func1(0)을 호출한다. 그리고 func1(0)은 02번 줄에 걸려서 종료된다. 이렇게 과정을 따라가고 나면 func1(3)을 실행했을 때 3 2 1이 출력된다는 것을 알 수 있다. 귀납적 사고 첫 번째로 func1(1)이 1을 출력한다, 이건 굉장..

문제 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 가중치가 있는 그래프에 대한 처리를 어떻게 하면 좋을지 고민할 수 있었던 문제 일차원 배열이어도 접근 방식은 비슷하다. 무게나 비용이 가장 적은 것 먼저 넣고 그것들을 먼저 뽑고 싶기에 큐를 사용했던 것이다, 가중치가 있으면 이를 만족하는 것이 맞다. 해당하는 자료구조가 왜 등장했는지 생각하자. from collections import deque def solution(n, k): if n == k: return 0 siz..

문제 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 처음에 익을 수 없는 경우의 수를 먼저 체크해주는 것이 좋겠다고 생각했다. 이번에는 큐에 넣어주어야 하는 경우가 두 가지 더 추가되었었다. (위층, 아래층) 예외적인 상황은 먼저 이른 리턴해주어서 가지치는 것도 특정 케이스에서 복잡도를 줄이는 방법 중 하나 인 것 같다. from collections import deque # TODO: 토마토가 익는 최소 일 수 구하기 🪀 def solution(h, n, m, board): ..

문제 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 해석 및 풀이 적록 색약인 경우와 적록 색약이 아닌 경우 색을 볼 때 경우의 수 차이가 생기게 되는데, 이에 유의해서 케이스를 나눈다. 일반적인 BFS와 비슷하지만 적록 색약인지 아닌지에 따라 행해야하는 행위가 달라지게 된다. 따라서 적록색약인지 아닌지를 인자로 받고, 이에 따라 bfs내부에서 if문으로 처리해주었다. from collections import deque def solution(n, board): cw_cnt = 0 total_cnt ..