클라우드 낚시꾼

코딩 테스트란 무엇인가 - 코딩 테스트는 누가 실시하는가? 아마 필자를 포함한 개발자 꿈나무들이 "어디에서 일하고 싶어요?"라는 질문을 들으면, 대부분 "네카라쿠배요!"라고 답할 것이다. 보통의 기업들은 스펙, 면접 등으로 유능한 인재를 선별한다. 하지만, IT 대기업은 조금은 생소한 방식으로 유능한 인재를 선별하는데 그것이 바로 알고리즘 코딩 테스트다. - 코딩 테스트를 왜 실시할까? 코딩 테스트는 여러 가지 환경, 변수를 다 배제하고 문제를 해결하는 능력 자체를 평가하기 위해 실시한다. 기업 입장에서도 실무 환경에서 직접 프로그램을 개발하는 능력을 평가하고 싶을 것이다. 하지만, 그 환경이 회사마다, 사람마다 천차 만별이기 때문에 정확한 개발 능력을 평가하기 쉽지 않다. 코딩 테스트 공부법 코딩 테스..

문제 해결 과정 이 문제는 단순 BFS 문제였고, 인접 정점을 내림차순으로 정렬하는 조건이 중요했다. 문제가 쉬움에도 불구하고 나는 계속 답은 맞는데 시간 초과 문제가 발생했다. 그 이유는 아래와 같다. 시간 초과가 발생했던 이유 원래 필자는 그래프에 정보를 추가하면서 인접 정점을 정렬하였다. 그래서 정렬 과정이 2번 일어났고 이것이 시간 초과가 발생했던 주된 이유였다. 시간 초과 문제를 해결하기 위해 기존의 정렬 코드를 없애고 그래프 정렬을 위한 for문을 작성하여 정렬과정을 수행했다. 그 결과 정렬 코드의 시간 복잡도가 O(2n)에서 O(n)으로 감소하였다. 전체 코드 import sys from collections import deque input = sys.stdin.readline m,n,r ..

제한 조건과 설계 미로 문제처럼 M*N 격자 그래프 문제이므로 BFS를 사용한다. 1은 검은색 격자이기에 전류가 잘 통하지 않고, 0은 흰색 격자로 전류가 잘 통한다. 0행에서 M-1행에 도달하는 경로가 있는 지를 물어보는 문제다. 자연어 알고리즘 정보를 입력 받고 그래프를 생성한다. 0행에서 값이 0인 좌표가 시작 지점이다. 이 지점들을 starts 리스트에 저장한다. starts 중 한 지점으로 BFS 탐색을 시도 했을 때 m-1 행에 도달하면 YES를 출력하고 프로그램을 종료한다. starts의 모든 지점을 시작 지점으로 BFS를 반복한다. 3번에서 YES를 출력하고 종료되지 않았다면 NO를 출력하고 프로그램을 종료한다. 코드 import sys from collections import deque..

제한 조건과 설계 시간 제한이 2초지만 노드가 30만개라서 좀 불안하다. 방향 그래프다. 시작 노드로부터 모든 각 노드의 거리를 구하는 것이므로 BFS가 좋아보인다. 자연어 알고리즘 정보를 입력 받아 그래프를 생성한다. 시작 정점으로 BFS 탐색을 시도한다. queue에서 front 노드를 dequeue한다. dequeue된 노드의 인접한 노드 중에서 아직 방문하지 않은 노드가 있다면 queue에 인접 노드를 enqueue 한다. 시작 노드로부터 인접 노드의 거리 = 시작 노드로부터 이전 노드(dequeue된 노드)의 거리 + 1 queue가 빌 때까지 위의 과정을 반복한다. 선형 탐색으로 nodes_dist에서 요소 값이 k(거리)인 index를 ans리스트에 append 한다. 답에 해당하는 노드들을..

제한 조건과 설계 1. 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. -> 노드가 최대 100개 이므로 메모리와 시간 제한이 널널하다. 2. 탐색 시작 노드에서 특정 노드에 도달하는 데 까지 거리를 묻는 문제이다. -> DFS 자연어 알고리즘 정보를 입력 받는다. 시작 노드와 탐색 노드를 설정하여 DFS 탐색을 시도한다. DFS 탐색 다음 노드로 이동할 때 마다 이동 거리를 1 증가시킨다. 특정 노드에 도달하면 그때 까지의 이동 거리를 출력하고 프로그램을 종료한다. 노드를 재방문할 때는 이동 거리를 1 감소시킨다. 3번에서 특정 노드에 도달하지 못했다면 -1을 출력하고 종료한다. 코드 import sys input = sys.stdin.readline node..

제한 조건과 설계 N이 2000이하이므로 DFS를 쓸 수 있음. 무방향 그래프. 시간 제한과 메모리 제한도 넉넉하다. DFS 탐색으로, 문제의 조건을 만족 시켜야 한다. 자연어 알고리즘 그래프 생성, 방문 테이블, 노드 목록 생성 각각의 노드를 시작 지점으로 DFS 탐색 DFS 탐색 1) 탐색 노드 방문 처리 후, route에 탐색 노드 push 2) route의 길이가 5이면 -> 1을 출력하고 종료 3) 인접 노드 중 아직 방문하지 않은 노드가 있다면 -> 그 인접 노드로 DFS 탐색 4) 인접 노드 모두를 방문했다면 -> route에서 현재 탐색 노드를 pop 한 뒤, 미방문 처리 1 ~ 3 이 종료될때 까지 반복 0 출력 후 종료( ABCDE 관계가 나왔다면 3-(2)에서 종료) 코드 impor..

제한 조건과 설계 1. 무방향 그래프다. 2. 정점의 개수가 1000개 이하다. 3. 시간 제한과 메모리 제한이 굉장히 널널하다. 4. 2번과 3번을 고려했을 때 DFS가 좋아 보인다. 자연어 알고리즘 무방향 그래프, 방문 테이블, 노드 목록를 생성한다. 연결 요소의 개수 cnt를 0으로 초기화 하여 선언한다. 노드 목록 하나 하나를 시작 지점으로 설정하여 DFS 탐색을 시도한다. 노드가 이미 방문된 지점이면 -> continue 노드가 아직 방문되지 않은 지점이면 -> DFS 탐색 DFS 탐색을 리스트 자료구조를 이용한 Stack 또는 재귀 함수를 이용한 Stack을 이용해 구현한다. 가장 중요한 POINT: 스택에 PUSH된 순간 그 지점은 방문될 지점이므로 그 즉시 방문 테이블에 방문 처리를 한다...

제한 조건과 설계 1. W와 H는 50보다 작다. -> MAX 2500 그래프 2. DFS로 2000번 이상 탐색 시 Recursion Error 발생될 수 있기에 BFS 선택 3. 시간 제한 1초, 메모리 제한 128MB -> 엄격한 제한이므로 Queue 방문 처리 필수 자연어 알고리즘과 코드 1. 그래프 입력을 받는다. 2. 그래프를 BFS로 탐색한다. 탐색 지점이 0 이면 -> continue 탐색 지점이 1 이면 -> 그 지점을 시작 지점으로 삼아 queue에 enqueue하고 BFS 탐색을 시작 land를 1증가시킨다. Queue에서 dequeue 한다. for문을 이용해 dequeue 된 지점에서 상,하,좌,우 + 왼쪽 위 대각선, 왼쪽 아래 대각선, 오른쪽 위 대각선, 오른쪽 아래 대각선으로..