wonseok.log wonseok.log

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 #include #include using namespace std; vector vec(3000,""); void print(int k,int num,bool flag){ if(num == 1){ if(flag){ vec[k]+="*"; } else{ vec[k]+=" "; } } else{ if(flag){ for(int i=0;i

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 처음에는 cin, cout으로 풀이를 하였으나 시간초과가 발생하였습니다. 알고리즘은 맞다고 판단하여 scanf와 printf가 cin, cout보다 빠르기 때문에 입출력 부분만 수정하여 제출하였더니 맞았습니다 #include #include using namespace std; vector vec; void hanoi(int n,int s,int e){ if(n==1){ vec.push_back({s,e}); } else{ hanoi(n-1,s,6-s-e); vec.push_back({s,e}); hanoi(n-1,6-s-e,e); } } int main(){ int num; scanf("%d",&num); hanoi(num,1,3); printf..

이 글은 (https://m.blog.naver.com/ndb796/221234424646) 블로그 글을 참고하여 작성하였습니다. 다익스트라 알고리즘 다이나믹 프로그래밍(DP)을 활용한 대표적인 최단 경로 탐색 알고리즘입니다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 이전에 구했던 최단 거리를 사용한다는 특징때문에 다이나믹 프로그램을 활용한다고 볼 수 있습니다. 출발 노드를 설정합니다. 출발 노드에서 각 노드까지 가는 최소 비용을 배열을 만들어 저장합니다. 방문하지 않는 노드 중에서 가장 비용이 적은 노드를 선택합니다. 해당 노드를 거쳐서 각 노드로 가는 경우까지 비교하여 최소 비용을 갱신합니다. 위 과정에서 3~4번 반복합니다. 여기서 3번 과정에서 코딩 구현 시 배열을 완전 탐색해서 최소 ..

이 글은 (https://m.blog.naver.com/ndb796/221230994142) 블로그를 보고 작성하였습니다. Kruskal Algorithm 크루스칼 알고리즘은 연결된 그래프에서 가장 최소 비용을 사용하여 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 다른 말로는 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이라고 할 수 있습니다. 프로그래머스 (https://programmers.co.kr/learn/courses/30/lessons/42861?language=cpp) 이 문제를 예시로 들어 설명하도록 하겠습니다. 크루스칼 알고리즘을 쓰기 위한 핵심 개념은 크게 3가지가 존재합니다. 최소 비용 순서에 맞게 간선들을 정렬시킵니다. 정렬된 순서에 맞게 그래프에 포함시키는데 포함시..

이 글은 (https://m.blog.naver.com/ndb796/221230967614) 블로그를 보고 작성하였습니다. Union Find 유니온 파인드는 대표적인 그래프 알고리즘입니다. 여러 개의 노드가 있을 때 두 가지의 노드 하나의 그래프로 연결되어 있는지 판별하는 알고리즘입니다. 먼저, 배열을 만들어서 해당 노드번호로 부모 노드번호를 가리키게 합니다. 처음에는 당연히 연결된 그래프가 없기 때문에 각자 자신의 노드번호를 가리키게 됩니다. 1과 2를 연결하게 되면 합친다는 뜻에서 Union이라고 부르고 노드번호 중 작은 노드번호가 부모노드가 됩니다. 이렇게만 구현할 경우 2와 3이 연결하게 되면 부모노드가 2가 되는데 1과 3이 같은 그래프로 연결되어 있는지는 알 수가 없습니다. 따라서 재귀함수를..

이 문제는 c++로 풀이를 작성하였습니다. 문제 예시 풀이 #include #include using namespace std; // 우, 상, 좌, 하 int dir[4][2]={{0,1},{-1,0},{0,-1},{1,0}}; int n; // map에 1이 표시된 부분을 확인하여 사각형을 이룬다면 answer+1 bool map[101][101]={0}; int main(){ int answer=0; cin>>n; for(int i=0;i>x>>y>>d>>g; vector v; // 방향을 담을 벡터 v.push_back(d); // 0세대 방향 // 한 점을 기준으로 시계 방향으로 한다는 것은 // 회전시 각 방향을 시계반대 방향으로 회전하면 된다 for(int j=1;j=0;k--){ int p..

이 문제는 c++로 풀이를 작성하였습니다. 문제 예시 풀이 #include #include using namespace std; int n,m; int map[500][500]; // 각 테트로미노가 나올수 있는 경우의 수 int cnt[5]={2,1,8,4,4}; // 방향 벡터 dir[5][2] 는 대각선을 위해 표시 int dir[6][2]={{0,0},{0,1},{1,0},{0,-1},{-1,0},{1,-1}}; // 테트로미노가 나올수 있는 경우의 수를 방향으로 표시 int vec[5][8][4]={ {{0,1,1,1},{0,2,2,2}}, {{0,1,2,3}}, {{0,2,2,1},{0,3,3,2},{0,1,2,2},{0,2,3,3},{0,2,2,3},{0,2,1,1},{0,3,2,2},{0,..

이 문제는 c++로 풀이를 작성하였습니다. 문제 예시 풀이 #include #include using namespace std; int dir[4][2]={{0,1},{-1,0},{0,-1},{1,0}}; int n; bool map[101][101]={0}; int main(){ int answer=0; cin>>n; for(int i=0;i>x>>y>>d>>g; vector v; v.push_back(d); for(int j=1;j=0;k--){ int p=(v[k]+1)%4; v.push_back(p); } } map[y][x]=1; for(int j=0;j