기록

문제 보기 이 문제는 브루트 포스 문제이다. 2차원 배열에 존재하는 CCTV의 가능한 모든 방향을 다 고려한 후 사각지대의 최소 크기를 출력하면 된다. 1번 -> 상, 하, 좌, 우 2번 -> (상, 하), (좌, 우) 3번 -> (상, 우), (우, 하), (하, 좌), (좌, 상) 4번 -> (좌, 상, 우), (상, 우, 하), (우, 하, 좌), (하, 좌, 상) 5번 -> (상, 하, 좌, 우) 5가지 CCTV가 움직일 수 있는 방향은 위와 같으며 코드 상에서 반복적으로 나오는 부분이 많아서 코드의 길이가 길다. 코드 import sys import copy def dfs(idx): global min_area, arr if idx == len(position): temp = 0 for i in..

문제 보기 이 문제는 bfs 문제이다. 물의 이동과 고슴도치의 이동 순서만 잘 고려해 준다면 어렵지 않게 풀 수 있다고 생각한다. 알고리즘의 순서는 아래와 같다. 1. 물의 이동을 수행한다. 2. 고슴도치가 이동할 수 있는 구간을 파악한 후 이동시킨다. 3. 1 ~ 2 의 과정을 도착지에 도달하거나, 더 이상 이동할 곳이 없을 때까지 진행한다. 코드 import sys from collections import deque def bfs(): position = deque() # 이동 경로 water = deque() # 물의 위치 for i in range(R): for j in range(C): if arr[i][j] == "*": water.append([i, j]) elif arr[i][j] == ..

