프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근한 방법 DFS로 현재 문자열에서 한 글자씩 지워가며 비교하는 방식으로 탐색합니다. 예를 들어 begin이 hit라면, 순차적으로 *it, h*t, hi* 과 같은 위치인 글자가 words배열에도 존재하는지 확인하여 존재하면 진입 횟수를 카운트하여 재탐색합니다. 이때 이미 방문했던 단어들은 제외하기 위해 방문 배열을 설정하여 관리합니다. target이 발견되면 현재까지 저장했던 result 카운트를 갱신한 후 DFS가 완전히 끝날 때 남아있는 result의 값이 최소 비교 횟수가 됩니다. 코드 설명 1. ..

1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 접근한 방법 그리디를 이용해 최소 개수로 최대한 많은 강의(작업)를 실행하기 위한 작업 스케줄링 문제입니다. 기본 아이디어는 강의들을 시작 시간을 기준으로 오름차순 정렬한 후, 그리디하게 선택하는 것입니다. 1. 강의들을 시작 시간을 기준으로 정렬합니다. 2. 힙(우선순위 큐)을 사용하여 강의 시간을 스케줄링합니다. 힙은 강의의 종료 시간을 저장하는데 사용되고 항상 종료 시간을 기준으로 최소 힙(가장 작은 종료 시간을 루트에 두는 힙)으로 유지해야..

5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 접근한 방법 최장 공통 부분수열을 구하는 문제로써 DP를 활용하여 해결할 수 있습니다. 1. DP 테이블 d를 생성하여 문자열의 길이에 따른 최장 공통 부분 수열 길이를 저장합니다. d[i][j]는 s1의 첫 i개 문자와 s2의 첫 j개 문자 사이에서의 최대 공통 부분 수열의 길이를 나타냅니다. 2. 문자열을 비교해 최장 공통 부분 수열 길이를 갱신합니다. 이중 반복문을 사용하여 s1과 s2의 각 문자를 순회하면서 만약 s1[i - 1]과 s2[j -..

접근한 방법 미로에서 최단 경로를 찾는 BFS 알고리즘을 사용하여 해결할 수 있습니다. 최소 heap 자료구조를 이용하여 매 방문마다 가장 적게 벽을 바꾼 지점의 좌표를 꺼내서 해당 좌표에서만 탐색을 나아가면 최소 개수로 벽을 바꿀 수 있습니다. 1. 큐에서 원소를 하나씩 꺼내면서 해당 위치의 상하좌우를 체크합니다. 2. 벽이 있는 경우는 +1 카운트 하여 큐에넣고 그렇지 않은 경우는 그대로 큐에 넣어줍니다. 3. 마지막 지점에 닿으면 현재까지의 카운트를 출력하고 종료합니다. Python import sys input = sys.stdin.readline n = int(input()) arr = list(list(map(int, input().rstrip())) for _ in range(n)) from..

5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 접근한 방법 그래프의 간선 가중치를 고려한 최단 경로를 구하는 문제입니다. 힙 자료구조를 이용한 다익스트라 알고리즘으로 풀이할 수 있습니다. dist는 노드 간의 최단 거리를 저장할 리스트로 초기값은 무한대(inf)로 초기화하고 1번 노드부터의 최단 거리를 나타냅니다. graph는 각 노드에 연결된 엣지 정보를 저장하는 리스트입니다. 먼저 그래프 정보를 구성해야 합니다. m번 반복하여 입력으로 주어지는 간선 정보를 바탕으로 생성합니다. 양방향 그래프이므로 두 노드 간의 ..

2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 접근한 방법 답을 도출하기 위한 풀이 로직은 쉽지만 메모리, 시간 초과 문제로 인해 정답 비율이 낮은걸로 보입니다. 이 문제를 만약 2개의 배열을 만들어 중간 결과를 저장하는 방식으로 코드를 짰다면 입력 데이터가 클 때 메모리 제한(4mb)에 걸리게 될겁니다. 따라서 입력 데이터의 최댓값과 최솟값을 계산하면서 중간 결과를 저장하는 대신, 이전 단계의 계산 결과만 활용하여 계산해 나가는 방식을 사용하면 풀이할 수 있습니다. 첫 입력 데이터 한 줄을 초깃값으로 정해놓고 다음 입력..