분류 전체보기
[LeetCode/릿코드] 948. Bag of Tokens - Python
[Medium] https://leetcode.com/problems/bag-of-tokens/ 풀이 tokens 배열을 오름차순 정렬해준 후, Two Pointer 기법을 이용해 풀어주면 쉽게 풀이할 수 있다. curl, curr 이라는 두 개의 커서를 각각 0, len(tokens) 로 초기화한 뒤, 차례로 진행해주면 된다. 현재 power가 왼쪽 커서(curl)의 토큰값보다 크다면 power를 낮추고 score를 올린 뒤(Face-up), 커서를 오른쪽으로 한 칸 이동. 현재 power가 왼쪽 커서(curl)의 토큰값보다 작다면, score가 1 이상이며, 왼쪽 커서와 오른쪽 커서가 같은 곳을 가리키지 않을 때, score를 낮추고 power를 올린다. (Face-down) 왼쪽 커서와 오른쪽 커서..
[백준] 9328. 열쇠 - Python
[Gold I] https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 풀이 시간초과와 메모리 초과를 몇 번 받다가, 이리저리 최적화하여 Accepted 받은 문제. 처음엔 [백준] 1194. 달이 차오른다, 가자. 와 비슷해 보여, 비슷하게 Bitmasking을 이용해 풀이할까 생각했지만, 가능한 열쇠의 개수가 26개이므로, 2^26의 경우의 수를 모두 저장할 수는 없어, 다른 방법을 생각했다. 우선 그래프(지도)의 형태를 입력받을 때, 겉을 빈 공간('..
[백준] 17387. 선분 교차 2 - Python
[Gold II] https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 풀이 작년 2학기 알고리즘 수업때 배웠던 CCW 알고리즘을 이용한 선분 교차 판별 문제. 그 때 강의 교안을 다시 보면서 기억을 되살리며 풀었다. CCW의 곱이 둘 다 0일 때, 선분이 포개어져 있는 경우 교차하는 것으로 판단한다. 이 케이스만 주의하면 나머지는 알고리즘을 그대로 적용하여 쉬이 풀이할 수 있다. AC. x1, y1, x2, y2 = map(int, input().split()) x3, y3, x4, y4 = map(int,..
2024 카카오 채용 연계형 겨울 인턴십 코딩테스트 후기
서론 Apple Developer Academy @ POSTECH에서의 생활, 포항에서의 생활이 막바지에 이르고 있다. 나는 올해가 지나고 내년이 되면 다시 복학을 할 예정이고, 졸업까진 4학기 정도가 남아 있으며, 군 문제가 아직 해결되지 않은 상태이기 때문에, 당장 취업을 할 생각은 크지 않았지만, - (그것과는 별개로 이런 상황의 대학생을 누가 채용하겠는가.) 평소에 알고리즘 문제들을 꾸준히 조금씩은 풀어 오기도 했고, 백준 티어도 곧 플래티넘을 찍을 것 같고, 알고리즘(코테) 스터디도 계속 열고, 운영하고 있었는데.. 정작 코딩테스트는 한 번도 본 적이 없었던 것이다. 뭐 그런 것도 있고, 카카오의 코딩 테스트가 다른 회사들에 비해 어려운 편이기도 하다고 들었으며, 슬슬 주변에서 동기들과 지인들은..
[Xcode 15] Xcode 15에서 추가한 시뮬레이터가 보이지 않는 현상
Environments - M1 Mac pro 14 - MacOS ver: 14.1.1 (Sonoma) - Xcode Version 15.0.1 문제 상황 MacOS 및 Xcode 업데이트 이후, 기존에 추가해 두었던 시뮬레이터들이 싹 날아가서 다시 새로 추가하였다. iPhone 14 시뮬레이터를 추가했는데도 Xcode에서 빌드할 때 보이지 않는 문제. 해결 시뮬레이터 목록 하단의, Manage Run Destinations에 들어간다. 추가한 시뮬레이터가 좌측에서 보일 텐데, 그 시뮬레이터 창에서 Show run destination을 Automatic에서 Always로 변경해주면 해결.
[백준] 1719. 택배 - Python
[Gold III] https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 풀이 모든 노드에서 시작하여, 다른 모든 노드로까지의 최단 경로를 구해야 하는 문제이므로, 플로이드-와샬(Floyd-Warshall) 로 풀이할까- 생각했다. 그러나 음의 가중치를 가지는 간선이 존재하지 않았고, 플로이드-와샬의 Time Complexity는 O(V^3), 다익스트라로 풀이한다면 O(E*VlogV) 정도이기 때문에, 다익스트라로 풀이하기로 하였다. 모든 노..
[백준] 1194. 달이 차오른다, 가자. - Python
[Gold I] https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 기본적으로 상하좌우 4방향으로 뻗어 나가는 흔한 BFS 형식으로 풀이하면 된다. 그런데 이제 비트마스킹을 곁들인. 열쇠와 문이 없다면, 각 row와 column, 그러니까 아래 코드에서는 visited[r][c] 2차원 배열만 채우며 진행하면 될 것이다. 그러나 열쇠가 있으므로.. 예를 들어, a열쇠를 가지고 (0,0)에 도달한 경우와, a열쇠가..
[백준] 1948. 임계경로 - Python
[Platinum V] https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 풀이 1 (오답) 문제를 보자마자, 그냥 크게 생각하지 않고 DFS(혹은 BFS..?) 느낌? 그냥 그래프 탐색으로 풀어본 결과. MLE가 나오긴 했지만, 다시 보니 지난 거리 개수를 셀 때 중복을 허용했기 때문에 틀린 코드다. MLE. (메모리 초과) / WA. from collections import deque n = int(input()) ..