본문 바로가기

알고리즘

[Lv2]소수찾기(C++) 1. 문제 programmers.co.kr/learn/courses/30/lessons/42839?language=cpp 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 2. 접근 방법 1) numbers의 각 자리 숫자를 char 단위로 입력 받음 => vector v; 2) 만들 수 있는 숫자의 길이는 최소 한 자리수부터 최대 v.size()자리 수 이므로, 각 자리수 만큼 순열을 구함 (ex. 1개 순열, 2개 순열 ,.... v.size() 개 순열 을 구함) 3) 각 순열에 의해 만들어.. 더보기
[2468]안전 영역(C++) 1. 문제 www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 2. 접근 방법 1) 물에 잠기는 기준 값을 standard라고 하면, standard는 1~101까지 존재한다. 2) 각 standard기준보다 높이가 높아서 물에 안잠겼으면서 방문했던 적이 없었던 지역을 기준으로 dfs를 수행하여 방문처리를 한다. 3) standard별 그룹 수가 나오는데, 가장 큰 수를 출력한다. 3. 실수했던 부분 & 처음 알았던 부분 1) 나는 처음에 물에 잠기는 범위를 지역 .. 더보기
[Lv2]가장 큰 수(C++) 1. 문제 programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 �� programmers.co.kr 2. 접근 방법 1) 처음에 "한자리수 끼리 비교하는 법 ", "두 자리 수끼리 비교하는 법".. 등 자리수 별로 조건을 달리해야 하나 고민이 있었다. 그런데 많은 자리수를 일일히 다 비교하는 게 말이 안된다고 생각했고, 다른 방법으로 접근했다. 2) string으로 표현하라는 게 힌트라고 생각했.. 더보기
[Lv1] K번째 수(C++) 1. 문제 programmers.co.kr/learn/courses/30/lessons/42748 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 2. 접근 방법 1) array에 있는 값들을 -> 자른 후 -> 정렬하여 -> K번째 수를 구하여 answer에 넣는 단순 구현 문제 => command[i]에 주어진 세 값(i,j,k)를 사용하여 array[i]~array[j]까지 범위만 복사하여 -> 정렬 후 -> K-1번째 값을 구함 2) 해당 문제는 assign함수를 알면 쉽게 풀 수 있었음 3. 실수했던 부분 & 처음 알았던 부분 * assign함수 1) v.assign.. 더보기
[Lv2]구명보트(C++) 1. 문제 programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 2. 접근 방법 1) "한 보트엔 최대 2명만 들어갈 수 있다." 라는 점에서 greedy 접근 방식을 생각했다. ( 만약 한 보트에 최대 인원이 정의되어있지 않았다면 DP로 풀어야 했는데, 최대 2명이므로 가장 무거운 사람 + 가장 가벼운 사람을 한쌍으로 묶으면 된다. ) 2) 사람을 무게 순으로 정렬시킨 후, (가장 무거운 사람(peo.. 더보기
[Lv2]삼각달팽이(C++) 1. 문제 programmers.co.kr/learn/courses/30/lessons/68645 코딩테스트 연습 - 삼각 달팽이 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] programmers.co.kr 2. 접근 방법 1) 규칙을 찾기 어려워서 단순 구현으로 생각했음 2) 아래 -> 옆 -> 위 방식으로 값을 채우고, 값을 채우는 개수가 처음 아래 방향으로 N개, 우측 방향으로 N-1개, 위 방향으로 N-2개..처럼 채우는 개수를 하나씩 줄이는 규칙을 발견했다. 3) cnt : (아래,옆,위) 방향으로 갈 "개수", num : 배열에 넣을 "값",minCnt : 해당 방.. 더보기
[1261] 알고스팟(C++) 1. 문제 www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 2. 접근 방법 1) (1,1) -> (N,M)으로 가는 모든 경우를 탐색해야 하므로 BFS / DFS로 구현 2) 문제에서 "부숴야 하는 벽의 최소 개수"를 구해야 하므로 단순 BFS / DFS에서 지금까지 깬 벽의 개수를 고려해야 함 3) 두 가지 경우의 수 - DFS 형식으로 푸는 경우 : 재귀 + 배열을 사용하여 배열 map[N][M]에는 (1,1) -> (i,j)까지 도.. 더보기
[2606] 바이러스 1. 문제 www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net 2. 접근 방법 1) PC 간의 연결 정보를 나타내기 위해 2차원 벡터를 선언한다(v). 2) dfs의 방문 정보를 나타내기 위해 bool 타입의 벡터를 선언한다(visited). 3) PC간 연결 정보는 양방향이므로 v에 값을 넣을 때 이 점을 유의하여 a-b의 연결 정보를 v[a]와 v[b]에 각각 저장한다. 4) 재귀 함수인 dfs를 선언하여 감염된 PC개수인 cnt를 반환한다. 3. 실수했던 부.. 더보기

티스토리툴바