코딩테스트 문제를 풀면서 자료구조&알고리즘을 합쳐서 이론 공부를 했더니 각각을 구별해서 알아둘 필요가 있겠다 싶었다. 스택, 큐, BFS, DFS, 연결 리스트 등 각각은 뭔지 아는데 어떻게 구분해야 하는지 헷갈렸다. 어쨌든, 일단 자료구조와 알고리즘의 개념을 먼저 공부하고 각각의 예시를 분류해보자.    자료구조자료구조는 데이터를 효율적으로 저장하고 관리하기 위한 방법이다. 데이터를 어떤 방식으로 정리하느냐에 따라 접근 속도나 사용 편의성이 달라지므로 문제를 보고 어떤 자료구조로 입력 데이터를 저장/처리할지 결정해야 한다.   📚 배열 (Array)예시: 사물함번호가 붙어 있는 사물함처럼, 데이터를 연속된 공간에 저장한다. 인덱스(번호)만 알면 데이터를 빠르게 찾을 수 있다.👉 특징:✅ 인덱스를 이..

https://www.acmicpc.net/problem/14502 문제설명바이러스의 확산을 막기 위해서 연구소에 벽 세우기벽을 세운 뒤 바이러스가 퍼질 수 없는 안전 영역의 최댓값 구하기   문제해결조건연구소의 크기 : N x M 직사각형 (직사각형은 1 x 1 크기의 정사각형으로 나누어져 있다.)연구소의 구성 : 빈 칸(0), 벽(1), 상하좌우로 퍼지는 바이러스 (2)새로 세울 수 있는 벽은 무조건 3개로직현재 빈 칸들 중 3개를 선택해서 벽 세우기 (조합 이용)바이러스를 퍼뜨리는 역할을 하는 BFS 실행, board 모두를 확인해야 하므로 바깥 for문 필요확산 후 안전영역 개수 세고 최댓값 갱신벽 되돌리기row_len, col_len = map(int, input().split())board =..

백준은 문제 옆에 IDLE이 없어서 넘 불편하다. 처음에는 vs code에서 파이썬 파일을 실행하고 입력을 한줄씩 복붙해서 넣어줬는데, 입력 파일을 따로 만들고 실행 파일에 코드를 작성해서 바로 결과를 볼 수 있는 꿀팁을 찾았다 !  1. 입력 파일 만들기입력 파일 안에는 아래와 같이 백준 문제의 예제 입력을 그대로 넣어준다. 원하는 테스트케이스가 있으면 수정해도 된다. 7 72 0 0 0 1 1 00 0 1 0 1 2 00 1 1 0 1 0 00 1 0 0 0 0 00 0 0 0 0 1 10 1 0 0 0 0 00 1 0 0 0 0 0    2. 실행 파일 만들기입력 파일에 있는 입력을 받아오고 원한는 형태로 쓰면 된다. 기본 형태는 input.readline()이고, 띄어쓰기로 구분되어 있으면 spl..

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ 문제설명nxn으로 구성된 행렬 grid가 주어질 때, (0,0)에서 (n-1,n-1)로 가는 가장 짧은 길의 길이를 구해라. 갈 수 없으면 -1. 0으로 구성된 칸에만 갈 수 있다.  문제해결가장 짧은 길이를 구하는 거니까 BFS 사용방향 주의하자 ! 4방향이 아니라 8방향으로 주어짐현재 위치 뿐만 아니라 현재 길이도 같이 저장하자. 현재 위치가 n-1이면 다온거니까 여기에 저장되어 있던 길이를 반환하면 된다. (BFS를 사용했으므로 가장 먼저 조건에 만족된 값이 가장 짧은 값!)(n-1, n-1) 위치에 도착하지 않았는데 더 이상 갈 곳이 없을 수도 있다. bfs 함수 마..

https://leetcode.com/problems/number-of-islands/description/ 문제설명grid가 땅(1)과 물(0)으로 구성되어 있을 때, 섬(물로 둘러싸져 있고 땅으로 구성된)은 몇 개 만들 수 있는지 ?  문제해결grid 전체를 탐색해봐야 하는데 하나로 연결되어 있지 않을 수 있으니까 전체적인 visit 필요만약 방문하지 않았고 해당 값이 “1”이면 -> bfs/dfs 실행 -> 끝나면 +1개class Solution: def numIslands(self, grid: List[List[str]]) -> int: def dfs(cur_r, cur_c): visit[cur_r][cur_c] = True dr = [0,..

https://school.programmers.co.kr/learn/courses/30/lessons/17680 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제설명DB 캐시를 적용할 때 캐시 크기에 따른 실행 시간 측정 프로그램 작성LRU(Least Recently Used) 방법 사용  문제해결현재 값이 캐시 리스트 안에 있으면현재 값 제거 후 맨 끝에 append, 실행시간+1현재 값이 캐시 리스트 안에 없으면꽉 찾으면 : popleft, append, 실행시간 + 5비었으면 : append, 실행시간 + 5def solution(cacheSize, cities): from collecti..

https://leetcode.com/problems/two-sum/description/ 문제설명정수로 구성된 리스트가 주어질 때, 두개의 숫자를 더해 target이 되는 인덱스를 반환  문제해결2중 for문class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)-1): for j in range(i+1, len(nums)): if nums[i]+nums[j] == target: return [i, j]   백트래킹class Solution: def twoSum(self, nu..

https://school.programmers.co.kr/learn/courses/30/lessons/118670 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr1. 문제설명행렬이 주어질 때 operations (Rotate, ShiftRow)를 순서대로 실행한 후 행렬의 결과 반환 2. 문제해결[첫번째 코드]def solution(rc, operations): from collections import deque new_rc = deque([]) for r in rc: new_rc.append(deque(r)) row_len = len(rc) for op..

1. 마지막 업샘플링층은 픽셀의 값을 직접 나타내고 있기 때문에 배치 정규화나 활성화 함수가 없다. (출력값이 변경되면 픽셀값의 정보가 소실되기 때문)   2. 재귀함수를 호출하면서 조건&return이 실행되면 진짜 returndef dfs(cur_v, bipart): ''' code ''' if dfs(next_v, bipart) == False: return False return True

https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 문제설명2진 트리 모양 초원에서 각 노드를 돌아다니며 양 모으기각 노드는 양과 늑대로 구성모은 양의 수보다 늑대의 수가 같거나 더 많아지면 모든 양 잡아먹힘중간에 양이 늑대에게 잡아먹히지 않으면서 다시 루트 노드로 돌아올 때, 최대 몇마리의 양을 모을 수 있는지 ? 2. 문제해결edges에서 하나의 edge는 부모-자식 노드의 연결을 의미한다.현재 노드에서 연결된 노드들을 방문할 수 있을 뿐만 아니라 이전 부모노드에 연결된 자식노드에도 방..