BFS...,,.,,

BFS로 풀면 된다.

다른 조건이 있을까 싶었는데. BFS로 전체 탐색하듯이 하면 된다. 시간초과 안남

풀이

1. 시작점부터 큐에 넣어 up, down 이동경로를 다시 큐에 넣는다.

2. 큐에서 나온 점이 도착점과 같다면 종료한다.

3. 범위가 0보다 작거나 최대값인 F보다 크다면 패스한다.

소스

자료구조...,,,  탐색....,,

범위가 작음.... 문제 생길게 없다.

해쉬맵 알고 있다면 쉽게 풀 수 있음

풀이

1. 해쉬맵을 통해 이름과 횟수를 저장한다. (key, value) 처럼

2. 해쉬맵을 전체 탐색하여 가장 큰 value를 max에 저장한다.

3. 해쉬맵의 key들을 리스트로 옮긴다. ( 사전 출력을 하기 위해)

4. 리스트를 정렬한다.

5. 리스트에서 value값이 max값인 key를 하나만 출력한다. 

소스

시뮬레이션....,,

아이디어는 간단한다. 거리 먼 M개씩 묶어 거리를 합친다. 최종적으로 합친 거리에서 가장 멀었던 거리를 뺀다.

나는 음수와 양수를 나눠서 계산했다.

범위가 작았기에 가능했지만 내가 구현한것은 성능 상 나쁜구현인거 같다.

풀이

1. 양수와 음수를 저장할 우선순위 큐를 사용한다. (우선순위큐를 사용하면 정렬되서 pop 할수 있기 때문에 사용했다)

2. 음수 우선순위큐와 양수 우선순위큐에서 따로 실행한다. 

3. 큐가 빌 때까지 M만큼 계속해서 뺀다. (즉 음수나 양수에 있는 모든 책을 가져오는 것)

4. 그때 가장 맨처음 나온게 이번에 이동했을 때의 가장 먼 거리를 갖고 있으므로 그때만 전체 길이에 추가해준다.

5. 전체길이에 추가할 때마다 전체 최장 거리를 저장해준다.

6. 전체 길이에서 최장 이동 거리를 뺀다.

7. 끝;; 설명 진짜 못한다.

소스

순열,, 재귀...,,

순열(Permutation) 이란? 서로 다른 물건들 중 몇 가지 대상을 뽑아 일렬로 나열하는 것

나는 순열을 어떻게 짜는지 몰랐다. 재귀로 짜는건가? 백트래킹으로 짜는건가? 많은 생각을 했지만 짜지 못했고

다른 사람의 소스코드를 봤다.... 아주 간단하더라.

풀이

1. 존재하는 수만큼 visited[] 배열을 만들어준다. 똑같은 값이 2번 들어가지 않게

2. 첫자리에 올 수를 반복문을 통해 하나씩 넣는다.

3. 두 번째 자리 부터 반복문을 다시 돌리는데 이미 사용한 숫자는 사용할 수 없도록 visited[] 배열을 통해 제한한다.

4. 재귀의 깊이가 갖고 있던 수만큼 들어갔을 때 출력하고 return하여 현재 순열에서 빠져 나온다.

5. 끝;; 내가 설명을 많이 못한거같은데 코드를 보면 이해 갈 수 있을 것이다.

소스

백트래킹......,,, DFS....,,,

DFS, 백트래킹 문제이다.

배열의 크기가 5x5이므로 전체 탐색을 해도 시간초과나 스택 오버플로우가 나지 않는다.

마음놓고 풀었다.

다만 String 형식으로 주고 받아야한다는 생각하는게  어려웠다.

풀이

1. 배열 0,0 부터 N-1, N-1까지 dfs 백트래킹을 실시한다.

2. 상하좌우로 계속해서 방문탐색한다. (왔던길도 다시 올 수 있다.)

3. 탐색의 깊이가 6일 경우 Set에 문자열을 넣는다. 이때 Set을 사용하는 큰 이유는 중복을 없애기 위함이다.

4. Set의 크기를 출력한다.

소스

그리디....

단순한 문제인거 같다.

수가 작기 때문에 메모리초과나 시간초과등에 신경을 안써도 된다. 아무렇게나 구현해도 된다.

풀이

1. 6개짜리 팩과 낱개를 각각 배열에 저장한다.

2. 팩, 낱개 배열을 정렬한다. (가장 적은 비용이 먼저 오도록)

