본문 바로가기 메뉴 바로가기

welcome!

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

welcome!

검색하기 폼
  • 전체보기 (230)
    • IT 저서 (20)
      • 가상 면접 사례로 배우는 대규모 시스템 설계 기초 (12)
      • 데이터 중심 애플리케이션 설계 (8)
    • Discrete mathmatics and Pro.. (41)
      • 1 논리 (14)
      • 2 기초적인 구조들 : 집합, 함수, 순열, 시그.. (3)
      • 3 알고리즘 (2)
      • 5 재귀와 귀납 (2)
      • 6, 8 경우의 수와 그 응용(dp) (7)
      • 9 관계 Relations (4)
      • 10 그래프 (1)
      • 11 트리 (6)
      • etc radom, samplings (1)
    • 알고리즘 문제 (7)
      • math (8)
      • implementation (17)
      • sort, search (5)
      • data structure (5)
      • Brute Force (4)
      • BFS (0)
      • DFS and Simillar (4)
      • DP (11)
      • graph (7)
      • Flow (1)
      • string (0)
      • 입사문제 (2)
    • 운영체제 (5)
      • 1 overview (0)
    • 네트워크 (12)
    • 데이터베이스 (3)
    • 컴퓨터구조 (0)
    • 개발이야기 (19)
      • 포트폴리오 (1)
      • Flutter (2)
      • Wpf (1)
    • 자유공간 (12)
    • Calculus (0)
    • IoT 과정 (39)
  • 방명록

알고리즘 문제/graph (7)
백준 11657 타임머신

문제 보기https://www.acmicpc.net/problem/11657 벨만포드 알고리즘이다. 알고리즘 분류 기능을 이용해 풀수있는 가장 첫 문제이며, 벨만포드 알고리즘을 그대로 사용하면 된다.기존소스에 반례가 있었다. 출발점에서 도달 할 수 없는 정점 간에 음수 경로가 존재해도 음수사이클 존재를 판단했던 것이다. 그리고 INF 값이 너무 작았다. 500*10,000+1 이상되어야한다. 수정하였음. 등록일이 18년 2월이었으니... 1년 8개월만에 수정한거네요!` 소스보기https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/11657.cc

알고리즘 문제/graph 2018. 2. 27. 18:17
백준 5719 거의 최단경로

백준 5719 거의 최단경로 난이도 꽤 있다고 생각함.https://www.acmicpc.net/problem/5719 다익스트라를 이용하여 최단경로를 저장해나가는데 pred 벡터에 이전 경로를 갱신해준다.그리고 이전경로를 모두 탐색해 그 경로를 재귀적으로 접근하여 -~ 사용할 수 없는 간선으로 만든다.그리고 다시 다익스트라를 활용한다. 그러면 거의 최단경로가 나온다. 개념적으로 와닿지만, pred 를 어떻게 벡터로 만들고, ... 그리고 어떻게 삭제하는가... 에 대해서 생각하는데 시간이 많이 걸린 문제였다. 여기서 아마 구현능력과 논리력이 갈리었을거라 생각한ㄷㅏ 리저널,, 문제였는데 어렵긴 어려운것 같다. 난 제한 시간내에 못풀었다 100% ㅋㅋㅋ. 이 문제로 인해 느낀점은, pred 벡터에 targ..

알고리즘 문제/graph 2018. 2. 23. 05:11
백준 1766 문제집

백준 1766 문제집원문보기https://www.acmicpc.net/problem/1766 방법론 : 위상정렬 + 우선순위 큐 이 문제는 위상정렬 문제이지만, 스페셜 저지가 아니였다. 즉 정답이 하나라는 이야기인데, 어떻게 이런 조건을 가지게 되었는지 살펴보자. 문제를 보면 n개의 문제와 m개의 간선 정보가 나온다. "문제" (실제 문제와 문제의 예제에 나오는 문제와 헷갈리지 않게 쌍따옴표로 강조했다.) 의 난이도가 낮는 것부터 우선순위를 두고싶다고 한다.그러면서도, 동일한 난이도가 없기 때문에 스페설 져지 문제가 아닌 답이 하나로 결정될수 있었다. 큐에서 꺼낼땐 난이도 낮은것부터 꺼내었다.C++의 STL priority_queue 자료구조를 이용했다. 소스보기 https://github.com/ing..

