기록

문제 https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 (s, e)를 끝점(e) 기준으로 정렬한다. 위치 0.5(shoot = 0.5)인 곳에서 미사일을 발사한다. 직전 미사일 발사위치(shoot)와 군사기지(target)의 시작점을 비교한다. 직전 미사일 발사위치(shoot) < 군사기지(target)의 시작점 군사기지의 종료점-0.5에서 미사일을 발사한다. 미사일 발사 지점을 저장한다. (shoot = target[1]-0.5) 다음 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 투 포인터 투 포인터 알고리즘은 주로 배열 또는 리스트에서 두 개의 포인터(인덱스)를 사용하여 특정 조건을 만족하는 부분 구간을 탐색하는 알고리즘이다. 시작과 끝을 가리키는 두 포인터를 이동하며 구간을 조절하며 조건을 만족하는 구간을 효율적으로 찾을 수 있다. 코드 def solution(queue1, queue2): s, e = 0, len(queue1) queue = queue1+..

문제 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 풀이 1) 분할된 팰린드롬의 최소 개수 문자열 ABACA가 주어졌을 때 해당 위치 안에서 찾은 팰린드롬을 아래처럼 표현할 수 있다. 각 위치에서 분할된 펠린드롬의 최소 개수를 저장하면, 문자열 전체에서 분할된 팰린드롬의 최소 개수를 저장할 수 있다. dp[e] = min(dp[s]+1, dp[e]) 팰린드롬의 최소개수를 dp로 구하는 풀이(시간초과) def isPal(s, e) : whil..

문제 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 1) 크루스칼 알고리즘 크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 크러스컬 알고리즘(영어: Kruskal’s algorithm)은 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 변의 개수를 E {\displaystyle E} , 꼭짓점의 개수를 V ko.wikipedia.org 1. 간선을 비용이 적은 것부터 오름차순으로 정렬한다. 2. 각 간선이 사이..

문제 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 1) 사이클 찾기 모든 학생들을 시작점으로 두고 dfs를 통해 사이클을 탐색한다. 1. 기존에 방문하지 않은 학생이라면, 방문기록을 남긴다. 다음 학생으로 이동한다. 2. 기존에 방문한 학생이라면, 방문 경로를 찾아 사이클을 이루는 학생의 수를 반환한다. 2) 시간초과 시간초과로 오래 고민했던 문제인데, 다른 문제를 풀면서 다시 한번 도전했다. 코드 import sys sys.setrecursionlimit(10**6) input = sys.stdin.re..

문제 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 풀이 1) 문제 이해하기 지도 밖으로 나가는 방향은 주어지지 않으므로, 어느곳에서 시작하더라도 사이클을 만나게 된다. (경로의 끝은 항상 사이클이다.) SAFE ZONE을 각 사이클에 만든다면, SAFE ZONE을 최소한으로 설치할 수 있다. 사이클의 개수를 출력한다. (최소 SAFE ZONE 개수 = 사이클의 개수) 2) 사이클 찾기 모든 위치에서 dfs를 통해 성우가 피리를 불때 움직일 경로를 시뮬레이션한다. 1. 기존..

문제 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 1) dfs for grouping 지도가 아래처럼 주어지면, 깊이우선탐색을 이용해 움직일 수 있는 경로를 그룹화 할 수 있다. 1 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1은 벽이므로 0에 대해서만 탐색하여, 그룹별 원소의 개수를 저장해둔다. {g00 : 2, g10 : 3, g22 : 1, g24 : 1, g32 : 1, g33 : 1} 1 1 g00 g00 1 g10 g10 1 1 1 g10 1 g..

문제 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 풀이 DP 위치를 위, 오른쪽, 왼쪽으로 움직이면서 가장 큰 경우를 board에 저장한다. 1. 0번째 행의 경우, 오른쪽으로만 이동이 가능하다. 2. 1번째 ~ N-1번째 행까지, 오른쪽/왼쪽으로 이동이 모두 가능하다. 2-1. 왼쪽과 위쪽을 비교하여 구한 배열과 2-2. 오른쪽과 위쪽을 비교하여 구한 배열을 비교해 해당 위치에서 가질 수 있는 최대값을 board에 저장한다. 코드..