Security Story

▶문제   ▶풀이이 문제는 연속된 배추 영역의 개수를 구하면 되는 문제이다.연속된 영역의 개수는 자료구조 시간에 이미 BFS, DFS 방식으로 배웠다. 나는 두 방식 중 BFS(너비 우선 탐색) 방식으로 문제를 풀었다. 방문한 배추는 더 이상 탐색되지 않도록 0으로 변경해 처리배추가 있는 위치(matrix[a][b] == 1)에서 BFS를 수행해 하나의 배추 그룹을 탐색하고 그룹의 개수를 증가즉, 배추밭을 모두 순회하며 배추가 있는 새로운 그룹을 발견할 때마다 BFS로 해당 그룹을 모두 탐색하고, 그룹 카운트를 증가시킨다.  전체 코드T = int(input()) # 테스트 케이스 수 입력dx = [-1, 1, 0, 0] # 상하 이동dy = [0, 0, -1, 1] # 좌우 이동def BFS(x,..

▶문제   ▶풀이이동 시 전에 이동한 거리보다 같거나, 1씩 크거나 작다.이동해야할 거리 = y지점 - x지점처음 이동 시와 마지막 도착 지점까지의 이동은 무조건 1이다. 우선 문제를 읽고 이 정도로 간략히 정리 해보았다. 일단 규칙성을 파악해야한다. 공간이동 장치 작동 횟수는 1, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7...의 규칙을 보이고 있다.홀수가 될 때마다 숫자의 반복 횟수가 늘어난다. (3일 때 2번으로, 5일 때 3번으로, 7일 때 4번으로 늘어남) 전체 코드t = int(input()) #테스트 케이스 개수 입력 받기for _ in range(t): #t만큼 반복하면서, 각 테스트 케이스마다 두 정수 x(출발점)와 y(도착점)를 입력 x, y =..

▶문제   ▶풀이n=int(input())d=[]for i in range(n): d.append(list(map(int, input().split())))for i in range(1,n): for j in range(len(d[i])): if j==0: d[i][j]=d[i][j]+d[i-1][j] elif j==len(d[i])-1: d[i][j]=d[i][j]+d[i-1][j-1] else: d[i][j]=max(d[i-1][j-1],d[i-1][j])+d[i][j]print(max(d[n-1])) 삼각형의 각 요소는 두 개의 바로 위 요소 중 더 큰 값에 현재 요소의 값을 더한 것각 요소에 대해 최대 경로합을 계산하기 위해 DP 테이블을 설정삼각형..

▶문제   ▶풀이그대로 구현하면 값을 구하는데 오래 걸린다고 하였다..그 이유는 동일한 값을 계속 연산하기 때문이다.따라서 dp 알고리즘을 통해 구현해서 if dp[a][b][c] : return dp[a][b][c]즉 dp[a][b][c]의 값이 존재한다면, 해당 값을 리턴하라는 기능만 추가해주면 시간 내로 풀 수 있다.  ※동적 계획(Dynamic Programming)주어진 문제를 이보다 더 작은 크기의 문제들로 나눈 후, 이를 해결해 최종해에 다가가서 해를 찾는 알고리즘주어진 문제를 단계적으로 해결해 나가는 과정에서 종전에 찾아 둔 해를 다시 활용하는 것이 동적 계획법의 중요 절차※메모이제이션중복되는 계산 결과를 저장하여 이전에 계산한 값을 캐시하고, 다시 필요할 때 해당 값을 가져와 재사용 이미..

▶문제​​​▶풀이이 문제도 블랙잭 문제와 같이 모든 경우의 수를 탐색하는 브루트 포스 방법을 사용하면 된다. ① 정수 N을 입력받는다. ② 1부터 입력받은 정수 N까지 반복문을 실행③ 각 숫자를 자릿수로 분리하여 각 자릿수를 리스트에 저장-> 전체적인 알고리즘은 이와 같고 코드별 세부 설명은 주석 처리하여 설명하였다.​​이 문제는 비교적 쉽게 풀 수 있었다!