알고리즘 문제/graph 2018. 2. 1. 17:51
백준 2252 줄세우기

백준 2252 줄세우기원문보기https://www.acmicpc.net/problem/2252 방법 : topological sort n명의 학생과 m 개의 2-순서쌍이 주어진다. 이 때 전체적인 키비교 수열, 즉 n-순서쌍을 생성하시오. 라는 문제이다. 이 문제는 스페셜 저지 문제인데, 정답이 여러개 존재할 수 있다는 이야기이다. 위상정렬 문제는 주어진 방향간선으로 여러 개의 정렬된 n-순서쌍이 나올수 있는 것이다.한번 살펴보면, 2번 예제는4 24 23 1 은 그래프 그룹이 두 개이므로, (4, 2, 3, 1), (4, 3, 2, 1), (4, 3, 1, 2), (3, 1, 4, 2) 등등...몇 종류가 된다. 여기까지는 약간 응용없는 위상정렬인것 같다.아직은 방법론을 배우자는 입장이니까, 포스팅 된..

알고리즘 문제/graph 2018. 2. 1. 16:39
백준 1005 acmcraft

백준 1005 acmcrafthttps://www.acmicpc.net/problem/1005 startcraft 게임처럼, 빌드 순서가 주어진다. n개의 건물이 있고, 빌드 순서 간선은 k개가 있다고 하자.그 n개의 건물들 중 순서도에 따라 지어가는 도중에 어떤 w 건물을 이기는게 확정된다고 한다.이때 이길 수 있는 w 건물을 짓게되는 최소시간이 몇인가? 방법론 : 위상정렬 (topological sort) + 간단한 수학 위상정렬을 할 때 입차수가 0인 임의의 u노드를 현재 그래프에서 빼주는데,이 때 남아있는 그래프에서 그 노드 u를 포함하고 있는 간선E가 연결된 나머지 노드 v에 대해 indegree를 뺴주는 것을 확실히 한다. 여기 까지는 naive한 위상정렬 알고리즘으로 구현할 수 있다. 그런데..

알고리즘 문제/graph 2018. 2. 1. 15:31
백준 2623 음악프로그램

백준 2623 음악프로그램문제보기https://www.acmicpc.net/problem/2623 n 명의 가수와 m명의 pd가 주어진다.m 명의 각각 pd는 자신만의 방법으로 음악방송 프로그램을 짜려고한다.각 pd는 선호하는 가수들의 방송 순서를 정해놓는데, 각 pd간의 가수 방송 순서를 준수하면서 음악 방송 스케쥴을 짤 수 있는지 체크해야한다.만약 그런 스케쥴이 존재할 수 없다면, 즉 존재하지 않는다면 0을 출력하고존재할 수 있다면 그 중 하나의 방송 스케쥴을 출력하라. 방법론 : 위상정렬 (topological sort graph algorithm)위상정렬 알고리즘 보기(* 추가 예정) 소스보기https://github.com/ingyeoking13/algorithm/blob/master/bj/p1..

알고리즘 문제/graph 2018. 2. 1. 12:49
911D : Inversion Counting

Codeforces 911D Inversion Counting숫자로 이루어진 집합에서 그 집합에서의 특정 두 원소 ai, aj의 위치가 i > j 일떄 ai

알고리즘 문제/graph 2017. 12. 30. 13:49
이전 1 다음
이전 다음
공지사항
  • 소스코드 중 링크가 존재하지 않다고 뜨는 것은⋯
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
  • paul wilton
  • 시뮬레이션
  • 이산 수학
  • 항해99
  • 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
  • 백준
  • 로젠
  • 자바스크립트
  • 대규모 시스템 설계 기초
  • 아레나 시뮬레이션
  • grafana cloud
  • 가상 면접 사례로 배우는 대규모 시스템 설계 기초
  • Simulation
  • 이산수학
  • 아레나시뮬레이션
  • arena simulation
  • 아레나
  • 최단경로 알고리즘
  • flutter
  • Propositional and Predicate Logic
  • rosen
  • 명제논리
  • 그라파나
  • 자바스크립트 예제
  • javascript
  • Grafana
  • beginning javascript
  • Arena
  • Discrete Mathematics
  • 데이터 중심 애플리케이션 설계
more
«   2025/06   »
일 월 화 수 목 금 토
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
글 보관함

Blog is powered by Tistory / Designed by Tistory

티스토리툴바