알고리즘
-
[백준] 11725 :: 트리의 부모 찾기알고리즘/BOJ(C++) 2019. 8. 2. 16:02
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 입력되는 간선정보를 바탕으로 각 노드의 부모를 저장하면 된다. 트리는 항상 n개의 노드가 있을 때 간선이 n-1개이므로 우리는 n-1개의 간선만 입력받아도 트리를 만들 수 있다. 처음에 일차원배열로 풀었다가 틀렸다. 왜냐하면 간선 정보가 depth가 깊어지는 순서대로 입력된다는 보장이 없기 때문이다. 따라서 그래프 입력받듯이 모든 간선 정보를 vector에 저장한 후 한번에 트리를 만들어야 한다. 소스코드 ...더보기 1 2 3 4 5 6 7 8 9 10 11..
-
[백준] 2250 :: 트리의 높이와 넓이알고리즘/BOJ(C++) 2019. 8. 2. 15:59
https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다. www.acmicpc.net 문제 그대로 트리의 넓이를 구하는 문제이다. 가장 중요한 포인트는 트리의 각 노드가 몇번째 열에 위치하는지를 알아내는 것인데, 조금만 고민해보면 이것은 preorder 트래버설로 알아낼 수 있다. 프리오더 트래버설은 왼쪽 -> 루트 -> 오른쪽 이렇게 탐색하는 방식이고 이 순서대로 탐색..
-
[백준] 3055 :: 탈출알고리즘/BOJ(C++) 2019. 8. 1. 19:28
https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 해결방법 1. 비버의굴과 바위는 못가는 곳으로 표현한다 2. 물이 위치하는 곳에서 부터 bfs를 탐색해, 어떤 지점에 몇초만에 그 물이 도달..
-
[2019 카카오 신입 공채 1차 코딩테스트] 2. 실패율알고리즘/etc 2019. 7. 13. 22:14
문제 정보와 자세하고 정확한 풀이는 요기로 ~~~ -> http://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/ 2019 카카오 신입 공채 1차 코딩 테스트 문제 해설 작년에 이어 올해도 블라인드 전형으로 카카오 개발 신입 공채가 시작되었습니다! 그 첫 번째 관문으로 1차 온라인 코딩 테스트가 지난 9월 15일(토) 오후 2시부터 7시까지 5시간 동안 치러졌는데요. 지원자분들 만큼이나 준비위원들도 테스트가 문제없이, 공정하게 치러질 수 있도록 많은 준비를 했고 두근 거리는 마음으로 끝까지 온라인 테스트를 모니터링했답니다. 문제는 작년과 비슷하게 구현 문제 위주로 쉬운 난이도에서 어려운 난이도 순으로 풀 수 있도록 차례대 tech...
-
[2019 카카오 신입 공채 1차 코딩테스트] 1. 오픈채팅방알고리즘/etc 2019. 7. 13. 21:39
자세한 문제 정보 및 풀이는 공식 사이트인 여기서 -> http://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/ 2019 카카오 신입 공채 1차 코딩 테스트 문제 해설 작년에 이어 올해도 블라인드 전형으로 카카오 개발 신입 공채가 시작되었습니다! 그 첫 번째 관문으로 1차 온라인 코딩 테스트가 지난 9월 15일(토) 오후 2시부터 7시까지 5시간 동안 치러졌는데요. 지원자분들 만큼이나 준비위원들도 테스트가 문제없이, 공정하게 치러질 수 있도록 많은 준비를 했고 두근 거리는 마음으로 끝까지 온라인 테스트를 모니터링했답니다. 문제는 작년과 비슷하게 구현 문제 위주로 쉬운 난이도에서 어려운 난이도 순으로 풀 수 있도록 차례대 tech...
-
[알고리즘 문제해결전략 #1] 자주 하는 실수알고리즘/알고리즘 문제해결전략 2019. 7. 10. 21:53
책 공부하면서 중요하다고 생각되는 부분 정리하고, 내가 자주 쓰는 코드도 정리할 생각이다! 이번 주제는 "자주하는 실수 모음" 산술 오버플로우 항상 문제 읽을 때 입력으로 들어오는 값의 범위 확인하면서 변수 타입 정하자! 문제 읽으면서 선행해야 할 필수 작업으로 머리에 상기시켜서 실수줄이기 1) 너무 큰 결과 값 2) 너무 큰 중간 값 최소공배수 같은 것들을 계산할 때 중간 계산과정에서 overflow가 일어날 수도 있다! 계산 과정도 확인한기 3) 너무 큰 무한대 값 INF값 잡을 때 무턱대고 큰 값 잡지말기 (무한대끼리 계산하다가 오버플로우가 날 수도 있다) 저자가 추천하는 값은 987654321이다! (어쩐지 사람들이 많이쓰더라..) 배열 범위 밖 원소에 접근 - 배열에 입력을 받을 때 인덱스를 1..
-
[BOJ] 1202 :: 보석 도둑알고리즘/BOJ(C++) 2018. 7. 24. 12:09
https://www.acmicpc.net/problem/1202 으엉 ㅠㅠ어려웠고 엄청 많이 틀렸던 문제라서 문제풀면서 느낀거 정리하려고 씀 1. 그리디한 문제. 가장 큰 가격 부터 가방에 담으려고 시도 -> 가방에 담을 때 자신보다 크거나 같은 가방 중 가장 작은 가방을 찾아야함2. 정말 naive하게 풀면 nk가 나오는데 물론! 시간초과3. 지금 담으려는 무게보다 크거나 같은 것 중 가장 작은 가방을 찾는 과정에서 시간을 줄이기 위해 lower_bound를 생각함(logN)4. lower_bound로 담을 수 있는 가방을 찾고 그 가방을 사용했다는 표시?를 하기위해 erase연산을 사용헀으나, vector에서 erase연산은 n의 시간복잡도를 가지므로 약 n^2logn이 나와 시간초과5. 우선, p..
-
[BOJ] 14226 :: 이모티콘알고리즘/BOJ(C++) 2018. 7. 3. 15:22
https://www.acmicpc.net/problem/14226 pair를 한 정접으로 하는 그래프를 생각하고, bfs탐색을 진행합니다. pair의 first원소는 현재 화면에 있는 이모티콘의 개수이고 second원소는 클립보드에 있는 이모티콘의 개수입니다. index관련 예외처리만 잘해주면 됩니다! 요즘 런탐에러 너무많이나네요ㅠ 실수안해야지.. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include using namespace std; int s; bool check[1003][2003];int dist[1003][2003]; int main(){ cin..