▶문제문제를 정리하자면플레이어는 N장의 카드 중 3장의 카드를 뽑는다.딜러가 외친 숫자 M을 넘지 않으면서 최대한 가까운 카드 3장의 합을 출력한다.카드의 개수 N은 3이상 100이하, 딜러가 외치는 숫자 M은 10이상 300,000 이하이다.​​​▶풀이이 문제 같은 경우는 모든 경우의 수를 다 돌아야한다.① map 함수 사용map() : 여러 개의 데이터를 받아서 각각의 요소에 함수를 적용한 결과를 반환하는 내장 함수기본 문법: map(function, iterable)function : 각 요소에 적용할 함수iterable: 리스트, 튜플 등 함수를 적용할 데이터 집합-> iterable의 각 항목을 순회하면서 function을 적용하고, 그 결과를 새로운 iterable 객체로 반환​이 문제에선 사..

▶문제​​​▶풀이우선 문제를 잘 이해해야한다(처음엔 2차원 배열인가 생각했는데 아니었다...)예를 들어 0층에 4호까지 있고 1호부터 4호까지 각각 1,2,3,4명이 산다고 생각해보자. ​2층: 1 4 10 201층: 1 3 6 100층: 1 2 3 4​이런식으로 살 수 있는 것이다. 즉, 정리해보면 1. k,n을 입력받음2. 중첩 for 반복문을 사용한다. 먼저 해당 호수에 거주하는 사람을 저장해둔다.3. 층수가 증가할 때마다 저장되어있는 값에 새로운 값을 저장한다. ​​​▶참고1. 반복제어변수 없는 for 반복문이 문제를 풀기 위해선 반복제어변수가 없는 for 반복문을 한 번 써야한다. 이 개념이 생소해서 따로 찾아보았다. -> 단순 반복만 할 때와 같이 제어변수를 명령에서 꼭 사용해야 되는 것은 아..

▶문제​​​▶풀이우선 어떻게 풀어야할지 바로 생각이 안나 1부터 경우의 수를 적어보았다.1부터 5까지 적어보니 1~3은 방법의 수가 각각 1,2,4가지이고 4부터 자기 앞의 3개 숫자의 방법의 수를 더한 값이 나온다는 것을 알았다!코드별 설명 및 주의사항은 주석으로 달았다. 이번 문제는 2주차 문제보다 훨씬 수월했다!​​​▶참고이 문제를 조건식으로 풀었는데 처음에는 배열로 푸려고 했다. 그러다 조건식이 더 간단하게 스스로 작성할 수 있을 것 같아 바꿨는데 배열의 초기화 하는 법을 몰라 검색을 하였다.​list명 = [0] * N-> [0]이 N개인 리스트를 생성하는 방법이다. 즉, N개의 원소를 가진 리스트를 0으로 초기화하는 방식이다.

▶문제문제 조건이 많다. 조건부터 정리해보자면① 추의 개수 : 자연수, 30개 이하② 추의 무게: 자연수, 500g이하, 같은 무게의 추 중복 가능③ 무게를 확인하고자 하는 구슬의 개수: 7개 이하④ 확인하고자 하는 구슬의 무게: 40,000보다 작거나 같은 자연수줄별로 크게 4가지로 나눌 수 있다.​​​▶풀이문제를 살펴보면 양팔 저울이 무게를 재는 원리는 "양팔에 올라간 추의 무게 차이"임을 알 수 있다. 이 문제 또한 시간 안에 풀기 위해서는 중복되는 경우가 있는지 생각해봐야 한다. 고민해본 결과 양팔의 차이가 같은 경우들은 굳이 중복해서 계산하지 않아도 되지 않을까?라는 생각을 해보았다. 예를 들자면 과 같이 1g&4g 추로 구슬의 무게가 3g임을 알 수 있지만 2g&5g, 극단적으로 97g&100..

▶문제​​​▶DFS​우선, 이 문제를 풀기 위해 DFS(깊이 우선 탐색)에 대해 알아야한다.​[참고]https://velog.io/@dltmdrl1244/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%9E%98%ED%94%84-%ED%83%90%EC%83%89-DFS-BFS[알고리즘] 그래프 탐색 - 깊이 우선 탐색 (DFS) (파이썬)그래프 탐색 알고리즘의 대표격이라 할 수 있는 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)에 대해 알아보자.velog.ioDFSDepth-First Searh, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이며 스택 자료구조(혹은 재귀함수)를 이용한다. ​DFS의 작동 방법1. 노드와 연결된 탐색하지 않은 이웃 노드 ..