일기 (사실 근황임) (52) 썸네일형 리스트형 solved.ac CLASS 6 구간 트리 문제 정리 solved.ac 알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다. solved.ac 서론 이 글에서 제시된 문제 중 Fenwick Tree로 풀이할 수 있는 문제들은 Segment Tree로 풀이할 수도 있습니다. 일부 스포일러가 존재합니다. 1. BOJ 2042번 - 구간 합 구하기 Fenwick Tree 기초 2. BOJ 2357번 - 최솟값과 최댓값 Segment Tree 기초 3. BOJ 11505번 - 구간 곱 구하기 Segment Tree 기초 수의 범위에 0이 포함되어서 Fenwick Tree 풀이는 어려워보인다. 4. BOJ 14428번 - 수열과 쿼리 16 Segment Tree 5. BOJ 2243번 - .. KTH Challenge 2014 G - Intercept Intercept – Kattis, Kattis Fatima commutes from KTH to home by subway every day. Today Robert decided to surprise Fatima by baking cookies and bringing them to an intermediate station. Fatima does not always take the same route home, because she loves to admire the artwork inside di open.kattis.com 문제를 다음과 같이 요약할 수 있다. 가중치가 있는 유향 그래프 G가 주어진다. 정점 s에서 정점 t로 가는 모든 최단 경로에서 반드시 지나는 정점 집합 V를 구하여라. 나의 .. 2022년 11월 2일 일기 10월 30일에 2022 SKKU 프로그래밍 대회 in 소프트의 밤 Open Contest에 참가하였다. 신나게 털려서 부족한 부분을 채우고 있는데 너무 정신 없어서 블로그에 접속할 수가 없었다. 앞으로 며칠간 다음과 같은 주제를 포스팅하려고 한다. 시간 여유가 그리 많지는 않아서 간단히 쓰거나 생략할 수도 있다. 1. 2022 SKKU 프로그래밍 대회 in 소프트의 밤 Open Contest 아직 모든 문제를 업솔빙하지 못하였다. 업솔빙이 끝나는 대로 올리려고 한다. 2. Fenwick Tree 이미 Fenwick Tree에 대하여 쓴 적이 있어서 개념은 생략하고 연습 문제 풀이만 간단히 올리려고 한다. 3. Segment Tree Fenwick Tree처럼 구간을 관리하는 자료 구조이다. Fenwic.. 자격증 목록 소재가 고갈되어서 현재까지 취득한 자격증 목록이나 포스팅하려고 한다. 2012-09-21 워드프로세서 2020-05-29 컴퓨터활용능력 1급 2020-11-12 정보처리기사 2021-08-08 상공회의소 한자 3급 2021-08-20 한국사능력검정시험 1급 2021-10-01 리눅스마스터 2급 2021-11-08 비서 1급 2021-12-17 SQL 개발자 2021-12-31 정보기기운용기능사 2022-03-25 데이터분석 준전문가 2022-06-10 리눅스마스터 1급 2022-07-01 G-TELP Level 2 82 2022-07-13 위험물기능사 2022-07-15 빅데이터분석기사 2022-07-19 IT PLUS Level 5 2022-09-02 사무자동화산업기사 대다수가 복무 중에 취득하였다. .. CP4 Chapter 1. Introduction Competitive Programming 4판을 읽고 있다. 번역본이 아직 출간되지 않아서 원서로 읽고 있다. 2017년에 3판이 번역본으로 출간되었었는데 현재 절판되었다. 우리나라에서 이 책으로 공부하는 사람은 거의 없는 듯 하다. CP4에 대한 정보는 다음 링크에서 확인할 수 있다. 3판의 단점은 UVa 문제만 수록하고 있다는 것이다. 2022년 기준으로 UVa는 매우 구식 사이트이다. 과거 사이트 운영자였던 Miguel A. Revilla가 사망한 이후로 내리막길만 걷고 있다. 현재 시점에서 UVa에 접속할 이유는 전혀 없다. 4판부터는 UVa 외에도 Kattis 문제를 수록하고 있다. 2주 전부터 Kattis를 사용해봤는데 괜찮아 보인다. 예전에 BOJ 사용할 때는 한국어 문제만 찾아다녔는데 K.. COCI 2014/2015 Contest #4 Task SABOR Sabor – Kattis, Kattis A land far, far away has N Members of Parliament (MP). They had a turbulent and passionate debate on the law on amendments to the law on a new referendum on referendums. From Monday to Friday, all MPs joyfully came to work and argued all day. A diligent ne open.kattis.com 문제를 다음과 같이 정리할 수 있다. 각 정점의 차수가 5 이하인 그래프가 주어질 때 모든 정점을 빨간색 또는 파란색으로 칠하려고 한다. 이때 각 정점에 대하여 자신과 동일한 색을 가.. 부동 소수점 연산의 위험성 부동 소수점 타입의 연산 결과는 부정확합니다. long double 타입도 마찬가지입니다. 되도록이면 부동 소수점 연산을 사용하지 맙시다. 반드시 필요하다면 EPS를 적극적으로 이용합시다. 10+ WA 받고 열 받아서 데이터 까보면서 얻은 교훈입니다. 부동 소수점 연산이 부정확하다는 것은 예전부터 알고 있었습니다. 그런데 이렇게 부정확할 줄은 몰랐습니다. 웬만하면 쓰지 마세요. 끝 BOJ 18789번 814 - 2 문제 18789번: 814 - 2 이 출력된 표에서는 1부터 112까지 읽을 수 있지만, 113은 읽을 수 없어 112점을 받는다. www.acmicpc.net 풀이 본 문제와 같은 최적화 문제는 유전 알고리즘으로 접근할 수 있다. 그렇다고 해서 단순히 유전 알고리즘을 이용하기만 하면 풀리는 문제는 아니다. 혁신적인 아이디어와 다양한 실험을 통하여 알고리즘의 성능을 향상시켜야 한다. 나는 문병로 교수님의 저서와 논문을 다수 참고하였다. 1등 2022년 9월 20일 기준 잠시나마 1등을 차지하고 있다. 티어 2022년 9월 20일 기준 이 문제의 티어는 루비 3인데, 나는 다소 과대평가되었다고 생각한다. 일반적인 유전 알고리즘에 혁신적인 아이디어 하나만 더하면 8140점은 쉽게 도달할 수 있다. 개인적으로.. 이전 1 ··· 3 4 5 6 7 다음