문제 보기 이 문제는 브루트 포스 문제이다. case를 두 가지로 나누고 브루트 포스를 진행하면 된다. case 1 - abs(N - 100)의 값을 구한다. (채널 100번에서 +,- 버튼만 채널을 이동하는 것이다) case 2 - 0번부터 1,000,000까지 브루트 포스를 진행한다. (이동하려고 하는 채널의 최댓값이 500,000 이기 때문에 500,000 보다 크면서 모든 숫자의 경우의 수를 거치는 1,000,000까지를 범위로 잡았다. 코드 if __name__ == "__main__": enable = {str(i) for i in range(10)} # 0, 1, 2 ... 9 (가능한 수) # input N = int(input()) # 이동하려고 하는 채널 M = int(input()) ..

이번 글에서는 여러 가지 정렬 알고리즘을 간략하게 정리하고자 한다. 알고리즘을 4가지 특징에 따라 비교한 표는 아래와 같다. Algorithm In-Place Stable Comparison Complexity Bubble O O O O(n^2) Selection O X O O(n^2) Insertion O O O O(n^2) Shell O X O O(n^2) Merge X O O O(nlogn) Quick O X O O(nlogn) Heap O X O O(nlogn) Counting X O X O(n + k) Radix X O X d x O(n) 버블 정렬(Bubble Sort) 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다. 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서, 맨 마..

문제 보기 이 문제는 다익스트라 문제이다. 최근 코딩 테스트에서 자주 출제되는 유형이기 때문에 알아둘 필요가 있다고 생각한다. 알고리즘 순서는 다음과 같다. 1. 입력(노드, 간선, 시작 지점, 도착 지점)을 받는다. 2. 1차원 배열에 거리의 값을 무한대로 초기화해서 저장한다. (시작 위치는 0으로 초기화한다.) 3. 우선 순위 큐를 사용해서 최단거리에 있는 노드를 선택하고 그 노드와 인접된 노드까지의 거리를 계산한다. - 이미 계산한 거리보다 더 작은 거리 값이 나온다면 값을 업데이트하고 인접한 노드를 우선순위 큐에 추가한다. 4. 우선순위 큐가 빌 때까지 3번 과정을 반복한다. 다익스트라를 구현하면서 왜 우선순위 큐를 사용하는지 궁금하였다. bfs 대신에 다익스트라를 구현했다는 자체만으로도 엄청난 ..

문제 보기 이 문제는 시뮬레이션 문제이다. 삼성 기출문제는 대부분 bfs로 풀거나 지도에서 움직이는 형태가 많은 것 같다. 이 문제 또한 지도에서 움직이는 형태이다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. - 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. - 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. - 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 문제에서 요구하는 사항을 하나씩 완성시키면 쉽게 구현할 수 있다. 알고리즘 수행 과정은 아래와 같다. 1. 2차원 배열(N x N)을 만든다. (0으로 초기화) 2. 사과의 위치에 1을 저장한다. 3. (0, 0)에서 뱀은..

소프트웨어 마에스트로 11기에 합격하였다. 이번에 소프트웨어 마에스트로에 지원한 이유는 작년과 얼마나 달라졌는지 알고 싶었고, 코딩테스트 준비를 잘하고 있는지 알고 싶어서 지원하였다. 사실 2차 코딩테스트도 통과할지 몰랐다. 따라서 면접 준비는 안 되어있는 상황이었고 급하게 준비를 시작하였다. 자기소개서 정독 면접 준비의 시작은 자기소개서를 완벽하게 숙지하는 것이라고 생각한다. 다행스럽게도 자기소개서에 거짓말을 적지 않았다. 조금 부풀려서 쓸 수도 있고 팀 프로젝트를 하면서 자신이 했던 역할이 아닌 부분을 적는 사람들도 있다고 들었다. 하지만 그렇게 조금 부풀려 쓰는 것보다는 본인이 했던 것을 솔직하게 적는 것이 자신감 있고 편안하게 면접 준비를 할 수 있도록 만든다고 생각한다. 첫 문항을 제외하고는 글..

작년에는 소프트웨어 마에스트로 코딩테스트에서 떨어졌는데 이번에는 1, 2차 모두 통과하였다. 1년 동안 성장한 나 자신에 대해서 뿌듯하였으며 지금까지 공부한 내용들이 헛되지 않았음을 느꼈다. 1차 코딩테스트와 마찬가지로 문제에 저작권이 있기 때문에 정확하게 어떤 문제였는지 설명하기보다는 어떤 유형이었는지 작성하고자 한다. 알고리즘 3문제, SQL 1문제, 웹 1문제가 출제되었으며 유형은 아래와 같다. 알고리즘 1번 - dp 2번 - Union-Find 3번 - Line Sweaping(라인 스위핑) SQL - join과 정렬 활용 WEB - ajax를 이용한 통신 및 HTML에 표시 1, 2번은 dp와 union-find 방식으로 구현하였지만 3번은 라인 스위핑이 아닌 완전 탐색으로 구현하였다. SQL은..

문제 보기 이 문제는 큐(queue) 문제이며, 문제 이름을 통해서도 유추가 가능하다. 큐는 먼저 집어넣은 데이터가 먼저 나오는 FIFO 구조로 저장하는 형식을 말한다. 문제를 구현하는 알고리즘은 크게 어렵지 않았다. 문제에서 요구하는 6가지 명령을 구현하면 된다. push와 pop은 이미 구현된 append, popleft를 활용하였으며, size와 empty는 원소의 개수를 세는 변수(count)를 따로 둬서 구현하였다. front와 back은 큐가 비어있는지 확인하고 출력하면 된다. 명령 구현 push append pop popleft size count 활용 empty count 활용 front 단순 출력 back 단순 출력 코드 from collections import deque import ..

문제 보기 이 문제는 완전 탐색 문제이다. 치킨 집의 위치 중에서 M개를 고른 모든 경우의 수를 탐색하면 된다. 알고리즘 순서는 다음과 같다. 1. 치킨 집의 위치를 저장한다. 2. 치킨 집의 위치 중 M개를 고른다. (조합) 3. 치킨 거리를 계산하고 최솟값을 계속해서 업데이트한다. - (x1, y1)과 (x2, y2) 거리 -> abs(x2 - x1) + abs(y2 - y1) 코드 import itertools, sys, copy if __name__ == "__main__": N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] # 치킨집 탐색 chicken = [] for i in ran..