1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/1174(1) 조건 분석 📊N번째 감소하는 수를 구해라2. 코드가 나오기까지 🛠️KEY WORD: DFS(1) 감소하는 수 구하기감소하는 수를 만들려면, 위와 같이 9부터 0까지 내림차순으로 있는 배열을 차례대로 DFS를 타며, 각 깊이의 수를 고를지 말지 선택하면 된다.이후 index를 벗어나는 지점에서 해당 수들을 list에 저장한다.(2) 답을 위한 정렬하지만 위의 DFS로 구한 감소하는 수들의 list는 오름차순 정렬 이 되지 않은 상태임으로, 정렬을 한 번 해줘야 한다. (1) 시간복잡도 분석 ⏳3. 코드 🌐(1) SUDO CODE 💬+ 1. 역순 1 자리 숫자 배열 만들기, N 받기+ 2. ..

Relevace Framing 🧩관련된 개념 : [[위상정렬]], [[DFS]]1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/1948(1) 조건 분석 📊A. 문제의 조건도시 간엔 일방 통행이고, 사이클이 없다.모든 도시는 시작 도시에서 갈 수 있으며, 모든 도시는 도착도시로 도착할 수 있다.출발도시에서 도착 도시로 갈 수 있는 모든 경로에 사람을 보낼 것이다. (즉 둘 사이의 모든 경로를 다 쓴다.)B. 답 요구사항모든 사람이 도착 도시에 올 수 있는 시간. 제일 늦게 도착하는 사람들이 건넜던 도로의 개수 C. 알고리즘 선정알고리즘은 위상정렬로 사료된다. 이유는 다음과 같다.전제 조건이 위상 정렬의 사용 가능 조건을 충족한다. (No cycle, 출발 ..

Relevace Framing 🧩관련된 개념 : [[ 시뮬레이션]]1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/20207(1) 조건 분석 📊열이 365개의 날짜, 행이 날짜 기록인 달력에 스케줄 표시하는데, 다음 규칙을 따른다.시작날짜가 앞선 것 부터 차례대로 달력에 채워넣는다.시작날짜가 같다면 스케줄 기간이 긴 것 먼저 채워넣는다.날짜가 겹치지 않으면서 연속된 스케줄 (ex 24, 5 7) 은 한 줄에 이어서 표기한다.날짜가 겹치면 한 칸 내려서 표기한다.코딩지 붙이기는 다음 규칙을 따른다.최소한의 코팅지로 최대한 많은 스케줄을 감싸야 한다.그럼 다음과 같이 된다.출처: 해당 문제 그림2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, 높이 배..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/1516(1) 조건 분석 📊각 건물마다 그것을 지으려면 선행해서 완성해야하는 건물이 있을 수 있다.(마치 스타크래프트나 임진록 같은 게임을 하면 배럭 전에 벙커를 지을 수 없는 것과 마찬가지)각 건물마다 그것을 지을 수 있는 최소 시간을 구하라.2. 코드가 나오기까지 🛠️KEY WORD: 위상정렬, 우선순위 큐(0) 집중 포인트 잡고 가기이번 문제에서는 집중해야할 포인트와 그러지 말아야할 포인트가 나뉜다.먼저 집중해야할 포인트는 "각 건물마다 그것을 짓기 위해서는 선행되어 지어져야 하는 건물이 존재할 수 있다" 라는 것이다. 이것은 해당 문제가 위상 정렬 을 써야 함을 소리치고 있다.괜히 집중했다간 문제 풀이..

1. 문제에 대하여 📦https://www.acmicpc.net/problem/2252(1) 조건 분석 📊키 순서별로 학생들을 정렬하려 한다.키 순서에는 순환이 존재할 수 없다. (사이클 없는 그래프)키에는 대소가 존재한다. (방향 그래프)키의 대소 관계가 일부만 존재하기 때문에, 답이 여러가지인 경우 아무거나 출력해라2. 코드가 나오기까지 🛠️KEY WORD: 위상 정렬이 문제는 전형적인 위상정렬 문제이다.만약 위상정렬에 대한 이해가 부족하신 분들은 [알고리즘] 위상정렬, 그림으로 쉽게 설명^^을 보고 오시길 바란다.처음에는 그저 진입 차수 배열 + for, while 반복문으로 문제를 풀었더니 시간이 963ms 정도로 높게 나왔다. 이를 최적화 하려면 인접리스트 + BFS 방식으로 가장 선행되는..

1. 정의위상 정렬이란, 사이클이 없는 방향 그래프에서 정점을 정렬하는 알고리즘이다.(1) 사전 지식A. 진입 차수란?방향 그래프에서 본인을 향해 있는 간선의 개수가 바로 진입 차수이다.반대로 본인에서 나가는 간선의 개수는 진출 차수라고 부른다.위의 사진에서 진입차수는 3이고, 진출 차수는 2라고 할 수 있다.B. 정점끼리의 관계에서 선행된다와 후행된다의 차이기준 정점에서 볼 때, 자신에게 진입하는 간선을 가진 정점을 선행하는 정점, 자신이 진출하는 정점을 후행하는 정점으로 볼 수 있다.(2) 정렬의 기준은?정렬의 기준은 선행되는 정점의 개수이다. 즉 선행되는 정점이 많을수록 우선순위가 낮다. 이를 위해서는 위에서 설명했듯이 (1) 사이클이 없고, (2) 방향 그래프임이 전제되어야 한다.다음의 그림을 통..

1. 문제에 대하여 📦https://www.acmicpc.net/problem/15683(1) 조건 분석 📊상남자의 문제 완전탐색이다.그냥 문제 조건 그대로 시간복잡도 신경 안쓰고 풀면 된다.'오류가 없다면' 순열과 조합을 써도 문제가 풀려야 한다.2. 코드가 나오기까지 🛠️KEY WORD: 순열, 완전 탐색1번2번3번4번5번출처: 해당 문제의 이미지 사진A. 순열은 어디에 쓰는가?순열은 CCTV가 동작할 수 있는 모든 경우의 수를 세기 위하여 필요로 되어진다. 위에 나오는 각 CCTV는 90도씩 회전이 가능하다. 1,3,4번은 동서남북 모두 경우의 수가 다르고, 2번은 상하, 좌우만 다르며 5번에서는 나올 수 있는 경우의 수가 딱 하나이다. cctv는 1개 이상 8개 이하일 수 있기 때문에, ..

1. 문제에 대하여 📦https://www.acmicpc.net/problem/4803(1) 조건 분석 📊트리의 수 세기사이클이 있는 그래프는 트리가 아니므로, 갯수 센 것에서 제외하기2. 코드가 나오기까지 🛠️KEY WORD: Union & Find나머지 정점 N개 간선 N-1 개 등, 다른 트리의 특징들은 해당 문제에서 2개의 정점 사이에는 하나의 간선밖에 업다고 못 박아 두었기 때문에 신경 쓸 필요가 없다. 따라서 사이클이 생기는지만 신경써서 확인해주면 된다.필자는 다음과 같은 방법을 거쳐 사이클 여부를 확인했다. (내용을 진행하기 앞서, 독자들이 Union&Find에 대해 알고 있다는 가정 하에 설명을 이어가겠다. 혹시 모르시는 분은 [알고리즘] 유니온 파인드 쉽게 이해하기 ^^를 한 번 읽..

1. 문제에 대하여 📦https://www.acmicpc.net/problem/2933(1) 조건 분석 📊배열의 오른쪽과 왼쪽에서 한 번씩 번갈아 막대기를 던져서 미네랄 파괴고드름처럼 밑둥을 치면 아래것들은 떨어진다. 떨어질 때 형태가 유지되어야 함. 즉 ㄱ 자로 떨어지면 ㄱ 자 형태 그대로 맨 끝의 문자가 x 또는 바닥을 만날 때까지 떨어진다.광물의 끝점이 하나인 경우만 주어진다. (즉 맨 아래가 하나인 경우만 주어진다. ㄱ자, ㅋ자는 가능하지만, ㄴ자 ㄷ자는 불가)2. 코드가 나오기까지 🛠️KEY WORD: BFS, 완전 탐색해당 문제는 문제에 나온 설명 그대로 구현하면 되는 시뮬레이션 문제이다.필요한 함수는 다음과 같다.A. 막대기 맞은 광물 부수기왼쪽, 오른쪽 번갈아 던지기 구현 필요B. 떨..

1. 문제에 대하여 📦https://www.acmicpc.net/problem/1865(1) 조건 분석 📊+한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, +출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지필자는 해당 부분을 '정점 중 단 하나라도 자신에게 돌아오는 음의 사이클이 있는지' 라 받아들이고 풀었다가 틀렸다. 해당 조건은 '음의 사이클이 있는지'만 체크하는 조건이다. 이유는 다음과 같다.출발지점이 정해져 있기 않기 때문에, 음의 사이클이 존재한다면, 그 음의 사이클 내부의 정점도 출발 정점이 될 수 있다. 따라서 음의 사이클만 있다면, 언제든 출발을 하였을 때보다 시간이 되돌아가 있는 경우는 반드시 있다.음의 사이클 확인 이라는 지..

1. 문제 설명 📌(1) 링크🔗문제 링크(2) 해설🕵시작도시에서부터 도착도시로 가며 최대한 많은 이윤을 내는 것이 목표(+도시에서 장사해서 얻는 이득, - 이동 비용) 2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: 벨만포드, BFS주목해야할 문제 조건은 다음과 같다.방문한 도시는 또 방문할 수 있다.시작 지점에서 도착 지점으로 도달할 수 없는 경우 gg 출력도착지점에 도착했을 시 돈을 무한히 가질 수 있다면, Gee 출력A. 조건 1에 대하여방문한 도시를 또 방문할 수 있다는 조건에서 벨만 포드를 고려했다. 벨만포드는 총 N-1번의 완화 과정을 거치며, 시작 정점에서 모든 정점까지의 최단 거리를 구한다.(이는 시작 지점에서 갈 수 있는 제일 먼 정점이라도, 최대..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/10830(2) 해설🕵고등학교 이후로 행렬의 곱을 오랜만에 만나는 거여서 다시 공부하고 왔다.행렬 A,B에 대하여 A * B = C라 할때, C의 각 행렬의 값은 그 부분을 교차하는 A의 행 * B의 열 이다.직관적으로 행렬이니까, 곱하는 왼쪽 요소의 행, 오른쪽 요소의 열이라고 생각하면 편하다.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: 행렬의 곱 식 알기, 거듭제곱을 위한 분할정복, 모듈러 분배의 원칙A. 행렬의 곱 식 알기행렬의 원리는 알겠는데, 이를 반복문을 이용한 식으로 구현하려니 골치가 아팠다. 다행히 행렬의 크기가 최대 5여서, 시간복잡도적 압박감은 없었다. 직..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/3197(2) 해설🕵문제가 직관적이라서 패스2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: BFS + 오늘 BFS 돌릴 Queue과 내일 돌릴 Queue 구분!언뜻 보면, 그냥 벽부수고 이동하기 같은 문제처럼 매번 BFS를 단순히 돌면 된다고 생각하기 쉽지만, 다음과 같은 조건 때문에 더 깊게 생각해봐야 한다.행과 열의 최대가 1500이므로, 이렇게 풀면 시간초과가 난다.하루가 구분되어, 정해진 양만큼만 BFS를 돈다.필자의 경우 1번을 간과하여 시간초과를 냈으며, 두 번째를 간과하여 이후 틀렸습니다. 오류도 내었다. 자세한 트러블 슈팅은 현 포스팅 맨 하단에 기록해 두겠다.따..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/20040(2) 해설🕵3개 이상 동일 선상에 안 놓아져있는 점들의 집합에서 자신의 턴마다 점과 점을 잇는 선분을 그리는 턴제 게임목표: 사이클이 형성된 게임 턴 출력조건:선분의 끝과 시작 점 조합은 오로지 한 번만 나옴(= 이전에 그린 선분은 다시 그릴 수 없다.)다른 선분 위로 교차 하는 것은 가능2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: Union & Find두 개의 점을 선분으로 이으면, 이제 둘은 동일한 트리 그래프를 형성하게 된다. 이를 합집합으로 표현한다.두 개의 점을 선분으로 이으려 했더니, 이미 둘은 같은 트리에 속한다. 이는 이미 둘이 간접적으로 이어져 있..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/10775(2) 해설🕵게이트와 비행기가 존재비행기마다 착륙할 수 있는 게이트의 한계치가 있음. (만약 문제에서 비행기의 정차 $g_i$를 5라고 하면, 해당 비행기는 GATE 1번부터 5번까지 중에서 한 곳에만 착륙해야함.)만약 임의의 비행기가 착륙할 수 있는 GATE가 없다면 비행기를 폐쇄해야함.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: Greedy Algorithm, Union Find첫 번째 시도 Greedy Algorithm각 비행기마다 그 비행기가 착률할 수 있는 GATE의 끝 순번부터 시도해서 가능한 게이트에 댄다.이렇게 하는 이유는 다음과 같다.만약 비행기 착..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/4195(2) 해설🕵각 TC마다, 친구 맺는 숫자와 실제 친구 맺는 사람들이 (a, b) 형태로 이름이 나열된다.각 ROW 마다 친구를 맺었을 때, 두 사람의 친구 네트워크 (중복 제거하거 각자 파도타기 해서 들어갈 수 있는 친구 수)를 출력하라.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: UNION FIND, Hash Map 변환이름 자체가 문자열로 주어지는데, 이를 매번 다 equals()로 확인하면, 시간 초과가 날 것이 뻔했다. 왜냐하면 TC가 몇 개인지도 모르는데, 한 번의 TC 당 100,000 개의 (a,b) 문자열 쌍이 주어진다. 그럼 최대 200,000개의 ..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/1043(2) 해설🕵지민이가 거짓말쟁이가 되는 경우의 수 2가지진실을 모르는 사람들만 있는 파티에서 영호가 지민이의 과장된 무용담을 듣는다.이후 영호가 진실을 아는 사람 파티에 또 간다. (선 과장 - 후 진실)진실을 아는 사람이 한 명이라도 있는 파티에서 영호가 지민의 진실된 이야기를 듣는다.이후 영호만 진실된 이야기를 알고, 나머지는 모르는 상황인 추후 파티에서 지민이의 과장된 무용담을 듣는다.(선 진실 - 후 과장)따라서 진실을 먼저 알게되든 나중에 알게되든 상관없이 진실을 알게만 된다면 지민이는 거짓말쟁이가 된다. 실시간성 계산이 없으므로, 모든 유니온 파인드 진행 후 파티의 유효성 검증을 해도 괜찮다...

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/1976(2) 해설🕵각 도시간의 양방향 연결 양상을 보여줌여행 시 도시 방문 계획표가 주어질 때, 이 계획표가 도시 연결 양상을 볼 때 가능한지, 죽어도 못 가는 곳이 있는지 확인 후 답 출력 (가능: "YES", 불가능: "NO")2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: UNION-FIND문제 맨 마지막에 주어지는 도시들이 모두 하나의 집합에 속해있으면, 일정의 모든 도시를 방문할 수 있는 것임으로, YES를 출력하면 된다. 해당 문제는 인접리스트 그리기 -> 임의의 정점에서부터 DFS -> 일정에 있는 도시 만날 경우, 계획표에서 x 표로 표시 -> 모든 도시가 표시..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/1717(2) 해설🕵유니온 파인드 할 수 있는지를 묻는 문제였다.혹시 유니온 파인드 알고리즘을 모른다면, DO IT 알고리즘 강의 - 유니온 파인드 편을 보고 오자.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: UNION-FIND도출한 아이디어가 없으므로 해당 파트 생략(2) SUDO CODE 📜+ 1. 입력 받기 (메타데이터 - 노드 개수, 연산 개수 + 연산 전부 일괄 저장)+ 2. union, find 함수 만들기 (find 함수 만들 때 경로 압축 스킬 추가)+ 3. 실행(3) 시간복잡도 분석 🕓find 연산: 경로 압축이 암시적 트리 높이는 줄여주지만, 그럼에도 ..

1. 정의Union-Find 알고리즘은 이름 그대로 밑의 두 가지를 수행하는 알고리즘이다.union: 2개의 서로소 집합을 합쳐 하나의 집합으로 만든다.find: 하나의 원소가 속한 집합이 무엇인지 찾는다.하지만 이를 위해 집합의 명칭과 원소의 명칭을 따로 선언해서 별개로 관리하면, 알고리즘 자체보다 변수가 무엇을 뜻하는지 찾는데 시간을 더 쏟게 될 것이 뻔하다. 따라서 알고리즘의 가독성과, 변수 관리의 효율을 위하여 트리 자료구조를 활용해서 알고리즘을 구현한다.위 그림에서 하나의 트리에 묶이는 노드들이 곧 하나의 집합에 묶이는 원소들이다. 따라서 집합으로 표현하면 {2,4,5}, {3,6,7}로 나눌 수 있다. 이제 다시 union과 find를 이에 맞춰서 정의해보자.union: 2개의 서로소 집합의 ..

1. 문제 설명 📌(1) 링크🔗문제 링크(2) 해설🕵값을 하나씩 추가할 때마다, 지금까지 누적된 수 중 중간값을 알아내서 출력해야 한다.해당 문제는 최소힙, 최대힙에 대한 이해가 있어야 한다. 아직 해당 부분에 대해 모르시는 분들은 밑의 이론과 연습 문제 학습 과정을 거친 후 다시 도전하시길...이론: 최소 힙에 대한 소개, 최대 힙에 대한 소개연습 문제: 최소 힙 문제, 최대 힙 문제, 절대값 힙 문제2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: max-heap, min-heap문제의 핵심 컨셉은 전체 중 중간값 이하만 저장된 최대힙, 중간값 초과만 저장된 최소 힙 이다. 이렇게 둘을 구현하다 보면 max-heap자료구조의 루트 노드는 무조건 중간값이다. 이를..