개발자 되기(feat.SSAFY)

1. 사용한 알고리즘 | 자료 구조 BFS 큐 2. 풀이 접근 방식 전형적인 BFS 문제입니다. K회 만큼 BFS 연산 후 Queue 에 있는 값을 정렬, 출력합니다. 3. 특이사항 Stack 2개를 스왑하는 방식으로 사용하여 deque 를 import 하지 않고 BFS 알고리즘을 구현할 수 있습니다. 4. 언어 | 실행시간 | 메모리 사용량 Python3 | 1264ms | 97164kb from sys import stdin def solution(): # 1. 입력 # N: 정점의 수 | M: 간선의 수 # K: BFS 연산 횟수 | X: BFS 연산 시작점 N, M, K, X = map(int, stdin.readline().split()) # 2. 선언 # 2-1. paths: 간선 정보 pat..

10월 13일에 백준 플레티넘5 를 달성했습니다. 작년 10월 20일에 골드 1을 달성하고 나서 거의 1년만이네요. 올해 3월까지 1일 1알고리즘을 했었습니다. 그러다 프로젝트도 바쁘고, 건강도 악화되어 7개월간 알고리즘 풀이를 쉬었습니다. 지금 생각해보니 `알고리즘 티어 욕심` 을 부린 탓인 것 같기도 합니다. 하루에 1~2문항씩 재미있게 풀었으면 좋았을텐데, 플레티넘 티어를 달성하겠다는 생각때문에 알고리즘 풀이를 즐기지 못했습니다. 잘 지내고 있습니다. 스케이트보드도 즐겁게 타고 있습니다. 별 다른 부상 없이 10개월간 취미를 유지했습니다. 운이 참 좋았다고 생각합니다. 모아두었던 알고리즘 풀이들도 업로드 하겠습니다.

사용한 알고리즘 / 자료구조 스택 정렬 힙 정렬 접근한 방법 정렬을 이용한 접근법 '책 더미'(스택)의 정보를 M회 입력 받는다. '책 더미'를 입력받을 때마다 각 책 더미가 내림차순으로 정렬되어있는지 확인한다. 만약 단 하나의 '책 더미'라도 내림차순 정렬되어있지 않다면, 문제에서 요구하는 정렬 연산은 불가능하다. 'is_order_possible'이라는 변수에 '정렬이 불가능하다'는 정보를 기입한다. 반복문을 종료한다. '정렬' 가능 여부를 파악한다. 조건에 맞게 콘솔에 출력한다. 힙 정렬을 이용한 접근법 '책 더미'(스택)의 정보를 M회 입력 받는다. '책 더미'를 입력받을 때마다 각 책 더미의 가장 오른쪽 원소를 pop한다. 2번에서 pop된 원소를 '책 더미'의 index값과 함께 heap 에 ..

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

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

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

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

1759. 암호 만들기 사용한 알고리즘 및 자료구조 DFS(백트래킹) 집합 접근 방식 문제의 조건은 아래와 같다. 중복되지 않는 알파벳들을 네 개 선택해서 나열해야 한다. 암호는 오름차순으로 정렬되어야 하며 자음이 2개, 모음이 1개 이상이여야 한다. 아래의 로직대로 풀었다. 입력 / 선언 input을 받는다. 길이가 127인 아스키-리스트를 만든다. input값에 등장한 알파벳들을 아스키값으로 변환, askii 리스트의 해당 인덱스에 '값이 있음' 표시 해준다. 연산 DFS 연산한다. index가 97일 때부터 연산한다 (ord('a') == 97) 연산 종료 조건 길이가 L일 때. 정답 조건 모음이 1개 이상, 자음이 2개 이상 DFS연산 모든 아스키값을 순회하면서 특정 아스키 값이 '있을 떄' 사용..

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

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