본문 바로가기

전체 글114

SPFA Optimization Techniques Shortest Path Faster Algorithm(SPFA) 알고리즘이 무엇인지 궁금하다면 이 게시글을 참고하자. 본 글에서는 SPFA 최적화 기법에 대해서만 서술하겠다. 1. Small Label First (SLF) 큐(Queue)에 최단 거리를 갱신할 수 있는 점(v)를 삽입할 때에, 큐의 가장 앞 부분에 위치한 정점(u)과 최단 거리를 비교한다. 만약 시작점으로부터 u에 이르는 거리보다 v에 이르는 거리가 더 짧다면, 큐의 가장 앞 부분에 v를 삽입하면 된다. 아래의 코드는 BOJ 1753번에 위 방법을 적용한 것이다. 2. Large Label Last (LLL) 큐(Queue)에 최단 거리를 갱신할 수 있는 점(v)를 삽입할 때에, 시작점으로부터 큐에 들어가 있는 정점들에 이르는 최단 거.. 2019. 10. 18.
2018 KAKAO CODE FESTIVAL 예선 A번부터 E번까지 해결하였고, F번은 해결하지 못했다. 대회 중에 내가 정답 판정 받은 코드는 여기서 볼 수 있다. 아래는 간략한 풀이 및 스포일러이다. A. 상금 헌터 간단한 구현 문제. 등수가 0일 때에 주의한다. B. 인형들 N이 500이하이므로 평균과 표준편차 정의에 의해 단순히 계산하면 된다. 자료형 오버플로우에 주의한다. C. 숏코딩 == 연산과 != 연산에 대해 구분하여 생각할 수 있다. == 연산의 경우, 연결 관계를 그래프로 표현하였을 때에 각 component가 독립적인 문제이다. 이 component에서 길이가 가장 짧은 하나의 노드와 다른 노드의 연결 관계를 모두 표현하는 것이 최적임을 알 수 있다. != 연산의 경우에 대해서는 서로 다른 컴포넌트 간의 관계만 표현해주는 것이 최적이.. 2018. 8. 5.
Vertex Cover, Independent Set Vertex Cover : 그래프 G=(V,E)의 정점 집합 중 어떤 부분집합 C를 택하였을 때에, 그래프 상에 존재하는 모든 간선이 C에 속하는 정점과 인접하다면 C를 G의 Vertex Cover라고 한다. 이 때 가능한 C 중 최소 크기의 C를 Minimum Vertex Cover(최소 정점 덮개)라고 한다. Independent Set : 그래프 G=(V,E)의 정점 집합 중 어떤 부분집합 I를 택하였을 때에, I의 모든 원소가 서로 인접하지 않다면(두 정점을 연결하는 간선이 존재하지 않는다면) 해당 집합 I를 Independent Set이라고 한다. 이 때 가능한 I 중 최대 크기의 I를 Maximum Independent Set(최대 안정 집합)이라고 부른다. 이와 연관하여 알아두면 좋은 사실들.. 2018. 7. 20.
OpenCup 튜토리얼 재현이(koosaga)가 재작년에 OpenCup 연습에 대해 알려주었습니다. 하지만 해당 대회의 수준이 매우 높아 연습해 볼 엄두를 못내다가 작년에 용기를 내어 시도해보았습니다. CodeForces에서 snarknews에게 메세지를 보내보았습니다. 아래는 그 내용입니다. snarknews가 알려준대로 http://opentrains.snarknews.info/~ejudge/opencup.cgi 로 가봅니다. 아래와 같은 로그인 화면이 나옵니다. Login과 Password에 snarknews가 알려준 ejudge login과 ejudge password를 각각 입력합니다.로그인하면 아래와 같은 화면이 나옵니다. My Teams 에서는 본인이 속한 학교의 참가자 계정들을 관리할 수 있습니다. 저는 고려대 .. 2018. 5. 4.
TopCoder Marathon Match 100 후기 이번 마라톤 매치에는 50등 이내의 참가자들에게 티셔츠를 주는 이벤트가 있었습니다.문제는 상당히 단순합니다. H*W 크기의 격자 판이 있습니다. 각 격자 칸에는 0 ~ C-1의 숫자가 있습니다. 여러분은 숫자가 같은 두 격자 칸을 선택해서 없앨 수 있는데, 추가적인 조건으로 두 격자 칸을 대각 꼭짓점으로 하는 직사각형 내에 다른 숫자의 격자칸이 있으면 안됩니다. 삭제된 칸은 숫자가 쓰여 있지 않다고 가정합니다. 가능하면 많은 수의 격자 칸을 없애야하는 것이 본 문제의 목표입니다.문제 본문은 다음 링크( MM 100 Problem Statement )에서 보실 수 있습니다. 대회 결과는 다음 링크( MM 100 Standings )에서 보실 수 있습니다. 아래 영상은 제가 작성한 코드가 격자 칸을 없애는 .. 2018. 4. 26.
삼성 신입 SW 역량테스트 대비 문제 추천 1. SW Expert Academy 공식 풀이는 "Learn → Course → Problem-Solving → 해당 문제 학습하기" (링크) 로 확인할 수 있다. 1) [모의 SW 역량테스트] 등산로 조성 2) [모의 SW 역량테스트] 수영장 3) [모의 SW 역량테스트] 탈주범 검거 4) [모의 SW 역량테스트] 미생물 격리 5) [모의 SW 역량테스트] 점심 식사시간 6) [모의 SW 역량테스트] 차량 정비소 7) [모의 SW 역량테스트] 디저트 카페 8) [모의 SW 역량테스트] 벌꿀 채취 9) [모의 SW 역량테스트] 보호 필름 10) [모의 SW 역량테스트] 홈 방범 서비스 11) [모의 SW 역량테스트] 활주로 건설 12) [모의 SW 역량테스트] 특이한 자석 13) [모의 SW 역량테스트.. 2018. 4. 12.