Let's Begin Programming

참가자 리스트 participant와 완주자 리스트 completion이 입력으로 주어지고 완주하지 못한 선수를 출력하는 문제이다. 참가지 리스트에 있는 선수들 중에서 완주자 리스트에는 없는 선수를 찾으면 될 것 같지만 문제를 보면 동명이인이 존재할 수 있다. 동명이인을 처리하기 위해서 dictionary를 사용했다 처음에 모든 참가자에 대한 key를 생성하고 value를 0으로 초기화 한다. 그리고 참가자와 완주자 리스트를 합한 리스트를 순회하면서 해당하는 선수의 value를 1 증가시킨다. 그리고 이 딕셔너리에 저장된 value들 중에서 홀수를 찾는다. 만약에 동명이인이 아닌 A 선수가 완주를 했다면 딕셔너리에서 A의 value는 2일 것이다. 동명이인이라고 해도 모두 완주했다면 짝수를 값으로 가질 ..

개발 공부 (알고리즘) 2021. 8. 18. 01:38

온라인으로 2주간 패스트캠퍼스 강의를 수강한 후에 오프라인 과정이 시작되었다. 강의가 시작되는 월요일 전날 일요일에 오후까지 와서 포항공대 국제관에 숙소를 배정받는다. 국제관은 포항공대에 있는 호텔로 2인 1실 배정이었다. 서울역 - 포항역 KTX로 2시간 30분정도 소요되었다. 포항역에서 포항공대까지는 택시로 이동했다. 일찍 도착해서 짐을 풀고 잠시 쉬고 룸메이트를 만나서 인사를 나눈 뒤 강당으로 이동해 안내를 받았다. 교육과 생활에 관련된 안내를 받은 뒤에 숙소로 이동했다. 교육과정을 이수하면서 교육적인 것을 이야기 하기 전에 생활하면서 미리 알고가면 편했을 것 같은 것들을 정리해본다. - 식사는 아침 점심 저녁 모두 RIST 식당에서 무료로 제공해준다. - 포항공대의 도서관, 체육관, 운동장을 이용..

청년 AI - Big Data 아카데미 2021. 8. 14. 01:13

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 해결하지 못하고 다른 분들의 해결 방법을 참고했다. 먼저 주어진 물건의 개수와 무게 만큼의 이차원 배열을 생성한다. 1번 물건부터 n번 물건까지 하나씩 살펴보는 것이다. 현재 내가 보고 있는 물건이 1에서 k까지 배낭의 무게가 달라질 때마다 가치가 어떻게 달라지는 지를 기록한다. 만약에 현재 배낭의 무게가 현재 내가 보고있는 물건의 무..

개발 공부 (알고리즘) 2021. 4. 17. 03:57

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 앞선 문제들과 유사한 문제다보니 비교적 쉽게 해결했다. 연속해서 붙어있는 수열의 합이 가장 큰 것을 구하는 문제이다. 일단 연속이라고 했으니 앞에서부터 차례대로 숫자를 살펴본다. 만약에 다이나믹 프로그래밍, 메모를 이용하지 않는다면 모든 경우의 수를 계산해서 최댓값을 구할 것이다. 효율을 위해 메모를 이용한다. 메모에 적는 내용은 현재 보고 있는 숫자와 이전 결과에 현재 숫자를 더했을 때 둘 중에 더 큰 값이다. 예를 들..

개발 공부 (알고리즘) 2021. 4. 16. 21:20

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제 역시 혼자 풀지 못하고 다른 분들의 글을 참고했다. 다이나믹 프로그래밍 문제들은 간단해보이지만 다이나믹 프로그래밍을 이용해야겠다는 생각과 어떤 식으로 해결 방법을 구성할 지가 답을 보고도 쉽게 이해되지 않는다. 두 문자열을 비교해서 같은 부분 문자열의 최대 길이를 찾는 문제이다. 이전에 풀었던 증가하는 부분 수열 문제와 비슷하다고 생각해서 문자 하나씩 확인하..

개발 공부 (알고리즘) 2021. 4. 15. 03:45

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 감이 안 와서 다른 분들의 블로그를 참고했다. 결과적으로 이전에 했던 가장 긴 증가하는 부분수열을 구하는 방법을 이용하면 됐다. 문제는 전깃줄이 겹치지 않도록 전깃줄을 제거하는 최소 갯수를 구하는 것이다. 주어지는 전깃줄 정보가 순서대로 주어지지 않기 때문에 먼저 A 기준으로 정렬을 해준다. 그리고 A에 연결된 B의 정보를 훑으면서 증가하는 수열을 찾는다. 전깃줄이 꼬이지 않는 경우는 B의 숫자가 계속 증가하는 경우다..

개발 공부 (알고리즘) 2021. 4. 14. 23:49

www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이전에 풀었던 11053번 가장 긴 증가하는 부분 수열 문제의 응용버전이다. 바이토닉 수열은 증가하는 부분과 감소하는 부분이 동시에 존재한다. 증가하는 수열과 감소하는 수열을 둘로 나누어서 메모하는 아이디어는 생각했지만 실제로 어떻게 구현할 지를 생각하지 못했다. 다른 분의 글을 참고해서 이해했다. 예를 들어 본다. 1 2 3 2 1 이라는 바이토닉 수열이 있다. 증가하는 부분은 1 2 3 감소하는 부분은 3 2 1 이다. 이전에..

개발 공부 (알고리즘) 2021. 4. 13. 01:45

www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 처음에는 단순하게 반복문을 돌리면서 이전의 최댓값보다 더 큰 값이 나오면 추가한 다음 전체의 길이를 출력하는 방법을 이용했다. 결과적으로 접근법은 유사했으나 문제 이해를 못했던 것 같다. 일단 구해야하는 수열은 증가하는 수열이다. 그리고 그 수열 중에서 가장 길이가 긴 수열을 구해야 한다. 먼저 각각의 숫자를 순서대로 탐색한다. 증가..

개발 공부 (알고리즘) 2021. 4. 13. 00:07