Tempo Tempo

1. 수레 움직이기📑 사용한 알고리즘구현📑 구현 방식에 대한 간략한 설명모든 경우의 수를 탐색하기 위해, 2중 for문을 사용해 파란색과 붉은색 수레를 각각 움직인다. 어떤 수레를 먼저 움직이는지는 완전탐색이기 때문에 상관이 없다.N이 4로 작은편이라 재귀로 풀이할 수 있었습니다.시간복잡도는 O(V^2 + E^2) 입니다.++ 이 문제에서 주목해야 할 부분은, 서로 "스위칭"이 불가능 하다는 것 입니다.ㅁ R ㅁ ㅁㅁ B ㅁ ㅁㅁ ㅁ ㅁ ㅁ다음과 같이 빨간색 수레와 파란색 수레가 존재할 경우,ㅁ B ㅁ ㅁㅁ R ㅁ ㅁㅁ ㅁ ㅁ ㅁ다음과 같이 움직일 수는 없습니다. 당연히 한 쪽 수레가 움직이려면, 빈 공간으로 움직여야 합니다.해당 부분을 주의해 수레를 움직이는 조건식을 작성해야 합니다.제 코드에서는 ..

1. 도넛과 막대 그래프 📑 사용한 알고리즘 BFS 📑 구현 방식에 대한 간략한 설명 새롭게 생성된 정점은 쉽게 구할 수 있습니다. 해당 정점으로부터 나가는 간선이 2개 이상이면서(도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다. 라는 조건이 있음), 들어오는 간선이 0개인 정점을 찾으면 됩니다. 그렇게 시작 정점을 구한 후, 해당 정점으로부터 BFS 방식으로 분기하며 각 그래프의 종류를 찾았습니다. 먼저 8자 그래프인 경우, 임의의 한 정점에서 시작할 경우 탐색하다 보면 간선이 2개 연결된 정점이 무조건 존재합니다. 그래서 연결리스트 탐색 중 연결된 정점 개수가 2개 이상이면 8자 그래프로 판단했습니다. 도넛 그래프인 경우, 탐색하다보면 무조건 이미 방문한 정점을 탐색..

주어진 이진트리가 완전 이진 트리인지 확인하는 문제이다. 알고리즘은 BFS 탐색을 이용해 풀었다. BFS 탐색을 진행하면서, left나 right가 null이더라도 null Node를 탐색한것처럼 배열에 넣어 완전 이진트리인지 검사했다. 완전 이진트리이기 위해서는, BFS 탐색을 진행했을 때 null 노드를 방문했다면 앞으로 방문 할 노드들은 모두 null 노드이어야 한다. 위의 예시는 완전 이진 트리가 아닌 경우인데, NULL 노드도 방문한다고 가정한 후(단말 노드의 자식 노드라면 방문하지 않는다.) BFS 탐색을 해보면, 1 -> 2 -> 3 -> 4 -> 5 -> NULL -> 7 과 같은 형태로 방문하게 된다. 이렇게 NULL 노드를 방문했다면 그 다음으로 방문 할 모든 노드들은 NULL이어야 완..

가장 긴 등차수열의 길이를 구하는 문제이다. 처음에는 dfs 형태로 구현을 했는데, 이상하게도 특정 테스트 케이스에서만 무한루프가 돌아 문제점을 찾지 못한 채 멈췄었다. rnum의 최대길이는 1000이기 때문에, 내가 예상한 반복 회수는 최악일 때 500500번이였다. 이 정도는 0.1초도 되지 않을 텐데, 현재 rnum에 들어가 있는 특정 케이스에서만 무한루프가 도는 상태이다. dfs이긴 하지만 한 숫자를 선택하면 그 다음 인덱스부터 탐색을 진행하기 때문에, 따로 boolean 배열은 쓰지 않았다. package leetcode; public class LongestArithmeticSubsequence { static int answer = 0; static int[] rnum = new int[]{..

이미 정렬된 LinkedList에, 정렬을 유지한 채로 값을 넣는 문제다. Example 1: Input: LinkedList: 25->36->47->58->69->80 data: 19 Output: 19 25 36 47 58 69 80 Example 2: Input: LinkedList: 50->100 data: 75 Output: 50 75 100 총 경우의 수는 3개이다. 1. new node가 head node가 되는 경우 head 노드가 null인 경우 현재 연결 리스트에 노드가 한 개도 없는 상태이므로, key값을 이용해 새로운 노드를 만든 후 head노드로 만들어준다. 리스트에 넣을 key값이 head 노드의 값보다 작을 경우 head 노드가 null인 경우와 같이, 새롭게 만든 node가 ..

https://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/#algo1 Top 10 algorithms in Interview Questions - GeeksforGeeks Top 10 algorithms in Interview Questions www.geeksforgeeks.org 매번 문제를 풀 때 마다 한 번씩 실수하는 알고리즘들을, 다시 한 번 구현해보며 각각을 정리하고 있다. BFS와 DFS는 어렵지 않게 구현해서 따로 작성하지는 않았지만, 다익스트라는 헤맸던 부분이 생겨 정리하게 되었다. BFS, DFS와 Dijkstra의 차이점은, 다음 노드로 가기위한 가중치이다. BFS, DFS -> 다음 노드로 가기위한 가중치는 모두 ..

간단한 탐색 문제였지만, bfs로 풀려다가 각각의 순회마다 따로 visited를 빼줘야하는 부분에서 애를 먹었던 문제. 역시 이런 탐색 문제는 dfs + 백트래킹 방식이 제일 구현도 쉽고 확실하게 맞을 수 있는 방법인것 같다. 기본적인 4방향 탐색 문제 중 가장 무난한 문제였다. package leetcode; import java.util.*; class GoldMine { static class Cord { int x; int y; int gold; Cord (int x, int y, int gold) { this.x = x; this.y = y; this.gold = gold; } } static int[][] arr; static int[] dx = {0, 0, 1, -1}; static int[..

문제 설명 다른 사람들의 코드에 비해서 빠르다거나 메모리를 효율적으로 사용한 것은 아니지만, 쉽게 이해 할 수 있는 코드라고 생각하게되어 포스팅을 하게되었습니다. 기본적인 개념은, https://www.acmicpc.net/problem/14503 백준 14503번 로봇청소기로부터 따왔습니다. 알고리즘은 이렇습니다. 해당 도형을 y축 대칭시켜서 나온 모양이 원래 모양과 다르지 않다면, 동서남북 각 방향으로 도형을 그리게 되면 모든 경우의 수를 나열 할 수 있게 됩니다. 모양이 다른 경우, y축 대칭 시킨 도형에대한 메소드를 하나 더 만들어줘야 합니다. y축 대칭시킨 후에도 모양이 같은 경우(메소드 1개) y축 대칭 시킨 후에 모양이 변하는 경우(메소드 2개) ※ Y축 대칭해서 달라지는 도형들은 h와 ㄱ ..