본문 바로가기

분류 전체보기65

중등수학으로 2차원 배열 방향 전환 이해하기 현재의 상태(State)가 앞으로의 동작에 영향을 주는 경우가 있는데, 이를 조금 쉽게 다룰 수 있게 노력해보자! 중등수학의 개념을 활용해 배열의 방향 전환에 추가로 도움도 줄 예정이다! 쉽게 만들어보고 싶은 상황은 그림과 같다. 위의 그림에서, 현재 A의 위치에 있고, 방향은 위를 바라보고 있을 때 A가 확인할 수 있는 칸, 즉 영향이 미치는 범위를 파란색으로 빗금 쳐놓은 부분이라 생각하자 A를 (x, y)로 가정하고 A로부터 가장 가까운 파란색을 좌표로 표현해보면, 위의 그림과 같다. 만약, A가 왼쪽을 본다면? 파란색 영향을 미치는 구간은 A가 회전한 방향 쪽으로 같이 돌아갈 것이다. 역시 파란색의 좌표를 표현해보면 위와 같이 돌아갈 것이다. 중등수학이 나오려면, 한 바퀴를 다 돌려봐야 한다! 다 .. 2024. 1. 3.
[프로그래머스] PCCP 기출문제 4번, 수레 움직이기 문제 https://school.programmers.co.kr/learn/courses/30/lessons/250134 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 제가 복잡해하는 유형입니다. 동시에 여러개의 타겟이 움직일 수 있는 형태요 ㅎ 문제에서 '최소 혹은 최대의 경우를 구해봐라' 라고 나온다면, 보통 백트래킹으로 모든 경우를 체크해가며 최소인 경우를 찾으려 하는 것 같습니다. 추가로 구하려는 값이 최소라면, 현재 구해진 답보다 큰 값이 나오고 아직 구해야 할 연산들이 남아 있다면 더 체크를 해주지 않아도 되는 것이 백트래킹의 기본 아이디어이기.. 2023. 12. 24.
그래프에서 SCC (Strongly Connected Component) 찾기 SCC에 대한 증명을 위한 글이 아님을 알려드립니다! SCC란 그래프에서 서로 다른 노드 u, v 2개를 뽑았을때, u->v로도 직간접적으로 갈 수 있고, v->u로도 역시 직간접적으로 갈 수 있는 노드들의 집합이다. 위의 그림에서 SCC를 추출해보자면, [1, 2, 3], [4, 5], [6] 으로 나뉠 것이다. 사람의 눈으로 직관적인 분리는 쉽지만, 이를 코드로 구현할 때를 생각해보자 그런데! SCC를 찾기 아주 조금 전에 우선적으로 생각해볼 문제가 있다. 1->2로 가는 그래프가 있다 가정해보자. 1번 노드에서 시작해 후위표기 즉 post number를 각 노드에 붙인다 하면, 1번 노드가 2번이 되고 2번 노드는 1번이 될 것이다. 2에서 시작하는 후위표기를 하면 이 역시 1번 노드가 2번, 2번.. 2023. 12. 7.
[백준] 선수과목 - 14567번 문제 https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 내가 하는 이해 예제 입력 1을 생각해보면, 3번과목을 듣기 위해서는 2번과목을 선수해야하고 또 그 2번과목을 듣기 위해서는 1번과목을 선수해야 한다. 즉 1 -> 2 -> 3 순으로 이수해야 한다. 동일하게 예제 입력 2를 생각해보면, 1 -> 2 -> 5 1 -> 3 4 -> 5 위와 같이 1 -> 2 -> 5, 4 -> 5 처럼 5번 과목의 입장에서 생각할 때, 독립적인 깊이를 가진 여러 선수과목 코스가 생길 수.. 2023. 12. 6.

티스토리툴바