Algorithm (2139) 썸네일형 리스트형 (C++) - 백준(BOJ) 18223번 : 민준이와 마산 그리고 건우 https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net dijkstra문제였습니다. 📕 풀이방법 📔 입력 및 초기화 인접그래프를 만들어줍니다. 📔 풀이과정 1 ~ p까지의 최단거리 + p ~ v까지의 최단거리 cost + nextCost){ dist[next] = cost + nextCost; pq.push({dist[next],next}); } } } return dist[endPoint]; } i.. (C++) - 백준(BOJ) 2021번 : 최소 환승 경로 https://www.acmicpc.net/problem/2021 2021번: 최소 환승 경로 첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발 www.acmicpc.net 5214번과 같은 bfs 문제였습니다. 📕 풀이방법 같은 호선에 속해있는 역끼리는 간선으로 연결할 필요가 없습니다. 유의미한 간선은 역 호선 또는 호선 역 뿐입니다. 인접그래프를 형성할 때 정점을 역, 호선으로 생각하며 역과 호선 사이를 간선으로 해 형성해줍니다. 호선은 동그라미, 역은 네모로 그림을 그렸습니다. 이렇게 간선의 개수를 줄일 수 있습니다. 이제 탐색할 .. (C++) - 백준(BOJ) 5214번 : 환승 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net bfs 문제였습니다. 📕 풀이방법 같은 호선에 속해있는 역끼리는 간선으로 연결할 필요가 없습니다. 유의미한 간선은 역 호선 또는 호선 역 뿐입니다. 인접그래프를 형성할 때 정점을 역, 하이퍼튜브로 생각하며 역과 하이퍼튜브 사이를 간선으로 해 형성해줍니다. 📔 입력 및 초기화 m개의 호선에 대해 각 호선에 속한 정점들을 k개씩 입력하고 무방향 인접리스트를 형성해줍니다. 하.. (C++) - 백준(BOJ) 20167번 : 꿈틀꿈틀 호석 애벌레 - 기능성 https://www.acmicpc.net/problem/20167 20167번: 꿈틀꿈틀 호석 애벌레 - 기능성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net brute force로 푼 문제였습니다. 📕 풀이방법 먹이를 선택 또는 선택하지 않는 2가지 경우의 수가 n만큼 발생하기 때문에 n이 20인경우 2^20으로 모든 경우의 수를 확인해도 TLE(시간초과)가 발생하지 않습니다. 📔 입력 및 초기화 먹이별 에너지를 일차원 배열 energy에 저장합니다. 📔 풀이과정 0번 먹이부터 시작해 선택하지 않는 경우, 여태 먹은 먹이의 누적합.. (C++) - 백준(BOJ) 20166번 : 문자열 지옥에 빠진 호석 https://www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net dfs문제였습니다. 📕 풀이방법 k를 입력받을 때마다 dfs를 수행한다면 tle입니다. 따라서 전처리로 dfs 후 k를 입력받아야 합니다. 📔 입력 및 초기화 n,m,k 입력 후 문자열 배열 board에 적절히 입력받습니다. 📔 풀이과정 1. n행 m열을 모두 돌며 board[i][j]를 시작점으로 dfs를 수행해 줍니다. 2. dfs 수행 시 만든 문자열을 모두 map에 넣어줍니다. 해당 문자열의 value를 1씩 증가시킴으로써 경우의 수를 구할 수 있습니다. 📔 정답출력 k만큼.. (C++) - 백준(BOJ) 1755번 : 숫자놀이 https://www.acmicpc.net/problem/1755 1755번: 숫자놀이 79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 www.acmicpc.net 문자열과 정렬문제였습니다. 📕 풀이방법 📔 입력 및 초기화 m, n을 입력받습니다. 숫자를 문자열로 변환시킨 값을 key, 숫자를 value로 한 map 변수 numMap을 선언합니다. 📔 풀이과정 i는 m ~ n까지 loop를 돌며 1씩 증가합니다. 한 자리 수일 때 i를 문자열로 변환시켜 map에 넣습니다. 두 자리 수일 때 i / 10 과.. (C++) - 백준(BOJ) 20207번 : 달력 https://www.acmicpc.net/problem/20207 20207번: 달력 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장 www.acmicpc.net 정렬 후 구현하는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 pair형 vector변수 plan을 선언합니다. 그 후 n만큼 차례대로 입력받습니다. 이 후 조건대로 시작날이 가장 앞서고 만약 같다면 일정이 제일 긴 pair들 순으로 정렬해줍니다. 📔 풀이과정 직사각형을 만드는 조건은 연속된 일정이 width 즉, 너비가 되고 겹치는 날의 개수가 height 즉, 높이가 되며 다음 일정이 비어있다면 widt.. (C++) - 백준(BOJ) 1284번 : 집 주소 https://www.acmicpc.net/problem/1284 1284번: 집 주소 재석이는 대문에 붙이는 (주소를 나타내는) 호수판 제작업체의 직원이다. 고객에게 전달할 호수판은 숫자와 숫자 사이 그리고 왼쪽 오른쪽으로 적당히 여백이 들어가 줘야하고 숫자마다 차지하 www.acmicpc.net 간단한 산술 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 문자열 s가 "0"일 때까지 입력합니다. 📔 풀이과정 1. 문제에서 모든 형태의 문자열은 s.size() + 1 만큼의 간격을 가지게 됩니다. 따라서 이는 변수 width에 고정적으로 더해집니다. 2. 이를 제외한 간격은 글씨자체의 간격뿐이므로 1일 때는 2, 0일 때는 4, 이외의 숫자에는 3을 문자 하나씩 확인해가며 출력할 정답 변수 width에 .. 이전 1 ··· 138 139 140 141 142 143 144 ··· 268 다음
