본문 바로가기

전체 글361

[BOJ]1590번: 캠프가는 영식 https://www.acmicpc.net/problem/1590 버스의 갯수 와 각 버스의 대수가 각 각 10만이므로 N^2 탐색을 하면 시간초과가 납니다. 그러므로 한 종류의 버스에 대해 영식이가 최소 몇 분을 더 기다려야하는지 계산할 때 logN만에 탐색해야 합니다. 그래야 NlogN으로 시간제한을 통과할 수 있습니다. 제가 logN으로 시간복잡도를 줄인 방법은 이분탐색입니다. 이분 탐색을 사용하여 버스 도착 시간의 상한과 하한을 계산해서 영식이가 탈 수 있는 최초 버스 시간을 구했습니다. 코드: https://github.com/cotchan/algorithm/blob/main/java/BOJ/BOJ1590.java 2021. 6. 23.
[2020 카카오 기출] 블록 이동하기(JAVA) https://programmers.co.kr/learn/courses/30/lessons/60063 시뮬레이션 문제입니다. 크게 두 가지가 중요합니다. 1. 로봇의 상태를 나타내는 법 로봇의 상태는 현재좌표(Y,X) + 바라보고 있는 방향(Direction)으로 나타낼 수 있습니다. 두 칸을 각 각 HEAD, TAIL이라고 하고 HEAD 기준으로 바라보는 방향으로 TAIL 위치를 구할 수 있습니다. //int값 X의 의미: X초에 로봇이 (y,x) 좌표에서 dir 방향으로 있었음을 의미 int robotState[DIR][N][N]; 2. 매 초 이동하는방법 매 초마다 로봇이 이동할 수 있는 방법은 8가지입니다. case1. 회전하지 않고 주어진 방향에서 좌우상하로 4방향 이동하는 경우 - 4가지 ca.. 2021. 6. 20.
[2021 카카오 기출] 카드 짝 맞추기(JAVA) https://programmers.co.kr/learn/courses/30/lessons/72415 풀이는 바킹독님의 해설을 참고했습니다. (https://www.youtube.com/watch?v=FX9n1PFv2K4&t=2851s) 풀이는 크게 3가지 파트로 나눠집니다. 1. 6개 종류의 카드 중 어떤 카드부터 짝을 맞출 것인지 - 시간복잡도: O(6!) 2. 한 종류의 카드는 2장이 있는데, 두 장 중 어떤 카드부터 탐색할 것인지 - 시간복잡도: O(2^6) 3. 실제 탐색하는 BFS - 시간복잡도: (6 * O(4^2)) 위 3개의 조합으로 O(1*2*3)을 한 게 브루트포스로 해결한 시간복잡도입니다. N제한이 크지않으므로 C++, JAVA의 경우는 브루트포스로 해결 가능합니다. 코드: http.. 2021. 6. 20.
[BOJ]2493번: 탑 https://www.acmicpc.net/problem/2493 스택으로 해결할 수 있는 문제입니다. 1. 입력으로 주어지는 탑의 높이를 큐 자료구조에 저장합니다. 2. 큐에서 나오는 각 element에 대해 필요한 연산을 하고 저장을 할 스택(rest)을 만듭니다. - 스택의 의미는 현재 큐에 나오는 element가 쏘는 레이저를 송신하는 탑을 의미합니다. 3. 큐에서 하나씩 element를 뽑으면서 내 레이저를 송신할 탑을 찾습니다. -1 현재 스택의 TOP에 있는 탑의 높이가 현재 element 탑의 높이보다 높다면 => ---- 현재 element의 레이저를 송신하는 탑으로 스택의 TOP을 저장하고 현재 element를 스택에 push합니다. -2 현재 스택의 TOP에 있는 탑의 높이가 현재 e.. 2021. 6. 18.