[문제] 5014번: 스타트링크 (acmicpc.net) 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net [문제 풀이] BFS를 이용해서 푸는 문제이지만 DFS에 기믹을 1개 추가해서 풀어볼려고 한다. visited 배열을 이용해서 해당 지점에 왔을때 몇번이 걸렸는지 체크를 해주고 이미 방문했던 숫자보다 더 크다면 방문을 하지 말고 return을 해주자. 또한 현재 위치가 0이 되거나 f 보다 크다면 종료를 해주자. 그렇게 도착점에 도착했을때 가능한 방법중 가장 작은값을 출력하도록 하자. 자세한 부분은 코드를 보면서 파악..

[문제] https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net [문제 풀이] 전형적인 BFS 문제이다. 처음 입력받을때 I의 위치를 저장한 후 dx[4]와 dy[4]를 이용해서 상하좌우로 움직이면서 P를 찾을때마다 answer에 추가를 해주자. [회고] 처음에 범위를 nextX >=0 을 nextX > 0 으로 둬서 틀렸다. 범위는 언제나 주의하자. 오랜만에 bfs 문제. 2달만이었지만 아직 감은 안 떨어진듯. 다음엔 이분탐색 + bfs..

[문제] 7568번: 덩치 (acmicpc.net) 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net [문제 풀이] 배열을 만들어둔뒤 해당 위치에서 처음부터 끝까지 배열을 순회하면서 몇개가 해당 위치보다 더 큰값이 있는지 파악하자. 완탐으로 반복문 2개면 간단하게 끝나는 문제. [회고] 처음엔 배열을 복사한뒤에 sort를 해서 어디 위치에 있는지 파악할려고 했는데 해당 코드로는 오류가 발생하였다. 로직 구현상 조건을 만족하는 if문 쪽에서 똑같은 숫자가 생길때 문제가 발생했던 것 같음. [코드] #..

[문제] 12852번: 1로 만들기 2 (acmicpc.net) 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net [문제 풀이] DP를 사용해서 푸는 문제이다. 1~1,000,000까지 DP배열에 해당 숫자를 입력하고( 1에서 순서대로 증가하면 그 숫자만큼의 결과가 나올테니까) for문으로 n까지 돌려보면서 만약 3이나 2로 나눠진다면 나눠진 dp 배열의 숫자에 1을 더하고 이와 같은 방법으로 인해서 도중에 이전 숫자에 1만 더하는 값이 더 커질수 있기 때문에 반복문 처음에 dp[i] = dp[i - 1] + 1;을 선언해줬다. n부터 여태까지 왔던걸 확인하는 것은 반대로 반복문을 통해서 n에서 3이 나눠지고 해당 숫..

[문제] 18352번: 특정 거리의 도시 찾기 (acmicpc.net) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net [문제 풀이] 다익스트라 알고리즘을 응용해서 쉽게 풀 수 있었던 문제. 다만, 기존의 간선의 값이 주어진 문제들과 달리 모두 1로 통일이었기에 다음에 더할값을 1로 통일만 시켰다. [회고] 알고리즘은 모두 구현했으나 입력 코드를 구현 안하고 냈다가 틀렸다. 예시만 한번 돌려보면 바로 알 수 있는 부분이었는데 주의하자. [..

[문제] 1389번: 케빈 베이컨의 6단계 법칙 (acmicpc.net) 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net [문제 풀이] 플로이드-워셜 알고리즘을 이용해서 풀었다. 2차원 배열에 해당 문제에서 나오지 않는 큰 정수를 default로 만들어 둔 뒤 3중 for문(플로이드-워셜)을 이용해서 자기 자신은 0으로 만들고 나머지는 모두 최소 몇번을 진행하면 갈수 있는지 파악하였다. [코드] #include #include using namespace std..