< 프로그래머스 LV2 타겟 넘버 >
using System;
public class Solution
{
static int[] sign = new int[2] { 0, 1 }; // 0이면 빼기, 1이면 더하기
static int length = 0;
static int answer = 0;
public int solution(int[] numbers, int target)
{
length = numbers.Length;
int[] signBox = new int[length];
Calc(0, signBox, target, numbers);
return answer;
}
public void Calc(int index, int[] signBox, int target, int[] numbers)
{
if (index == length)
{
int answerInt = 0;
for (int i = 0; i < length; i++)
{
if (signBox[i] == 0)
answerInt += numbers[i];
else
answerInt -= numbers[i];
}
if (answerInt == target)
answer += 1;
return;
}
for (int i = 0; i < 2; i++)
{
signBox[index] = i;
Calc(index + 1, signBox, target, numbers);
}
}
}관련 키워드
DFS : 깊이우선 탐색
BFS : 넓이 우선 탐색
깊이 우선 탐색과 넓이 우선 탐색 둘중 어느것으로도 풀 수 있으나, 상대적으로 최단 탐색에 유리한 BFS 보다는 DFS가 모든 노드를 탐색 하는것에 있어서 유리 하기 때문에 DFS를 사용했습니다. DFS는 스택 혹은 재귀를 통해서 구현할 수 있고, 위의 방법은 재귀 함수를 통해서 구한 방법입니다. DFS/BFS의 가장 기본적이라고 볼 수 있는 문제였습니다.
< 프로그래머스 LV3 네트워크 >
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public int solution(int n, int[,] computers)
{
int answer = 0;
bool[] visited = new bool[n];
Queue<int> queue = new Queue<int> ();
for(int i =0; i < n; i++)
{
if (visited[i] == true)
continue;
answer++;
queue.Enqueue(i);
while (queue.Count > 0)
{
int checkNum = queue.Dequeue();
visited[checkNum] = true;
for(int j =0; j < computers.GetLength(1); j++)
{
if (visited[j] == false && computers[checkNum, j] == 1)
queue.Enqueue(j);
}
}
}
return answer;
}
}관련 키워드
DFS : 깊이우선 탐색
BFS : 넓이 우선 탐색
이 문제 또한 모든 노드를 탐색해야 한다는 점에서 DFS를 사용할 수도 있었으나, 이번에는 BFS를 이용해서 풀이해 보았습니다. 한번 방문반 배열에서는 다시 중복 체크가 불필요 하므로 visted 는 이중배열이 아닌 단일 배열로 설정하고 Queue 를 이용해서 BFS를 구현했습니다. Queue 또한 튜플 형태가 아닌 단일 int 값 만으로도 쉽게 노드들을 탐색하여 네트워크 갯수를 얻어 낼 수 있었습니다.
< 프로그래머스 LV2 게임 맵 최단거리 >
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Collections;
using System.Reflection;
class Solution
{
int[] dx = new int[] { -1, 0, 1, 0 };
int[] dy = new int[] { 0, 1, 0, -1 };
static int length;
static int height;
public int solution(int[,] maps)
{
height = maps.GetLength(0);
length = maps.GetLength(1);
int answer = 0;
bool[,] visited = new bool[height, length];
Queue<(int,int,int)> queue = new Queue<(int,int,int)> (); // count, x, y 순서
queue.Enqueue((0,0,0));
while (queue.Count > 0)
{
(int count,int x, int y) = queue.Dequeue();
if (x == length - 1 && y == height - 1)
return count + 1;
for (int i =0; i < 4; i++)
{
int nextX = x + dx[i];
int nextY = y + dy[i];
int nextCount = count + 1;
if (nextX < 0 || nextX >= length)
continue;
if (nextY < 0 || nextY >= height)
continue;
if (visited[nextY, nextX] == true || maps[nextY, nextX] == 0)
continue;
visited[nextY, nextX] = true;
queue.Enqueue((nextCount, nextX, nextY));
}
}
return -1;
}
}관련 키워드
DFS : 깊이우선 탐색
BFS : 넓이 우선 탐색
Dp : 동적 프로그래밍도 사용 가능
최초의 풀이에서 Dequeue 를 하는 시점에 visited 체크를 진행했더니 효율성 부분에서 시간 초과가 발생했습니다. 이는, Enqueue 때 먼저 방문 체크를 진행 해 주어야 다른 for문에서 이를 중첩적으로 받아지지 않도록 막을 수 있는 것 때문이었습니다. 즉, 같은 Vitied 의 방문 체크라도 어느 시점에서 진행하느냐에 따라서 효율성이 크게 차이날 수 있다는 점을 확인할 수 있습니다.
또, 위의 방법처럼 bool 배열로 vitied를 따로 생성하지 않고, 기존에 인풋인 maps[,] 에 dp 형식으로 지금까지의 count수를 기록하고, count가 1인 경우에만 Enqueue를 진행하도록하고, 최종 결론때 목적지의 배열에 1이 들어와 있다면 방문하지 못한것이니 1을 return 하고 그게 아니라면 maps의 값을 return 하게 하는 방식으로도 문제를 풀 수 있었습니다.
< CS 공부 정리 >
컴퓨터의 장치들에 대한 간단한 정리
CPU : 인간의 두뇌 느낌, 연산 진행, 단 기억능력은 떨어짐
RAM : 주 기억장치, 단 전원이 끊기면 저장된 메모리가
SSD : 보조 기억장치, 반 영구적으로 정보를 저장
GPU : 연산량은 많지만 난이도는 낮은 일들을 처리(그래픽)
Q : 데이터 형이 종류(실수, 정수... ) 에 따라 종류가 다양한 이유
A : 필요없이 너무 크기가 큰 변수를 사용하면 메모리 누수가 발생하고, 너무 작은 변수를 사용하면 오버 플로우가 발생하게 되기 때문이다.
캐스팅 - 형식변환
int를 short 로 바꾸고 싶은 경우
short b = (short)a와 같이 사용이 가능하다.
모든 경우에 형식 변환을 해주어야 할 필요는 없고 기본적으로 큰 변수에서 작은 변수로(double -> float) 갈 때에 데이터가 일부 소실 될 수 있기 때문에 위와 같이 캐스팅(형식변환)을 요구하게 된다.
이때, int 값을 (string)intA 이런식으로 변경해 줄 수는 없다.
이런 경우에는
(string -> int)
int.Parse(a)(int -> string)
// 스트링 포맷
string.Foramt(“당신의 HP는 {0} {1} 입니다”,hp, max);
// 스트링 인터플레이션
string message = $”당신의 hp는 {hp} 입니다.”;위와 같이 별도의 함수나 방법을 통해서 변환을 진행해 주어야 한다.
