본문 바로가기

개발일지

옛날 이야기이지만 - KOI 2016 (한국정보올림피아드) 후기 ※ 주의!! 이 글은 너무 옛날 이야기를 소재로 하고 있습니다!! ※ 경고!! 이 글 작성자는 기억에 의존해서 글을 작성하고 말았습니다!! 옛날 옛적에... 정말로 개인적인 이야기로 시작하려다가 지웠다. 어쨌든 16년도에 고등부로 한국정보올림피아드를 나갔다. 몇 월이었는지는 까먹었다. 처음 나간 프로그래밍 ( 그 중에 알고리즘 ) 대회였다. 지역 예선이 필기 시험같은 형태로 하고 결선?이었나 그게 이제 당시 경일대학교에서 초등부/중등부/고등부 각각 200명씩해서 거기서 장려상 / 동상 / 은상 / 금상 뭐 그렇게 순위별로 주고, 상위 몇 명이었나 은상~금상 쯤이었나 그 정도 인원을 데리고 뭐해서 국제정보올림피아드 (IOI) 에 보내는 그런 식이었던 것 같다. 지역 예선 사실 시험 내용 자체는 잘 기억이 .. 더보기
백준 9251번 - LCS (Longest Common Subsequence) * 문제 링크 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 내용 요약 문자열이 2개 주어지면 (최대 길이 1000자), 공통된 부분 수열 중 가장 긴 거 길이를 출력해라. (Longest Common Subsequence = 최장 공통 부분 수열) 접근법 매우 유명한 다이나믹 프로그래밍 문제 2 정도로 보면 된다. 항상 그렇듯이, 무엇을 어떻게 메모할지를 정하는 것이 중요하다. 첫번째 힌트로.. 더보기
백준 10254번 - 고속도로 * 문제 링크 https://www.acmicpc.net/problem/10254 10254번: 고속도로 n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다. 고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 www.acmicpc.net 문제 내용 요약 나라에 도시 N개 (2 ≤ N ≤ 200,000) 가 있는데 거기에서 가장 먼 두 도시를 찾아내라. 접근법 이 문제는 회전하는 캘리퍼스 (Rotating Calipers) 를 사용하기 때문에, 컨벡스 헐을 기본으로 깔고 가야한다. 컨벡스 헐에 대한 설명 및 내용은 아래 글 참조 https://syerco0.com/10 백준 1708번 - 볼록 껍질 * 문제 링크 ht.. 더보기
백준 2565번 - 전깃줄 * 문제 링크 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 내용 요약 전봇대에 높이에 따라 1번부터 500번까지 있는데, 전깃줄은 두 전봇대 각각의 번호 한 쌍을 연결한다. 근데 이게 교차되면 합선되니까 교차가 안되게 제거할 전깃줄의 최소 개수를 구해라 접근법 단계별로 풀어보기에도 나와있지만, 이 문제 또한 LIS의 응용 문제다. LIS에 관한 설명은 아래의 링크를 참고하자. https://syerco0.com/22 백준 11053번 - 가장.. 더보기
백준 11054번 - 가장 긴 바이토닉 부분 수열 * 문제 링크 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 내용 요약 어떤 수 S_k 를 기준으로 S_1 부터 S_k 까지 증가, S_k 부터 S_n 까지 감소하는 형태면 바이토닉 부분 수열이라고 부른다. 수열이 주어지면 가장 긴 바이토닉 부분 수열의 길이를 구하여라. 접근법 일단은 이 문제를 풀기 전에 LIS 문제부터 풀고 오는 것을 추천한다. https://syerco0.com/22 백준 11053번 - 가장 긴 증가하는 부분 수열 (LIS) * 문제.. 더보기
아니메컵 1쿨 어영부영 참가 후기 ※ 이 글은 대회가 열린 날 밤에 작성자의 기억을 바탕으로 작성되어 저장해놨던 글로, 그때의 감상 및 시점을 기준으로 작성되었음을 미리 알려드립니다. ※ 정말 어영부영 참가하고 어영부영 글 쓰는 것이라 영양가 없음 주의 ※ 작성자는 BOJHelp의 이용규칙을 읽고 왔습니다. (발견해서 읽었습니다.) 이용 규칙에 어긋나지 않게 글을 쓰려고 했지만, 미처 어긋난 부분이 있을 경우 알려주시면, 알게되는대로 수정/삭제하겠습니다. * (23.02.08 추가) 대회 링크 있으면 좋을 거 같아서 https://www.acmicpc.net/contest/view/938 아니메컵 1쿨 www.acmicpc.net 그냥 지나가다가... 그냥 평소처럼 솔브닥 잔디 심어야지 하는데 대회를 열어보니 아니메컵 1쿨이 진행 중이었.. 더보기
백준 11053번 - 가장 긴 증가하는 부분 수열 (LIS) * 문제 링크 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 내용 요약 수열(크기 1 ≤ N ≤ 1000)이 주어졌을 때, "가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)"의 길이를 구해라 예) {1,2,1,3,2,5} 면 {1,2,3,5} 가 LIS 다. 접근법 (힌트에서부터 차근차근) 피보나치를 제외하면 가장 유명한 .. 더보기
백준 11376번 - 열혈강호 2 * 문제 링크 https://www.acmicpc.net/problem/11376 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, www.acmicpc.net 문제 내용 요약 강호네 회사에서는 또 직원 N명과 할 일 M개가 있다. (1 ≤ N,M ≤ 1000) 직원 한 명은 2 개의 일만 가능하고, 한 일에는 한 명만 배정되어야 한다. 최대 몇 개의 일을 할 수 있을까? 접근법 11375번 열혈강호 문제를 먼저 풀어오기를 추천한다. https://syerco0.tistory.com/19 백준 11375번 - 열혈강호 * 문제 링.. 더보기
728x90
반응형

티스토리툴바