알고리즘(파이썬)
1.[백준] 11053번(파이썬) 가장 긴 증가하는 부분 수열
11053기본적인 DP 문제이다.처음에 문제를 제대로 이해하지 못해서, 단순히 주어진 리스트에서 중복을 제거하고, 오름차순 정렬한게 답이라고 생각했다.하지만 이 문제는 증가하는 '부분'수열이 핵심이다. 즉, 주어진 리스트 그대로 그 안에서 오름차순으로 진행되는 부분적인
2.[백준] 6087번(파이썬) 레이져 통신
6087번 문제 BFS 탐색문제이다. 처음에 거울 설치 횟수를 어떻게 셀까를 고민했을때 든 생각은 바로 전의 이동방향을 생각해서, 전의 이동방향과 다른 방향으로 갔을 때, 거울 설치 횟수를 늘렸다. 하지만 이렇게 했을 경우에 한가지 문제가 생겼다. 아래와 같은 예시가 있을때 (0,0)인덱스의 지점에서 BFS 탐색을 시작하면 ↓, -> 두방향으로 탐색을 ...
3.[백준] 2579번(파이썬) 계단 오르기
2579번 문제 DP문제이다. 문제를 간략히 이해해보면, 세 계단을 연속으로는 밟을 수 없고(=두 계단을 연속으로 밟으면 한 계단 건너뛰어야한다.), 마지막 계단은 꼭 밟아야 한다. 이번 문제의 힌트는 마지막 계단은 꼭 밟아야한다는 조건에서 알 수 있다. > ### 마지막 계단의 입장에서 이전 계단들이 어떻게 밟힐지를 생각해보면 쉽게 풀 수 있다. 1,2...
4.[백준] 2638번(파이썬) 치즈
2638번 문제 BFS탐색 문제이다. 문제를 간략히 정리해보면, 치즈의 4변중 2변이상이 공기와 접촉하면, 한 시간만에 녹는다. 치즈 내부 공간은 외부 공기와 접촉하지 않는 것으로 가정한다. 가장자리는 치즈가 놓이지 않는것으로 가정한다. 내가 처음 문제를 접했을 때
5.[백준] 16236(파이썬) 아기상어
16236번 문제 BFS 탐색+구현 문제이다. 문제를 간략히 정리해보면 처음에 크기가 2인 아기상어가 있다. 이 아기상어는 1초마다 인접한 칸으로 이동이 가능하다. 아기상어는 자신과 크기가 같은 물고기는 지나갈 수 있고, 작은 물고기는 먹을 수 있다. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹으면 크기가 1 증가한다. 상어의 이동방식 가장...
6.[백준] 17135(파이썬) 캐슬 디펜스
17135번 문제BFS+시뮬레이션 문제이다.문제를 간략히 정리해보겠다.적을 잡는 턴방식의 게임이다.궁수는 성이 있는 칸에 3명을 배치한다.(여기서 성의 위치는 격자판 바로아래 행(n+1)이다.)각각의 턴마다 세명의 궁수는 동시에 적을 죽인다.(두명의 궁수가 한명의 적을
7.[백준] 19238(파이썬) 스타트 택시
19238번 BFS+시뮬레이션 문제이다. 우선 문제를 간략히 정리해보자. m명의 손님을 태우는 것이 목표 -> 목표 미달성시 -1출력 택시가 가장 가까운 승객을 태워서, 해당 승객의 목적지로 데려다준다. 가장 가까운 승객이 여러명일 경우, 행번호가 작은 승객 그 다음으로 열번호가 가장 작은 승객을 태운다. 승객을 목적지로 이동시키면, 그 승객을 태워 이동...
8.[백준] 21609(파이썬) 상어 중학교
21609번 상어 중학교 BFS+시뮬레이션 문제이다. 이 문제의 경우 2021 삼성 상반기 오전 공채 SW 역량테스트 문제 (SW A형)이다. 풀이에 대해 숙지 하고 있자. 문제를 정리해보겠다. 블럭은 검은색(-1), 무지개(0), 일반(1~m) 색상이 있다. 일반 블럭은 m가지 색상이 있고, m이하의 자연수로 표현한다. 블럭 그룹은 연결된 블럭의 집합...
9.[백준] 1699(파이썬) 제곱수의 합
1699번 제곱수의 합 DP문제이다. 이번 문제는 제곱수의 합으로 수를 표현하되, 가장 적은 갯수의 수들로 구성해야 한다. 예로 $11=3^2+1^2+1^2$ 처럼 3개의 수를 이용해서 표현할 수 있고, $11=2^2+2^2+1^2+1^2+1^2$ 과 같이 5개의 수를 이용해서 표현할 수도 있다. DP문제는 점화식을 찾는게 핵심이므로, 규칙을 찾기위해서...
10.[백준] 1072(파이썬) 게임
1072번 게임 이분탐색 문제이다. 아직 이분 탐색이 익숙하지 않아서, 문제를 보자마자 직관적으로 떠오르는 것은 없었다. 문제를 보면서 처음에 들은 생각은 게임횟수-이긴게임 사이의 수가 결국 정답으로 나온다는 것이다. 그래서 든 생각은 게임횟수-이긴게임을 lower_bound로 구현하면, 그것이 정답이라고 생각했다. 그래서 만든 코드가 아래와 같다. 하...
11.[백준] 2110(파이썬) 공유기 설치
binary search 이분탐색 문제이다.문제를 요약해보면집은 N개가 있고, 설치할 공유기는 C개가 있다.이때 집의 좌표 x1,...,xn이 주어지고, 공유기는 집에만 설치가 가능하다.이때 가장 인접한 두 공유기 사이의 거리를 최대로 해야한다.우선 문제를 처음 접했을
12.[Softeer] 바이러스
Softeer 알고리즘 풀이
13.[Softeer] 금고털이
Softeer 알고리즘 풀이
14.[프로그래머스] 퍼즐 조각 채우기
본 문제는 game_board의 빈공간에 table의 조각을 넣어서 빈 공간을 가장 많이 채우는 조각의 개수를 묻는 문제이다.game_board 빈 공간에는 하나의 조각만 들어갈 수 있고, 2개의 조각을 합쳐서 넣을 수는 없다.table의 조각은 회전은 가능하지만, 뒤