dfs로 탐색해서 풀면 되는 문제이다. 내가 작성한 코드는 아래와 같다. #include #include #include #include using namespace std; vector Tickets; vector Answer; int visited[10001]; int should_end; void dfs(string s, int count){ if (count == Tickets.size()){ should_end = 1; } else{ for (int i=0;i

일반적인 코루틴과 달리 실행 중인 함수 또는 프로세스의 상태를 스택(메모리)를 사용하지 않고 저장하고 관리하는 방식이다. 코루틴은 일반적으로 실행 중인 함수의 상태를 스택에 저장하여 나중에 이어서 실행할 수 있게 한다. 스택리스 코루틴은 스택을 사용하지 않고 상태를 저장해 일반적인 코루틴과 비교해 더 가벼우며 메모리 사용량을 줄일 수 있다. 다른 데이터 구조 (객체 또는 클로저)에 저장한다. 스택리스 코루틴이 스택을 사용하지 않고 상태 정보를 저장해 효율적인 멀티 태스킹을 구현하는데 도움이 되는데, 더 효율적인 이용이 가능한 이유는 다음과 같다. 1. 스택의 경우 각 함수 호출에 대한 스택 프레임을 생성하고 제거해야해서 메모리 소모가 더 크다. 2. 많은 스레드를 사용하지 않고도 동시성을 달성할 수 있따..

구현 문제이다. 앞선 포스트에서 삼성 코테에서 좌표 회전이 많이 나온 것 같다는 글을 썼다. 이 문제 역시 좌표 회전을 포함한 문제였다. 이런 유형을 몇문제 풀어보니 대충 좌표의 규칙을 확인해서 풀면 되는 것 같다. 다행히 규칙이 여태까지 본 문제 중에서 크게 어려운 문제는 없었다. 이 문제의 경우, (i, j) -> (j, n-i-1) 을 만족함을 생각해서 풀어야한다. 이 문제의 특이한 부분은, '최단경로' 문제임에도 불구하고 dfs나 bfs로 푸는 문제가 아니라는 점이다. 어차피 한칸만 이동이 가능하고, 이동해야하는 방향성도 명확하다. 따라서 매번 상하 -> 좌우 순으로 이동이 가능한지 확인하고 이동 가능하다면 이동을 시켜주면 된다. 테스트케이스 2번에서 에러가 나서 디버깅하는 시간이 조금 오래 걸렸..

문제는 시뮬레이션 문제이다. 1. 삼성 문제는 몇가지 유형으로 나뉜다. 시뮬레이션 문제 역시 몇가지 유형으로 나뉘는 것 같다. 1. 도형 이동 시키는 문제 2. 회전하는 좌표 3. 단순 빡구현 물론 1, 2번도 단순 구현이 많이 있는 편이다. 기출문제를 풀다보니 몇가지 요령이 생겼다. 1. 여러가지 함수로 나누어서 풀 것 이렇게 모듈화를 시키니 나중에 디버깅하기도 편리하고 재사용이 편리하다 2. 푸는 도중에 계속해서 디버깅 할 것 모듈화해서 풀고 각각의 모듈이 완성될 때마다 디버깅을 하니 나중에 디버깅 할 양도 줄어들고 중간 중간에 문제를 위해 최적화를 할 방안을 생각하기가 쉽다. 2. 이 문제는 2번 유형에 해당한다. 내가 풀이한 방식은, 배열에 다음에 이동해야할 방향을 담았다. 처음에는 (0,0)부터..

#include #include #include using namespace std; unordered_map m; int solution(vector clothes) { int answer = 1; for (int i=0;i

unordered map을 사용해서 해결했다. 모든 전화번호에 대해서 문자열 그대로 map 에 등록해둔다. 그리고 각각의 전화번호에 대해서 부분 문자열을 계산한 후에 이 부분문자열과 map에 등록된 문자열 중에 일치하는 것이 있는지 확인하고 만약 일치하는 것이 있다면 접두사가 겹치는 값이 있는 것이므로 false를 리턴하고 아니라면 true를 리턴하도록 코드를 작성했다. #include #include #include #include using namespace std; unordered_map m; bool solution(vector phone_book) { bool answer = true; for (int i=0;i

bfs로 풀 수 있다. 큐를 만든 다음에 문자열을 넣는다. 그리고 모든 words에 대해서 차이가 1이 나는 것을 넣는다. visited 배열을 선언해줘서 중복 방문을 방지한다. #include #include #include #include using namespace std; struct word{ string s; int cnt; }; int visited[101]; int solution(string begin, string target, vector words) { int answer = 0; queue q; q.push({begin, 0}); while (!q.empty()){ string t = q.front().s; int num = q.front().cnt; q.pop(); if (t==..

1. 현재의 위치를 큐에 넣는다 2. 큐에서 위치를 하나씩 빼서 1. 갈 수 있고 2. 최소비용 두가지 조건을 모두 만족하면 다시 큐에 집어넣는다 3. 큐에서 도착지점을 발견하게 되면 끝낸다 이 알고리즘으로 문제를 풀었다. #include #include using namespace std; /* dfs로 풀어야할지 아니면 bfs로 풀어야할지 잘 모르겠다. bfs로 풀자 별도로 배열을 두어서 거기까지 가게된 최소 단위를 저장해놓자. 1. 현재의 위치를 큐에 넣는다 2. 큐에서 위치를 하나씩 빼서 1. 갈 수 있고 2. 최소비용 두가지 조건을 모두 만족하면 다시 큐에 집어넣는다 3. 큐에서 도착지점을 발견하게 되면 끝낸다 */ int visited[101][101]; int dx[4] = {1,-1, 0,..

dfs로 풀 수 있는 문제이다. 결국 n개의 컴퓨터가 존재하는거니까 컴퓨터가 방문되지 않았다면 그 컴퓨터부터 연결된 모든 컴퓨터들을 방문하고 (dfs 수행) visited 배열에 방문 기록을 업데이트 해준다. 그리고 다시 n개의 컴퓨터에 대해서 방문하지 않았다면 그 컴퓨터부터 네트워크에 속하는 컴퓨터들을 탐색해준다. 그리고 이렇게 방문한 n개의 컴퓨터 개수가 네트워크 개수가 된다. #include #include using namespace std; int N; int visited[201]; vector connected; void dfs(int x){ for (int i=0;i