3. 비교한다.

 - 가장 싼 6개짜리 팩으로 모두 살 것인지

 - 가장 싼 낱개로 모두 살 것인지

 - 가장싼 6개짜리 팩과 가장 싼 낱개를 이용해서 살 것인지

소스

DP.........

dp 문제

풀이

1. oox, oxo, xoo 의 경우가 존재한다.

 1-2. oox 의 경우 dp[i-1] 가 된다.

 1-3. oxo 의 경우 dp[i-2] + arr[i] 가 된다.

 1-4. xoo 의 경우 do[i-3] + arr[i-1] + arr[i] 가 된다.

2. 위의 3경우중 가장 큰 값을 선택하면 된다.

 dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i])) 라는 수식이 나온다.

3. 끝.

4. 아 여기서 N=1 일때와 2일때가 존재한다. 이때의 경우를 조건을 통해 잘 계산하도록 한다.

소스

자료구조....,,, 정렬.....,,

나는 해쉬맵 자료구조를 사용했다.

범위가 (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 이므로 counting sort가 불가능하다.

그래서 해쉬맵을 사용했다. 그리고 해쉬맵의 키값들을 리스트에 저장해줘서 정렬 후 출력했다.

풀이

1. 해쉬맵에 키와 빈도수를 저장한다.

2. 해쉬맵에 저장된 모든 키들을 리스트에 저장한다.

3. 리스트들안에 저장된 키들을 빈도에 따라서 정렬한다.

4. 출력

소스

BFS,,...

오랜만에 BFS 문제 풀려고 했었는데 생각이 않났다. 그래서 시간 두고 다시 풀어봄.

아주 단순히 이전 값에 +1 해주면 되는 거였다.

풀이

1. 토마토가 익은 점들을 큐에 넣어준다. (동시 다발적으로 일어나기 때문에 큐를 사용한 BFS)

2. 익은 토마토 상하좌우를 탐색하며 익지 않은 토마토가 있으면 그 위치를 큐에 넣어준다. (그 위치의 값은 최대 일수를 계산하기 위해 전 위치 +1 을 해준다.)

3. 큐가 빌때까지 계속해준다.

4. 전체 토마토들을 탐색하여  익지않은 토마토(0 값) 하나라도 있으면 -1를 출력한다. 

5. 그 외는 최대 일수를 출력한다.

소스

삼성 SW 역량테스트,,,,,,

17년 상반기 DS부문 1번문제 였다.

맨 처음에는 그냥 if, while, for 등의 떡칠로 문제를 풀게 되었다.

2번째 풀 때는 반복문으로 풀면 조금 더 쉽지 않을까? 싶어서 Queue를 이용해서 풀었는데

다음 x,y좌표 구하는 규칙은 쉽게 구할 수 있었지만 방향을 구하는 규칙을 찾는데 너무 많은 시간을 투자했다.

결국 맨 처음 조건문,반복문 떡칠이 시간이 훨씬 조금 걸렸다.... 아무튼 풀긴 풀었다.

1. 현재 위치를 청소한다.

 --> 현재 위치 청소

2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 

 --> 위치는 제자리, 방향만 왼쪽으로 회전

  2-1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.

    --> 왼쪽으로 회전한 방향의 앞이 청소되지 않았다면 한칸 전진한 후 1번으로 진행한다. (즉 앞의 칸 청소부터 다시 시작한다)

  2-2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

    --> 왼쪽으로 회전한 방향의 앞이 청소할 공간이 없다면, 다시 왼쪽으로 회전한다.

  2-3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.

    --> 한바퀴를 다 돌았을 때 (네방향 모두 청소가 되어있을 때) 앞이 벽이라면, 뒤로 한칸 이동한다.

    --> 처음 바라보는 방향이 북쪽일 경우 탐색은 서쪽, 남쪽, 동쪽, 북쪽 순이 된다. 결국 마지막에 바라보는 방향은 북쪽이다. 그럴경우 남쪽으로 후진한다.

  2-4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

     --> 말 그대로...

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

로봇청소기의 동작과정이다. 저 문제를 이해하는게 엄청 어렵다. 내가 설명을 잘 했는지도 잘 모르겠다.

문제만 잘 이해한다면 쉽게 풀 수 있는 문제이다. 풀이도 딱히 필요없다. 

풀이

풀이는 이동과정으로 대체 한다.

소스 - 1 (규칙 없이)

소스 - 2 (규칙으로)