알고리즘36

• 

  [백준] 세그먼트 트리 모음(10868, 2357, 2042, 11505) 10868번: 최솟값 (acmicpc.net) 2357번: 최솟값과 최댓값 (acmicpc.net) 2042번: 구간 합 구하기 (acmicpc.net) 11505번: 구간 곱 구하기 (acmicpc.net) 4문제 다 세그멘트 트리 알고리즘 문제이다 순서대로 풀면 좋게 순서를 나열했다 나는 멋모르고 막 풀다보니 역순으로 풀었다 ㅎㅎ;; 11505 구간 곱 구하기를 못 풀겠어서 풀이를 보며 공부하다가 2042번을 알게 되고 이 문제도 풀이를 보며 공부하면서 풀고 10868 번을 보니깐 어떻게 접근해야될지 확 느낌이 오고 풀리는게 연습이 되는 느낌이였다 만약 처음 세그먼트 트리를 공부한다면 위에 올린 순서대로 풀어보면 좋지 않나 싶다. 4문제 다 세부적으로 풀이는 조금씩 다르지만 세그먼트 트리를 활용하여 .. TIL/SW&백준 문제 리뷰 2022. 8. 12.

• 

  [백준]1005 ACM Craft 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을.. TIL/SW&백준 문제 리뷰 2022. 2. 24.

• 

  위상정렬 (Topological Sort) 위상정렬 (Topological Sort) 선후 관계가 정의된 그래프 구조에서 정렬하기 위해 사용 그래프가 순환 구조 가지면 사용 불가 동작 진입 차수 테이블 생성 및 진입 차수 계산 진입 차수가 0인 노드 큐에 넣기 (순서 상관 X) 큐에서 노드 꺼내 연결된 노드들 진입 차수 감소 ( -1 해준다), 진입 차수가 0이 되면 큐에 넣기 큐가 비어버릴 때 까지 3번 반복하며 꺼낸 노드들 줄세우기 (이게 위상 정렬 결과값) 백준 문제 : 2252번: 줄 세우기 (acmicpc.net) 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A.. 미가공 필기(알고리즘) 2022. 2. 23.

• 

  유니온 파인드( Union Find ) 그래프 알고리즘 합집합 찾기, 상호 배타적 집합 여러 노드 존재시, 두 개의 노드 선택하여 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 2가지 연산 Find : x 가 어떤 집합에 포함되어 있는지 찾는 연산 Union : x 와 y가 포함되어 있는 집합을 합치는 연산 미가공 필기(알고리즘) 2022. 2. 18.

• [프로그래머스] 후보키 https://programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 내 풀이 문제를 사실 제대로 풀어내지 못했다. 하지만 오늘 내가 생각했던 접근 방식이 크게 틀리지는 않았기에 나중에 다시 풀어보고자 한다. 우선 조건이 최소성과 유일성 이 있고, 이를 만족하는 후보키의 개수를 구하는 것이 목적이였다 (지금 .. TIL/SW&백준 문제 리뷰 2021. 9. 2.

• 

  [백준] 16916 부분문자열 16916번: 부분 문자열 (acmicpc.net) 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 문제 문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다. 예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다. 문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자. 입력 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자.. TIL/SW&백준 문제 리뷰 2021. 8. 23.

• 

  [백준] 14938 서강그라운드 14938번: 서강그라운드 (acmicpc.net) 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 .. TIL/SW&백준 문제 리뷰 2021. 8. 23.

• 

  [백준] 14719 빗물 14719번: 빗물 (acmicpc.net) 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제 2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까? 입력 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다. 따라서 블록 내부의 빈.. TIL/SW&백준 문제 리뷰 2021. 8. 22.

• 

  [백준] 17503 맥주 축제 17503번: 맥주 축제 (acmicpc.net) 17503번: 맥주 축제 첫 번째 줄에 축제가 열리는 기간 N (1 ≤ N ≤ 200,000) 과, 채워야 하는 선호도의 합 M (1 ≤ M N) { //만약 사이즈가 초과하면 tempScore -= PQ.poll(); // 가장 작은 선호도 요소 꺼내서 빼줌 } // 조건에 맞는 경우에 도달하면 if (PQ.size() == N && tempScore >= M) { noAnswer = false; //정답이 있다고 변경 System.out.println(data[i][1]); // 레벨 출력(data를 도수 오름차순으로 정렬했기에 가능) break; } } if (noAnswer) { System.out.println(-1); } } } TIL/SW&백준 문제 리뷰 2021. 8. 20.

• 

  [백준] 20207 달력 20207번: 달력 (acmicpc.net) 20207번: 달력 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장 www.acmicpc.net 문제 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장마가 시작되었고, 습기로 인해 달력에 표시한 일정이 지워지려고 한다. 지워지는 것을 막고자 수현이는 일정이 있는 곳에만 코팅지를 달력에 붙이려고 한다. 하지만 너무 귀찮았던 나머지, 다음과 같은 규칙을 따르기로 한다. 연속된 두 일자에 각각 일정이.. TIL/SW&백준 문제 리뷰 2021. 8. 20.

• [백준] 2504 괄호의 값 2504번: 괄호의 값 (acmicpc.net) 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 문제 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 .. TIL/SW&백준 문제 리뷰 2021. 8. 19.

• 

  [백준] 11000 강의실 11000번: 강의실 배정 (acmicpc.net) 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개.. TIL/SW&백준 문제 리뷰 2021. 8. 18.