문제 파악https://school.programmers.co.kr/learn/courses/30/lessons/388353풀이일단 동시에 여러 지점에서 같은 깊이로 탐색이 필요해 BFS로 접근해야겠다는 생각이 들었다접근은 어렵지 않았지만, 추가 조건들이 존재해 구현이 조금 까다로웠던 문제였다.조심해야 할 케이스는 다음과 같다위와 같이 새로 노출되는 영역이 빈 칸일 경우, 빈 칸과 인접한 칸들도 노출된다.이 케이스를 커버하기 위해 조금만 더 신경쓰면 된다.구현 방향을 간략히 설명하자면 다음과 같다.컨테이너 맵의 크기와 동일한 isExposed(boolean[][]) 배열을 선언 및 초기화isExposed 테두리 부분을 true로 초기화하자.isExposed 배열을 참고하여 request에 따라 꺼낼 수 ..

문제 파악https://www.acmicpc.net/problem/1806풀이제목과 짧은 문제 덕에 문제 파악은 쉬웠다🙃. 부분 합 문제는 항상 투 포인터로 풀게 되는 것 같다.왼쪽 & 오른쪽 인덱스를 변수로 잡아준 다음 오른쪽 인덱스는 계속 증가시키며 연속합 변수에 누적하여 더해준다.안쪽 루프에서 연속합의 값이 S 이상이라면 왼쪽 인덱스를 오른쪽으로 조정해 주도록 하자.이때 왼-오 길이를 계산하여 기존 길이보다 짧다면 업데이트해 주면 된다.코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class N1806 { ..

문제 파악https://www.acmicpc.net/problem/1394어려운 점암호의 길이가 최대 1,000,000로 길기 때문에 제곱 연산이 많이 이루어질 것이고, 자료형의 범위를 넘기도 한다.첫 번째 라인에 주어진 문자열이 알파벳이 아닐 수 있음을 염두에 두자.풀이abc (암호로 사용할 수 있는 문자)ccc (암호)위를 예를 들어 계산해 보도록 하자암호 입력은a - b - c - aa - ab - ac - ba - bb - bc - ca - cb - cc - aaa - aab - (생략) - cca - ccb - ccc순으로 이루어진다.이를 조금 더 구분해 나누어 보자면 자릿수가 1개인 시도, 2개인 시도, 3개인 시도a - b - c - aa - ab - ac - ba - bb - bc - ca..

문제 파악https://www.acmicpc.net/problem/11054풀이DP문제이며 푸는데 오래 걸리지는 않았으나,문제에서 놓친 부분이 있어 마지막에 정답을 계산하는 과정에서 조금 헤맸다. 문제를 잘 읽도록 하자 ^_^가장 먼저 오름차순, 내림차순의 길이를 저장하는 DP 배열을 각각 선언해 준다.DP는 "해당 자리의 숫자를 포함"하여 오름차순, 내림차순을 만족하는 수열의 길이를 저장한다.증가(혹은 감소) 수열을 만족했을 때 DP값에서 1을 더해 현재 DP에 저장하도록 하자.오름차순은 인덱스가 증가하는 방향으로, 내림차순은 감소하는 방향으로 순회하도록 했다.다음 {1,2,2,3,1,4} 수열을 예로 들어 보았다.마지막으로 정답은 각각의 자리의 오름차순, 내림차순 DP를 더해 준 다음 1을 빼 준 값..

문제 파악https://www.acmicpc.net/problem/1375어려운 점문제의 입출력에 대한 설명이 아쉬웠다."이름의 길이는 6byte 이하이다"를 주목하면, 입력으로 주어지는 a, b가 문자열이 될 수 있다는 걸 살포시 유추할 수 있다..이 부분을 놓쳐 시간을 많이 썼다.풀이문제에서는 첫 번째로 대소 관계를 입력받고 두 번째로는 쿼리를 입력받는다.문제를 해결하기 위해서는 크게 두 가지를 수행해야 한다.대소 관계 입력 처리 및 관계를 정립Map>을 선언Key : 나이가 많은 이름 저장Value : Key보다 어린 이름을 저장`Alice Jude`, `Alice Tom` 와 같이 이름을 입력받는다면 Map은 다음과 같다.Alice : [Jude, Tom] 의 구조를 갖는다Jude, Tom를 키로..

문제 파악https://www.acmicpc.net/problem/1197풀이제목에서도 알 수 있지만 최소 신장 트리 MST 문제이다(Minimum Spanning Tree)BFS, DFS에서는 방문 여부 체크하는 visited 배열을 쓰다가 사이클을 신경 쓰는 문제를 오랜만에 풀어 흥미로웠다..본론으로 돌아가자면 기본적으로 부모(루트) 노드에 대한 접근이 필요하다.부모 노드에 대한 정보를 저장하기 위해 부모 노드의 인덱스를 값으로 가지는 일차원 배열(parent[])을 선언하여 사용해 주도록 하자.여기서 부모 노드가 되는 조건은 parent[i] = i일 때가 된다.또한 부모 노드가 같은 정점이라면, 같은 트리에 속해있다고도 이해할 수 있다.위 조건을 염두에 두고 핵심적인 두 가지 기능을 구현하도록 하..