알고리즘 문제풀이259 [백준 2533] 사회망 서비스 (SNS) (Swift) https://www.acmicpc.net/problem/2533 DP & DFS 트리인 그래프의 노드간 연결 정보가 간선개수(= 노드개수-1) 만큼 주어지고,모든 노드는 얼리어답터이거나 아니거나 일 때, 내가 얼리어답터면 내 친구들에게 정보를 전파할 수 있음.그래프의 모든 노드가 정보를 전파 받을 수 있으려면 최소 몇명이 얼리어답터여야 하는지.구하는 문제 접근방법DP랑 DFS 같이 쓰는거 생각해내기까지가 어려운 것 같음..블로그 보고 이해하고 풀이함 key 고려사항1. 무방향 그래프 처럼 인접 그래프를 만든다.2. DP 배열은 노드수 * 2 이고,[N][0] : N 번째 노드가 얼리어답터인 경우 최소 얼리어답터수[N][1] : N 번째 노드가 얼리어답터가 아닌 경우 최소 얼리어답터수이다.3. visi.. 2025. 3. 20. [백준 11058] 크리보드 (Swift) https://www.acmicpc.net/problem/11058 DP 왜 디피는 여전히 어려운걸까부분 문제로 열심히 머리굴리다가 안돼서 다른 블로그 참고했다.결론은 점화식을 세우는 것이었음! - 간단해보이는 문제는 점화식으로 풀려고 했었던 것 같은데 오히려 이렇게 복잡해 보이는 문제는 더 점화식으로 풀 생각을 안하는 것 같음.. Key Idea는- 우선 Ctrl-A, C, V를 한묶음으로 생각하기- 비교대상을 A누르기 vs 복사하기 에서 A누르기 vs 1번 복사하기 vs 2번 복사하기 .. .. 로 확장해서 생각하기였다. 점화식 세운 과정dp[i] = max ( dp[i-3] * (1+1), dp[i-4] * (2+1), .. 2025. 3. 19. [백준 16113] 시그널 (Swift) https://www.acmicpc.net/problem/16113 문자열 구현 문제입력이 아래와 같이 문자열의 길이와 #과 . 로만 이루어진 문자열이 들어온다. 40###..#..#.#..#..###..#..#.#..#..###..#.. 이 문자열로 5줄을 만들었을 때, #은 검은칸, .은 흰색칸으로 그리면숫자가 나온다.숫자는 세로로 5칸을 차지하고, 1의 경우 한칸의 열을 차지하는 것을 제외하면 3칸의 열을 차지한다.이런 규칙을 갖고 있는 시그널을 숫자로 해독하는 문제 접근방법딕셔너리에 이차원배열: 숫자 String 을 0~9까지 저장했다. 그리고 공백 "" 에 해당하는 5행이 모두 비어있는 배열로 이루어진 이차원 배열도 "" 이렇게 저장해줌 (빈칸이 여러개 있을 때를 대비한..) 그리고 문자열을 전.. 2025. 3. 13. [백준 1005] ACM craft (Swift) https://www.acmicpc.net/problem/1005 위상정렬, DP, DFS (?)건물들의 건설시간과 건설 순서가 주어진다 (건설 순서 : a, b (a지은 후 b를 지을 수 있음))이때 W번 건물이 지어질 수 있는 가장 짧은 시간 구하는 문제위의 사진의 경우 4번 건물을 2와 3이 모두 지어진 후인 110초 후에 지어지기 시작해서 120초가 걸려야 지어짐 접근방법part 1. 재귀 DFS + DP로 풀어보려고 시도얼마전에 그 강 순서 구하는 것 처럼 구해야할 노드에서 시작해서 역으로 구해보려고 했는데 시간초과났음 part 2. 위상정렬선행하는 노드들이 먼저 수행되어야 내가 수행될 수 있다 -> 이전에 줄세우기 문제와 유사함위상 정렬 사용해서 풀이해야 하는 문제라서 어떻게 할지 고민하다가 .. 2025. 3. 12. [백준 1495] 기타리스트 (Swift) https://www.acmicpc.net/problem/1495 DPN개의 곡마다 볼륨을 조정할 수 있는 크기가 주어진다. 무조건 그 곡을 연주할 때는 현재 볼륨에서 V[i] 를 빼거나 더한 볼륨으로 연주해야함시작 볼륨이 주어지고 볼륨의 최대치가 주어질 때, 마지막 곡을 연주할 수 있는 가능한 최대 볼륨을 출력하는 문제 접근방법이게 DP인지 완탐인지 모르게 풀이하긴 했다.처음에는 2차원 배열에 볼륨을 올리는 경우와 내리는 경우를 저장해서, 최대값을 갱신하는 식으로 하려고 했는데, 뭔가 고려하지 못하는 경우의 수가 있을 것 같았다..저번에 퇴사 문제 풀 때도 이렇게 풀어서 틀렸던 기억그래서 일직선에 0부터 M까지의 볼륨이 나타나있다고 가정하고, 시작 볼륨을 출발지라고 생각하면서출발지로부터 볼륨을 더하고 .. 2025. 3. 11. [백준 1743] 음식물 피하기 (Swift) https://www.acmicpc.net/problem/1743 BFSN*M 격자 판에 K개의 음식물의 위치가 (r,c) 로 주어지고, 인접한 음식들의 묶음 중 가장 큰 묶음의 크기를 출력하는 문제(인접 : 상하좌우로 연결되어 있음) 접근방법우선 2차원 배열 map에 음식물의 위치를 표시하고, map의 모든칸을 확인하면서 방문여부와 음식물여부를 확인해서,방문한 적이 없고 음식물인 칸을 큐에 추가한다.그럼 이제 이 칸이 속한 음식물 묶음의 크기를 BFS를 통해서 구한다. (인접한 음식물을 큐에 넣기, 큐가 빌 때까지 반복, 큐에서 뺄 때 마다 음식물 묶음의 크기 +1)큐가 비어서 반복문이 종료되면 해당 음식물 묶음의 크기를 현재까지 최대 음식물 묶음의 크기를 저장하는 변수 result 와 비교해서큰 값을.. 2025. 3. 10. [백준 2290] LCD Test (Swift) https://www.acmicpc.net/problem/2290구현 2 1234567890 Given numbers (1234567890 as in the example) should be displayed on the LCD display.(my korean keyboard doesn't work..; suddenly.. I may correct this...in the near future.) the first input number (= s) indicates the length of each line that makes up the number display.So you need to make the output displaying the second numbers as in below stri.. 2025. 3. 6. [백준 9470] Strahler 순서 (Swift) https://www.acmicpc.net/problem/9470하천계의 Strahler 순서는 다음과 같이 구할 수 있다.강의 근원인 노드의 순서는 1이다.나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다.재귀방향그래프가 위 그림 처럼 주어졌을 때 각 노드에 순서를 위의 규칙과 같이 구할 수 있다. 이때 마지막 노드인 바다와 만나는 노드의 순서가 이 하천계 그래프의 Strahler의 순서가 되는데 이를 구하는 문제 접근방법처음에 Strahler 순서가 무엇인지를 이해하는데 시간이 걸렸다. 결국 더이상 나가는 강이 없는 노드인 마지막 번째 노드의 순서를 구하는 문.. 2025. 3. 5. [백준 15989] 1, 2, 3 더하기 4 (Swift) https://www.acmicpc.net/problem/15989DP정수 n을 입력받아서 그 수가 1,2,3 들의 합으로 만들어질 수 있는 경우의 수를 출력하는 문제.순서는 상관없다. 접근방법한참 고민하다가 다른 블로그를 보고 풀었는데, 풀이만 간단하게 써있는 걸로는 이해가 잘 안갔다.대부분 점화식을 구해서 풀이하는 것 같았고, 가장 이해가 잘 됐던 설명은1. 모든 수가 1로만 더해서 만들어 질 수 있는 경우를 1가지는 갖고 있음 -> 그래서 1부터 10000까지의 수에 해당하는 경우의 수를 1로 초기화한다.- 1: 1- 2: 1+1- 3: 1+1+1- 4: 1+1+1+12. 그리고 이제 각 수가 1과 2만 더해서 만들어질 수 있는 경우의 수를 구해서 더해주는데, 이는 본인(N)에서 2를 뺀 수(N-2.. 2025. 3. 4. 이전 1 2 3 4 5 6 7 ··· 29 다음 728x90
