본문 바로가기

C C++165

[C/C++] 백준 10026번 적록색약 문제 풀이 이 문제는 전형적인 BFS와 DFS 문제이며 DFS로 문제를 풀도록 하겠다. 예시의 부분은 아래와 같다. R R R B B G G B B B B B B R R B B R R R R R R R R 예를 들면 첫 번째 [1,1], [1,2], [1,3] 영역을 칠하게 된다. 어떠한 식으로 칠해야할까? 1) for문으로 모든 영역을 훑도록 한다. (visit 체크된 좌표는 이미 칠했으므로 넘어간다.) 2) [1,1]이 입력되면 해당 좌표를 방문하였으므로 visit 체크한다. 3) 상하좌우 탐색한다. 4) 범위 밖으로 나가면 넘어간다. 5) 색이 다르는 등의 조건이 맞지 않는 경우 넘어간다. 6) 연결된 부위에서 조건이 맞는 내용은 또 칠한다. (DFS 함수에 탐색된 좌표를 다시 넣는다.) 위와 같다.. 2022. 10. 26.
[C/C++] DFS 61. 특정 수 만들기(DFS : MS 인터뷰) 문제 풀이 N개의 원소로 구성된 자연수 집합이 주어지면, 집합의 원소와 ‘+’, ‘-’ 연산을 사용하여 특정 수인 M을 만드는 경우가 몇 가지 있는지 출력하는 프로그램을 작성하세요. 각 원소는 연산에 한 번만 사용합니다. 예를 들어 {2, 4, 6, 8}이 입력되고, M=12이면 2+4+6=12 4+8=12 6+8-2=12 2-4+6+8=12 로 총 4가지의 경우가 있습니다. 만들어지는 경우가 존재하지 않으면 -1를 출력한다. 입력설명 첫 번째 줄에 자연수 N(1M; for (int i=1; i>arr[i]; } } void DFS(int cnt, int sum) { if (cnt==N+1) { if (sum==M) { flag=true; cnt_value++; return; } return; } DFS.. 2022. 10. 22.
[C/C++] DFS 60. 합이 같은 부분집합(DFS : 아마존 인터뷰) 문제 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. 입력설명 첫 번째 줄에 자연수 N(1n이 되어 if-return을 만나서 return된다. 1+2+3을 모두 더한 것이다. 그렇다면 return되었으니 x+1에서 하나 이전인 x값을 가지는 함수로 돌아가게 된다. 그리고 그 다음 DFS(x+1, tmp);를 만나게 된다. 이 함수는 횟수는 늘어나는 데, x .. 2022. 10. 20.
[C/C++] Leetcode 412. Fizz Buzz 문제풀이 이 문제는 기본적으로 int값을 string으로 변경할 수 있어야한다. string에서 int로 변환 #include 으로 부를 수 있는 to_string(int x)라는 함수를 통해 이를 구현할 수 있다. 외우자. (반대로, string에서 int로 변경하는 경우, stoi(string x)로 변경할 수 있다.) 해당 함수를 사용하지 않고 (string) (48+i) 등으로 형변환하여 풀고자 하였으나, ASCII 값은 0~9를 표현하는 것이기 때문에, 11, 13 등 자릿수가 두 자리 이상이 되면 구현하기 복잡해진다. to_string(int x) 함수가 가장 간단하다. 조건에 따라 vector에 값 넣기 if-else 조건에 따라 값을 넣으면 된다. 소스코드 class Solution { p.. 2022. 10. 17.

티스토리툴바