Gi-Log

문제 링크: https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 주어진 예시를 직접 손으로 한 번 써보면, 어떤 계단 형태의 합이 완성되는 것을 알 수 있다. 예를 들면, 가장 앞에 선 사람의 인출 소모 시간은 뒷 사람들의 소모 시간에 포함되기 때문에 지속적으로 전체 소모 시간을 구하는 과정에서 합해지는 것이다. 말이 어려운데 정답부터 이야기하자면, 결국 인출에 소모되는 시간이 긴 사람은 뒤쪽에 서 있는 것이 좋다는 것이다. 인출에 소모 시간이 긴 사람이 내 앞에 서 있다면, ..

문제 링크: https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 문제 풀이에 사용된 알고리즘: 다익스트라, 최단 경로, 더미 노드 문제에서 제시하는 조건(맥세권인지, 스세권인지)를 만족하는 정점(집)들 중에서, (맥도날드까지의 거리) + (스타벅스까지의 거리)가 작은 수치를 보이는 집을 찾는 문제이다. 우선 노드의 수가 굉장히 많고, 인접 행렬이 아닌 간선 형태의 인접 리스트가 주어지기 때문에 ..

문제 링크: https://www.acmicpc.net/problem/20542 20542번: 받아쓰기 세계적인 기업 CTP(Chickens Threaten Programming)에 입사하기 위해서는 영어 받아쓰기 테스트를 통과해야 한다. 영어 받아쓰기는 채용 담당자가 불러주는 단어를 지원자가 받아쓰는 시험이다. CTP에서는 www.acmicpc.net 문제 풀이에 사용된 알고리즘: DP, 편집 거리, Levenshtein Distance (정답 문자열)과 (내가 답안으로 작성한 문자열)이 같아지도록 얼마나 수정(편집, edit)을 진행해야를 수치화하는 문제이다. Levenshtein Distance, 편집거리라고 하는 알고리즘을 적용해서 쉽게 풀 수 있는 문제이다. 동적 프로그래밍(DP)로 구현할 수 ..

문제: SW Expert Academy 1251 하나로 "섬이나 도시, 컴퓨터 등등 어떤 정점들을 모두 잇는 최소 경로가 필요하다!"라는 문제가 나오면 십중팔구 최소 신장 트리(MST) 문제이다. 이 문제 또한 크루스칼 알고리즘을 적용하여 MST를 생성해서 풀 수 있는 문제였다. 본 블로그에서 몇 번 설명을 진행한 풀이가 있는데, 크루스칼 알고리즘을 간단히 설명하면 다음과 같다. 1. 어떤 노드들을 잇는 간선들을, 그 비용을 기준으로 오름차순 정렬한다. 2. 가장 비용이 적은 간선부터 연결을 시작한다. 3. 이 때, 간선을 연결했을 때 싸이클이 발생하게 된다면 해당 간선은 연결하지 않고 건너 뛴다. 위 알고리즘 구현을 위해서는 간선 정보를 어떤 컨테이너에 잘 담고, 정렬할 수 있어야한다. 그리고 싸이클 ..

문제: SW Expert Academy 1256 K번째 접미어 SWEA 1257 K번째 문자열(https://jinho9610.tistory.com/14)과 굉장히 유사하거나 거의 동일한 문제이다. 이번에는 부분 문자열이 아니라 접미어를 모두 구해서 저장하면 되기 때문에, 중복이 발생할 일이 없어서 단순히 벡터를 사용하고 정렬해주면 되는 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 /* SWEQ 1256 k번째 접미어 */ #define _CRT_SECURE_NO_WARNINGS #include #incl..

문제: SW Expert Academy 1257 K번째 문자열 swea에서 문자열 매칭 강의를 듣고 이 문제를 풀게 되는 사람들이 많을텐데, 강의에서 접미어 배열, 트라이, kmp 등등의 고급(?) 알고리즘이 등장한 것에 비해서 꽤나 쉽게 풀리는 문제이다. 굉장히 단순하게 주어진 문자열을 자를 두 위치를 i와 j로 지정하고, 파생되는 있는 모든 경우의 부분 문자열을 생성한다. 그리고 이 부분 문자열들을 저장할 컨테이너가 필요한데, 예시로 주어진 것처럼 food의 경우 o라는 부분 문자열이 중복(2번) 발생할 수 있다. 여기서 중복을 제거하기 위해서 set을 써야함을 눈치챌 수 있었다면 굉장히 쉽게 풀 수 있다. 특히나 해당 문제는 "k번째" 부분 문자열 출력을 위해서 정렬이 필요한데, set을 쓸 경우 ..

문제: SW Expert Academy 1248번 공통조상 (효율적인 풀이인지 검증이 필요한 풀이입니다) 주어진 트리 정보를 바탕으로, 두 정점의 공통 조상을 파악하고, 그 조상의 자식 노드 수 + 1(=서브 트리 크기)를 구하는 문제이다. 개인적으로 트리 문제가 나오면 긴장하는 편인데, 주어진 정보를 바탕으로 트리를 구현해야하나...라는 고민을 처음에 했고, 배열을 이용해서 트리를 구현하려고 했다. 하지만 공통조상을 찾기 위해서는 트리를 거슬러 올라가야할 필요가 있었기에 단순히 각 노드의 부모가 누구인지 parent라는 배열에 저장하고, 각 노드의 자식 노드는 누구(들)인지 child라는 2차원 배열에 저장하기로 하였다. 이 때 2차원 배열인 이유는, 주어진 트리가 이진 트리이기 때문인데, 그냥 vec..

문제 링크: https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제 풀이에 이용된 자료구조: 맵 이 문제에서 중요한 부분은 세 가지로 생각된다. 1. 입력받는 나무의 수가 제시되어 있지 않은데 어느 시점에서 어떻게 입력 받는 것을 중단할 지.... string 자료형 wood 값을 입력 받기 위해서 getline(cin, wood) 함수를 이용하는데 백준에서는 입력이 파일로 들어오므로, 해당 함수가 EOF를 읽게 되면 입력이 종료된다.