개발자 되기(feat.SSAFY)

사용한 알고리즘 / 자료구조 스택 접근한 방법 스택으로 명세를 그대로 구현한다. 유사한 문제를 이미 풀어보아서 큰 고민 없이 스택으로 풀이했다. '9935 문자열 폭발'과 같은 문제다. https://programmer-565.tistory.com/18?category=999468 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 9935. 문자열 폭발 - 스택. 파이썬 9935. 문자열 폭발 사용한 알고리즘 / 자료구조 1. 스택..

약 두 달간 운영했던 알고리즘 스터디를 끝마쳤다. 목표는 '삼성 모의 A형 역량평가' 였다. 공통의 목표를 위해 총 8인이 일주일에 6개의 문제를 풀었다. 나는 문제 풀을 만들기 위해 일주일에 약 30개의 알고리즘 문제들을 풀었다. 덕분에 정말 실력이 많이 늘었다. 모의 A형 시험은 다 끝났다. 더 이상 공통의 목표를 찾기 힘들다고 판단해서 스터디를 종료하게 되었다. 나도 개인적으로 내 알고리즘 취약점(재귀, 분할정복, 스택, 트리)을 보강하고 싶었다. 그리고 너무 무리하다가 건강이 안좋아지기도 했다. 욕심같아서는 어떻게든 조금 더 스터디를 운영해보고 싶었지만 너무 비현실적인 목표라고 생각한다. 8인 규모의 꽤 큰 스터디였다. 매일 구글 폼으로 난이도 조사를 받고, 풀어보고 싶어하는 문제들을 조사한 뒤 ..

사용한 알고리즘 / 자료구조 우선순위 큐 (heapq) 트리 다익스트라 알고리즘 접근한 방식 두 로봇 사이의 최단 거리를 계산해야 합니다. 일반적인 다익스트라 방식으로 접근했습니다. 단, 현재 사용한 경로에서 '가장 긴 경로'를 제외해야 하므로 두 로봇 사이의 최단 경로 정보를 저장해야 합니다. 배열을 사용해 이를 구현합니다. path: 접근 경로를 저장하는 리스트. index == 노드 번호, value == 출발지 path_distance: 경로의 길이를 저장하는 리스트. index == 노드 번호, value == 경로의 길이. 다익스트라 연산을 끝마친 후 경로를 역추적합니다. 로봇1에서 로봇2까지의 거리를 계산한 뒤 , 가장 길었던 경로(worst_path)를 거리에서 제합니다. 어려웠던 점 다익..

사용한 알고리즘/자료구조 델타를 이용한 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..

예.. 이렇게 되었습니다.. 약 두 달간 알고리즘 문제를 매주 30개씩 풀었습니다. 지금은 번아웃이 와서 하루에 1~2문항만 풀고 있습니다. 싸피에서 다소 아쉬운 점도 많았지만, 아주 잘 성장하고 있습니다. 첫 웹 프로젝트를 시작했고, 분할정복 + 다익스트라를 이용한 3교대 스케쥴 작성 모듈을 제작중입니다. 삼성 소프트웨어 역량평가 모의 A형을 1시간 만에 두 문제 다 풀고 나와서 약간 당황했습니다. 지금까지 봐왔던 삼성 A형 기출문제보다는 훨씬 쉽긴 했습니다. 암튼 싸피.. 추천합니다. 5일 뒤부터 7기 모집이 시작된다던데, 모집 전에 싸피 공략글을 써보던가 하겠습니다.

사용한 알고리즘 및 자료구조 BFS 큐 델타를 이용한 2차원 좌표 탐색 접근 방식 로봇이 한 턴 내에 할 수 있는 동작은 세 가지다. 1~3칸 전진. 좌로 회전. 우로 회전. 로봇의 상태를 que에서 받은 뒤, 위 세 가지 연산을 전부 처리한다. 로봇의 위치와 로봇이 바라보는 방향 모두를 정확히 기록해야 하기에, 3차원 방문 여부 리스트를 활용했다. 문제 특이사항 일반적으로 2차원 좌표 탐색 문제에서, '방향을 돌리는' 연산은 나머지 연산을 통해 쉽게 구현할 수 있다. (나누기를 활용해 2차원 좌표 탐색에 활용하는 문제 샘플을 곧 업로드 하겠습니다.) 하지만 이 문제는 '동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4' 라고 명시하고 있다. 따라서 좌표를 입력받을 때 적당히 변형하거나, 회전하는 함수를 ..

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

9935. 문자열 폭발 사용한 알고리즘 / 자료구조 1. 스택 접근한 방법 1) 입력받은 문자열을 스택에 삽입한다. 2) 폭발 문자열이 생성되었는지 비교한다. 3) 폭발 문자열이 생성되었을 경우 스택에서 폭발 문자열의 길이만큼 문자들을 뺀다. 어려웠던 점 마지막 폭파 처리를 리스트의 슬라이싱으로 처리했다가 시간초과. 느낀 점 시간 복잡도에 항상 유의해야 한다. 같은 결과값을 내는 연산이라면 가장 빠른 방법을 선택해야 한다. 풀었을 때의 백준 티어 2021-10-09. 골드 2. import sys # 1. 입력 # 둘 다 상수이므로 대문자로 표기한다. INPUT_STRING = list(sys.stdin.readline().rstrip()) # 초기 문자열 BOMB = list(sys.stdin.read..

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 에 더한다. 문제 ..