어흥

문제 링크: https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다) 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되 www.acmicpc.net 1. 주의할 점 - 모든 Node에 대해 돌릴 경우 N^2 -> 시간초과 발생 - 시작 Node를 기준으로 Leaf 까지..

문제 링크: https://www.acmicpc.net/problem/14405 14405번: 피카츄 피카츄는 "pi", "ka", "chu"를 발음할 수 있다. 따라서, 피카츄는 이 세 음절을 합친 단어만 발음할 수 있다. 예를 들면, "pikapi"와 "pikachu"가 있다. 문자열 S가 주어졌을 때, 피카츄가 발음할 수 있는 문자열인지 아닌지 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 주의할 점 - 3가지 단어 말고 다른 문자로 시작해도 NO 출력시켜야한다. 2. 구현 - Idx=0을 기준으로 입력받은 String에서 Idx번째 문자가 셋중 하나와 같으면 나머지 또한 같은지 비교한다. - 셋과 모두 다르다면 While문을 빠져오도록 설계한다. #include #include ..

문제 링크: https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다. www.acmicpc.net 1. 주의할 점 - BFS로 풀지만 어느 방향에서 왔는지 기억하지 않으면 답을 도출할 수 없다. - 시작점을 기준으로 반대지점까지 도착하도록 설계하면 된다 - 거울을 놓을 수 있지만 놓지 않는 경우도 처리해야한다. 2. 구현 - 한 방향에서 시작해서 끝까지 ..

문제 링크: https://www.acmicpc.net/problem/9207 9207번: 페그 솔리테어 문제 페그 솔리테어는 구멍이 뚫려있는 이차원 게임판에서 하는 게임이다. 각 구멍에는 핀을 하나 꽂을 수 있다. 핀은 수평, 수직 방향으로 인접한 핀을 뛰어넘어서 그 핀의 다음 칸으로 이동하는 것만 허용된다. 인접한 핀의 다음 칸은 비어있어야 하고 그 인접한 핀은 제거된다. 현재 게임판에 꽂혀있는 핀의 상태가 주어진다. 이때, 핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로 하려고 한다. 또, 그렇게 남기기 위해 필요한 최소 이동횟수를 구하는 프 www.acmicpc.net 1. 주의할 점 - 백트레킹을 통해서 구현한다(핀의 최대 개수: 8) - 맵을 바꾼 후, 다시 돌아왔을 때 맵을 복구하..

문제 링크: https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 1. 주의할 점 - 시작지점과 끝지점(고속도로의 길이)도 포함해야한다. - 이분탐색으로 해결한다. 2. 구현 - 첫 번째 구현방법: 구간과 구간사이의 길이를 구해서 우선순위큐에 적재한다. 우선순위큐의 Top에 있는 원소를 뽑아서 반..

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGGNB6cnEDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 숫자 하나씩 직접 할 경우 시간초과발생 - 10^15의 마지막 자리수를 Long으로 받아오고(Integer로는 10^15자체를 선언할 수 없다), Number 배열의 Index에 접근시 런타임에러 발생(이거 때문에 2번 틀렸다) - 각 자리수의 중요성 2. 구현 (1) 백준의 1019번 문제 "책페이지"와 푸는 방법이 거의 똑같다. (2) Start와 End를 입력받..

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 4방향 탐색 : X, 8방향 탐색: O - 2차 배열을 3개 사용하며 방문했는지 체크하는 Check[][], 정답 배열인 Mine[][], 입력받는 배열인 Arr[][]를 사용한다. 2. 구현 - 만약 입력받은 배열 Arr[][]의 값이 '*' 즉, 지뢰라면 현 위치 기준으로 8방향에 Mine배열에 1씩 더한다. - Mine배열을 처음부터 끝까지 살피면서 Check값..

문제 링크: https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 1. 주의할 점 - DP문제다. 백트레킹으로 접근할 생각하지 말자 - DP문제라는건 알았지만 점화식을 세우는게 쉽지 않다. 문제를 해결하고 다른사람들의 점화식을 확인해본 결과 나와 같은 점화식은 찾지못했다(내가 너무 어렵게 해결한것 같다). 2. 구현 - 우선 나는 0,1로 이루어진 비트라고 생각하고 접근했다(문제와 달리 행:2 , 열:N이라고 가정) - DP[숫자의 길이(=N)][마지막에서 2번째 번호][마지막 번호] 의 형태로 배열을 세웠다. ex)[N][0][0] : N의 길이면서 마지지막이 00으로 끝나는 수,..