개발자 되기(feat.SSAFY)

1744. 수 묶기 사용한 알고리즘/자료구조 1. 그리디 2. 정렬 접근 방식 입력받은 숫자들을 아래의 4종으로 구분해 정리한다. 1) 0 2) 1 3) 1이 아닌 양의 정수 4) 음의 정수 각각의 활용법은 다음과 같다. 1) 0 음의 정수에 곱해줘서 0으로 만든다. 단 음수가 2개 이상일 경우 음수끼리 서로 짝지어서 합에 더하는게 이득이다. 음수의 갯수가 홀수일 때, 가장 절댓값이 작은 1개의 음수에만 0을 곱해 소거하면 된다. 따라서 0은 True/False 로 존재 여부만 확인한다. 2) 1 갯수만큼 total 에 더한다. 3) 1이 아닌 양의 정수 큰 것 부터 2개씩 짝지어서 곱한 후 total 에 더한다. 4) 음의 정수 절댓값이 큰 것부터 2개씩 짝지어서 곱한 후 total 에 더한다. 문제 ..

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

2468. 안전영역 사용한 알고리즘, 자료구조 및 기법 BFS, 큐 델타를 이용한 2차원 배열 완전탐색 접근 방식 1. BFS로 순회. '수위'와 '건물의 높이'를 각 수행마다 비교하며 '구역'의 넓이를 구해야 한다. 2. 수위: 가장 낮은 건물의 높이보다 1 낮을 때~ 가장 높은 건물의 높이와 같을 때까지 모든 경우의 수를 완전탐색. 문제 특이사항 탐색 시작 / 끝 조건 설정이 헷갈릴 수 있다. 어려웠던 점 1. 종료조건의 설정: 높이가 올라갈수록 '구역'의 갯수가 수위에 따라 지속적으로 증가하다가 감소한다고 생각해서 아래와 같은 전제를 짜고 풀었다가 오답 처리당했다. 종료조건: 모두 물에 잠기거나 높이가 상승했을 때 '구역'의 갯수가 이전보다 줄었을 때. 느낀 점 좀 더 범용성 있는 방식으로 구현한 ..

1260. DFS와 BFS 사용한 알고리즘 및 자료구조 1. BFS, 스택 2. DFS, 큐 3. 연결 리스트 접근 방식 1. BFS와 DFS 를 구현한다. 문제 특이사항 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 한다. 스택: 후입선출 큐: 선입선출 의 특징을 염두에 두고 구현해야 한다. 2. DFS 특정 지점의 연결 리스트를 조회할 때 연결 리스트를 1) 오름차순 정렬 후 2) pop()으로 스택에 삽입하면 3) 정점 번호가 큰 순서대로 스택에 삽입된다. ==> 정점 번호가 작은 순서대로 조회할 수 있다! 3. BFS 특정 지점의 연결 리스트를 조회할 때 연결 리스트를 1) 내림차순 정렬 후 2) pop() 으로 큐에 삽입하면 3) 정점 번호가 작은 순서대로..

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

사용한 알고리즘 BFS 접근했던 법 시작점에서 끝 점까지 가는 방법을 출력해야 한다. `True` 와 `False` 로 방문 여부만을 판단하는 일반적인 `visited`리스트를 사용하는 대신 visited = [''] * 10000 를 선언. vstd에 '루트'들을 입력하며 방문처리와 루트 보관을 동시에 한다. vstd[st] 에 아무 값(',')을 채워넣고 BFS 연산 시작. vstd[ed] 가 None이 아닐 때 == 한 번이라도 닿았을 때 vstd[ed]를 출력하고 BFS 종료. 단, vstd[st]에서 임의의 값을 넣고 시작했으므로 적당한 슬라이싱이 필요. 어려웠던 점 '시작점에 방문 처리 안 해도 적당히 잘 풀리겠지' 하다가 틀렸다. 슬라이싱으로 오답을 받았다. D, S, L, R을 최소한의 연..