근현대 고슴도치 기술 근현대 고슴도치 기술

stack

• 백준 22942 데이터 체커 - [알고리즘] [kotlin]

  알고리즘/백준 2023. 8. 12. 02:31

  문제 내용 문제 분석 1. N개의 원 정보가 주어진다. (x좌표, 반지름) 2. 각 원은 x축 위에 있는 것이 보장된다. 3. 모든 원에 대해 서로 교점이 존재해서는 안된다. 아이디어 실패한 아이디어 더보기 논리 아이디어 1. 교점이 존재하는지에 대한 판단을 해야 한다. 2 y좌표는 모두 0 으로, 각 원의 x좌표와 반지름만으로 판단이 가능하다. 3. 임의의 두 원에 대해 교점이 존재하지 않으려면 다음 2가지 경우가 있다. a. 한 원이 다른 원에 포함되고, 내접하지 않는다. b. 두 원이 포함관계가 없고 외접을 포함한 교차점이 없다. 4. a의 경우 두 원의 "중심 사이의 거리" + "작은 원의 반지름"이 큰 원의 반지름보다 작아야 한다. 5. b의 경우 중심 사이의 거리가 각 반지름의 합보다 커야 한..

  Read More
• 백준 2493 탑 - [알고리즘] [kotlin]

  알고리즘/백준 2023. 8. 9. 18:59

  문제 내용 문제 분석 1. 높이가 서로 다른 탑 N개가 일직선상에 있다. 2. 각 탑은 꼭대기에서 레이저를 발사한다. 3. 이때 발사 방향은 왼쪽이다. 4. 더 레이저는 더 높은 탑을 만나면 해당 탑에 수신된다. 5. 각 탑에서 발사한 레이저가 어느 탑에 닿는지 출력하자. 6. 어느 탑에도 닿지 않으면 0을 출력한다. 아이디어 1. 문제를 재해석하면 각 탑의 왼쪽 중 본인보다 높은 가장 가까운 탑을 고르는 문제가 된다. 2. 왼쪽 영역에서만 찾아야 하므로 정렬해서는 안된다. 3. bruteFore하게 매번 검사할 시 O(n^2)의 시간 복잡도를 가지므로n = 500000인 상황에서 1.5초안에 해결하기 어렵다. 4. 각 검사마다의 worst case는 더 높은 탑이 없어 왼쪽의 모든 탑을 검사하는 경우이..

  Read More
• 백준 4949 균형잡힌 세상 - [알고리즘] [kotlin] [stack]

  알고리즘/백준 2023. 8. 3. 10:24

  문제 내용 문제 분석 1. 소괄호 대괄호가 적절히 열리고 닫히는지 검사해야 한다. 2. 괄호 안의 문자열 안의 문자열도 검사를 해야한다. 3. 마지막은 온점으로 끝난다. 4. 문자열이 없거나 소괄호 대괄호가 없는 경우도 균형잡힌 문자열이다. 5. 마지막으로 들어오는 "."은 종료조건이므로 "yes"를 출력하면 안된다. 아이디어 1. 열리는 괄호와 닫히는 괄호가 매칭되는지 검사한다. 2. 올바른 형태라면, 닫히는 괄호가 들어왔을 때 가장 최근에 들어온 괄호와 짝이 맞아야 한다. // 만약 짝이 없다면 올바른 형태가 아니다 ex) "abcd)abc", "abc)abc(abc" // 만약 짝이 다르다면 올바른 형태가 아니다 ex) "abc[abc)" 3. 가장 최근의 괄호와 비교하기 위해 stack 자료구조를..

  Read More
• 백준 10811 바구니 뒤집기 - [알고리즘] [코틀린]

  알고리즘/백준 2023. 7. 26. 00:34

  문제 내용 문제 분석 1. 1~N의 번호가 매겨진 n개의 바구니가 있다. 2. "x y" 형태의 명령이 m번 들어온다. 3. x~y바구니를 역순으로 배치한다. 아이디어 1. 크기 n+1인 배열을 만들어 1~n까지 바구니가 있다고 생각한다. (index: 위치, value: 바구니 번호) 2. "x y"가 들어오면 순서대로 stack에 넣은 후 빼서 순서를 역전시킨다. 풀이 2가지 방법이 더 생각나서 추가로 적용해 봤다. import java.util.LinkedList fun main() { val br = System.`in`.bufferedReader() // 한줄을 입력받아 공백을 기준으로 List로 반환 fun getInput() = br.readLine().split(' ').map { it.t..

  Read More
• 백준 2504 괄호의 값 - [알고리즘] [kotlin]

  알고리즘/백준 2023. 7. 25. 01:50

  문제 내용 https://www.acmicpc.net/problem/2504 문제 분석 1. 괄호는 [] ()로 2종류가 존재함 2. 괄호 안에 괄호가 있을 수 있다. 3. 안쪽 괄호는 바깥 괄호가 닫히기 전 닫혀야 한다. 즉, 닫히는 괄호가 들어올 때, 가장 최근 열린 괄호와 종류가 같아야 한다. 4. 괄호 안에 있는 값들에 곱연산을 한다. 5. 포함관계가 없는 괄호들은 합연산을 한다. 아이디어 1. stack을 이용해 가장 최근 열린 괄호와, 이번에 들어온 괄호의 종류를 비교할 수 있다. 2. 숫자가 붙어있을 경우 바로 합연산을 진행해도 무관하다. 풀이 1. push 및 내부 과정을 MyStack 클래스에 위임함 2. 매번 계산을 거치기 때문에 0~9를 넘을 수 있음 때문에, Int or String..

  Read More