개발자 되기(feat.SSAFY)

사용한 알고리즘/자료구조 델타를 이용한 2차원 배열 탐색 counter sort 해시 테이블(딕셔너리) 접근한 방법 학생의 위치를 정할 때마다 모든 좌표를 순회하며 주위 4 칸의 좌표 정보를 확인하는 브루트포스 알고리즘으로도 정답 처리를 받을 수 있습니다. 하지만 이런 브루트포스 방식은 O(4*(N**2))의 시간 복잡도를 가진, 굉장히 비효율적인 알고리즘입니다. A학생의 자리를 배정한다고 생각해봅시다. A학생이 좋아하는 학생들 중 한 명 이상이 이미 교실에 앉아있다고 하면, 우리는 이 학생이 좋아하는 학생들 근처 자리들만 조회한 후 우선순위를 계산하면 됩니다. 이 연산을 위해 딕셔너리를 활용합니다. 딕셔너리는 두 개를 사용합니다. 각 학생이 좋아하는 학생들의 정보를 담은 딕셔너리 학생 '주변 자리 좌표..

17070. 파이프 옮기기 1 사용한 알고리즘, 자료구조 및 기법 다이나믹 프로그래밍 비트마스킹 델타를 이용한 2차원 배열 탐색 접근한 방식 1. 파이프의 '머리'는 우, 하, 대각으로 움직일 수 있다. 1) 파이프의 '꼬리'는 신경 쓸 필요가 없는 변수다. 머리가 갈 수 있는 곳은 꼬리도 무조건 갈 수 있다. 2) 단, 기둥이 있는 곳에는 파이프를 놓을 수 없다. 2. visited[row][column]에는 '이 지점에 방문할 수 있는 방법의 수'를 저장한다. 1) 파이프가 '어디 방향에서 오는지'에 따라서 방법의 수가 달라진다. 2) visited[row][column]은 세 개의 정수를 가진 리스트로 구성한다.[0, 0, 0] 3) 0번 idx에는 '가로에서 접근한 방법의 수', 4) 1번 idx..

14500. 테트로미노 사용한 알고리즘/자료구조 1. 델타를 이용한 2차원 배열 탐색. 2. 브루트 포스 접근방식 테트로미노들의 상태를 모두 구현한다. 모든 경우의 수를 완전 탐색한다. 문제 특이사항 구현해야 할 양이 많은 문제다. 계획을 잘 짜고 구현하지 않으면 디버깅이 난해할 수 있다. 개선 가능한 점 1) 문제의 조건을 잘 읽고 가지를 칠 수 있다. 2) 부분합을 미리 구해둔 뒤 반복되는 연산을 생략할 수 있다. 느낀점 상당히 배운 점이 많은 문제입니다. 처음 풀 때에는 브루트포스로 풀었으나, 갈수록 시공간 복잡도를 절약할 수 있는 다양한 방법들이 떠올랐습니다. 곧 다른 풀이들을 업로드 하겠습니다. 문제를 풀었을 당시 백준 티어 2021-09-27, 실버 2 from sys import stdin ..

사용한 알고리즘, 자료구조 2차원 배열의 델타 검색 접근 방식 문제의 조건을 잘 읽고 정확히 구현한다. 입력 지도의 가로, 세로 길이를 입력받는다. 로봇의 시작 좌표와 초기 방향을 입력받는다. 선언 방문 여부 배열을 선언한다 지도 배열에 방문 여부를 기록할 수도 있다. 델타 탐색을 위한 배열 선언 로봇의 다음 좌표를 담을 리스트를 선언한다. 어려웠던 점 삼성 스타일 완전탐색 중에서는 비교적 간단한 편이었다. 느낀 점 시간을 아낄 수 있는 방법이 많았다. 일반적인 완전탐색(BFS) 처럼 생겼다는 이유로 습관적으로 deque를 import 했으며, visited배열을 선언하기도 했다. 문제를 다시 읽어보니 시공간 복잡도를 줄일 수 있는 방법들이 많았다. 파이썬은 느린 편히니 특히나 시간을 많이 아껴야한다. ..

사용한 자료구조 / 알고리즘 덱(deque) 접근 방법 고전 게임 '스네이크'를 직접 구현하는 알고리즘 문제다. 구현해야 하는 요소는 다음과 같다 사과를 먹을 때마다 뱀의 길이가 증가. 뱀이 자신을 물거나 벽에 닿으면 종료. 뱀이 성공적으로 이동할 경우, 뱀 꼬리를 옮겨줌. 시간에 따른 이동방향 변경 구현한 방법 뱀의 길이: 1로 시작해서 사과를 만날 때마다 증가하는 int 변수. 뱀의 좌표: deque로 관리. len(deque)가 뱀의 길이보다 클 경우, popleft 후 지도에서 뱀을 지워야 한다. (가장 먼저 들어갔던 곳 == 발자취 == 꼬리) 시간 값을 key로 하는 dictionary 를 선언. 매 초마다 value가 있는지 확인한다. 느낀점, 특이사항 문제를 꼼꼼하게 읽어야 한다. '뱀의 ..