문제https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 요약김대리는 회사에서 출발김대리는 모든 고객의 집 방문이후 집 도착위 조건으로 집, 회사, 고객의 집 좌표 정보를 이용해, 최단 거리를 구하는 문제이다. 문제 풀이고객의 수 = 2~10x, y 좌표 = 0~100 10개의 집을 순서대로 나열하는 경우의 수를 구하면10! = 약 300만이다. 좌표상 최장거리 = 200, 10개의 집최고 거리 = 200 * 10이다.즉, Integer 범위로 해..
Problem Solving
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이문자열에서 숫자 단어로 된 부분을 숫자로 바꿔는 문제이다. 1. 0~9까지의 숫자 단어를 매핑하는 배열을 생성한다. 2. String.replace를 사용해서 숫자 단어가 포함되어 있다면 전부 숫자 문자열로 변환한다. 3. Integer로 파싱해서 반환한다. 소스코드class Solution { public int solution(String s) { String[] numbers = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}; ..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이아기가 발음할 수 있는 4가지 발음이 존재하는데, 연속적으로 단어를 사용하지 않고 발음을 할 수 있는 단어의 수를 구하는 문제이다. 즉, 단어의 인덱스에서 word만큼의 길이를 잘라서, 발음을 할 수 있으면 인덱스를 이동하고 발음한 단어를 기록하는 방식으로 구현하면 된다고 생각했다. 1. 4가지 발음을 배열로 기록한다. 2. 단어마다 체크를 해야한다.현재 발음한 단어, 인덱스, 발음이 가능한지 여부 변수를 기록한다. 3. idx에서 발음할 수 있는 단어의 길이만큼 자르면서, 이전 발음과 다르다면 인덱스를 이동한다. 4. 발음을 못하면, 읽을 수 없는 것으므..
문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이삼총사가 되는 경우의 수를 구하는 문제이다.삼총사는 3명의 학생의 번호를 합했을 때 0이 되는 경우이다. 이 문제는 간단하게 3중 for문을 이용하면 풀 수 있다. 하지만, 3명이 아니라 5명, 10명이라면 5중 10중 for문을 사용할 수는 없다. 그래서 for문이 아닌, 재귀적인 방법으로 이 문제를 해결했다. 1. 전역 배열을 만들어서 복사한다. 2. dfs를 이용해서 3명의 학생 번호를 더한 다음, 삼총사가 되는 경우의 수를 센다. 3. 경우의 수를 리턴한다. 소스코드class Solution { int answer; int[] arr; ..
문제https://www.acmicpc.net/problem/1068 풀이트리에서 한 개의 노드를 삭제했을 때, 리프노드의 수를 구하는 문제이다. 어떻게 하면 삭제처리를 하면서, 리프노드를 구할 수 있을까? 문제의 그림을 보면 삭제 노드의 자식 노드들을 모두 삭제처리를 해야하는 것을 보면 dfs를 사용해야겠다는 것을 자연스럽게 떠올릴 수 있다. 삭제 노드의 부모 노드가 삭제 노드만 자식으로 가지고 있었다면, 부모노드도 리프노드가 되어야한다.(이게 제일 중요하다)즉 둘 사이을 끊어주는 것이 필요하다. 그래서 이 문제에서는 자식에서 부모를 가리키는 배열 + 부모에서 자식을 가리키는 배열 2가지가 필요하다. 1. 부모 자식간 연결 정보를 담는다. 2. 삭제 노드가 루트 노드일 경우, 모두 지워지므로 0을 출력..
문제https://www.acmicpc.net/problem/9466 풀이학생들의 선택에 사이클이 되는 경우 팀이 결성되는데, 결성 되지 않은 팀원들을 구하는 문제이다. 이 문제에서는 2가지 체크하는 배열이 필요하다.1. 노드를 방문 체크 배열2. 팀이 꾸려졌는지 체크 배열(팀이 결성된 학생을 세지 않기 위함이다.) 다음 노드가 무조건 1개이므로, dfs를 사용하는 것이 적절하다고 판단했다.dfs를 수행하면서 현재 정점에서 다음 정점에 대한 방문 여부를 생각했을 때현재 정점은 방문되지 않았지만 다음 정점이 방문되었다면 무조건 사이클이 도는 것이라고 할 수 있다. 그러면 팀 결성 여부를 확인하고팀이 결성되지 않았었다면, 사이클이 도는 학생들의 수를 센다. 이 풀이는 팀이 결성되지 않았으면서 + 사이클이 ..
문제https://www.acmicpc.net/problem/9465 풀이2행 n열로 배치된 스티커를 떼서 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 일단 2문제에서 떼고 안떼보고 전체적인 완탐을 수행하면 2^100000이기 때문에 무조건 시간초과가 난다. 그러면 이 문제를 어떻게 해결할 수 있을까? 결국 10만개의 데이터가 있다는 것은 선형적인 시간복잡도를 가지는 것으로 해결해야한다. 다이나믹 프로그래밍을 이용한다.이전 열까지 스티커를 떼고 최댓값을 누적시키면서 갱신해보는 것이다. 만약에 이런 형태가 있다고 하자.(O: 뗀 스티커, X: 떼지 않은 스티커)XXOXXX 그러면 하단의 2가지가 된다. (?는 스티커가 붙여있는지 안붙여있는지 모른다는 의미이다.)?XOOXX ?XOXOX 즉 밑에 있는 ..
문제https://www.acmicpc.net/problem/9252 풀이점화식을 도출하고 구하는 것은 이전 포스팅 글을 살펴보면 된다. [Baekjoon] LCS - Java문제https://www.acmicpc.net/problem/9251 풀이두 문자열이 주어졌을 때, 두 문자열의 공통 부분 수열의 최대 길이를 구하는 문제이다. ACAKCBAK위 두 문자열이 있다고 하자. 그러면 부분 수열은 CAK가 부분gretea5.tistory.com 최장 공통 부분 수열을 구하는 방법 중에 제일 쉬운 방법은 문자열도 함께 저장해서 문자를 붙이는 형태로 구현하는 것이다.근데 메모리 초과가 발생한다. 왜일까?문자를 저장하는데 1byte라고하자.1 * 1000(문자열의 길이) * 1000 * 1000 = 약 1G..
문제https://www.acmicpc.net/problem/9251 풀이두 문자열이 주어졌을 때, 두 문자열의 공통 부분 수열의 최대 길이를 구하는 문제이다. ACAKCBAK위 두 문자열이 있다고 하자. 그러면 부분 수열은 CAK가 부분 수열이 될 것이다. 이 문제를 잘보면,ACAK와 C의 공통 부분 수열의 길이를 구한다.ACAK와 CB의 공통 부분 수열의 길이를 구한다.ACAK와 CBA의 공통 부분 수열의 길이를 구한다.ACAK와 CBAK의 공통 부분 수열의 길이를 구한다.(목표 == 우리가 원하는 것) 문자열을 하나씩 붙이면서 큰 문제 즉, 우리가 원하는 문제를 만들고 있다.작은 문제에서 큰 문제를 구할 때 사용하는 알고리즘은 다이나믹 프로그래밍을 이용하면 된다. 1. 테이블을 정의한다.dp[i][..
문제https://www.acmicpc.net/problem/9019 풀이네자릿수를 저장하는 레지스터에서 D, S, L, R의 네가지 명령어를 수행하는데 주어진 숫자를 만들기 위한 최소한의 명령어를 구하는 문제이다. 이 문제를 명령을 수행해서 갈 수 있는 최소의 거리를 구하면 된다고 생각했고, 최소 거리를 구하면서 명령어도 같이 저장하면 될 것이라고 생각해 bfs를 사용해서 구현하면 된다고 생각했다. 1. 변환 전, 후 숫자를 입력받는다. 2. bfs를 사용해서 D, S, L, R과 같은 명령어를 수행했을 때, 방문 처리가 되지 않았으면 명령어를 같이 저장하면서 bfs를 수행한다. 3. 변환 후 숫자에 도달 했을 경우, 그에 대한 명령어를 출력한다. 소스코드import java.util.*;import ..
