C++(21)
-
[C++/그래프 다루기/프로그래머스 LV.3] 길 찾기 게임
https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr x,y 좌표에 따라서 흩어진 노드들을 그래프화 시켜서 전위순회(Preorder), 후위순회(Postorder)을 출력하는 문제입니다. 우선 정렬되어있지 않은 여러 노드들을 하나의 그래프로 완성시키기 위해서 노드를 관리할 수 있는 구조체를 생성했습니다. 해당 과정이 이 문제의 핵심이라고 할 수 있습니다. struct node { int x,y; //본안의 좌표 int data; //인덱스 node*..
2023.12.26 -
[C++/BackTracking/백준] 2580번 스도쿠
https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹 문제 중 하나인 스도쿠 문제입니다. 9x9 격자가 주어졌을때 조건에 따라 빈칸을 다 채우는 것이 스도쿠 입니다. 조건은 다음과 같습니다. 1. 모든 칸에는 1~9사이의 숫자가 들어간다. 2. 행 9칸에는 1~9사이의 숫자가 중복되면 안된다. 3. 열 9칸도 마찬가지로 1~9사이의 숫자가 중복되면 안된다. 4. 3x3 격자로 나누게된다면 총 9개의 구역이 생기는데 빈칸을 채우려는 숫자의 구..
2023.08.29 -
[C++/BackTracking/백준] 9663번 N-Queen
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 알고리즘에서 유명한 문제입니다. 체스판에서 퀸은 행,열 대각선을 자유롭게 움직일 수 있습니다. N x N 체스판에서 퀸을 놓아 퀸끼리 서로 공격 할 수 없게 설계하도록하는 모든 경우의 수를 구하는 것이 문제입니다. 조건 1. 같은 행과 열에는 퀸이 두 개 이상 존재 할 수 없다. (한 행과 한 열에서는 퀸 한개만 존재 할 수 있습니다) 2. 대각선에서도 퀸은 두 개 이상 존재 할 수 없다. 1번 조건에는..
2023.08.24 -
[C++/BackTracking/백준] 15649번 N과 M (1)
https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net DFS를 이용한 백트래킹 문제입니다. 조건과 부합하면 화면에 출력하고 return하여 백트래킹 해줍니다. visited 배열로 중복사용되지 않게 처리해주고 return이 되면 다시 마지막에있는 숫자를 pop_back()과 vistied[i] = false로 미 방문 처리하여 다음 순열에서 사용가능하게 처리합니다. 전체소스코드 #include #include #include #include usi..
2023.08.22 -
[C++/Greedy/프로그래머스 Lv 3] 야근 지수
회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.제한 사항 works는 길이 1 이상, 20,000 이하인 배열입니다. works의 원소는 50000 이하인 자연수입니다. n은 1,000,000 이하인 자연수입니다. 입출력 예 worksnresult [4, 3, 3] 4 12 [2, 1, 2] 1 6 [1,1] 3 0 입출력 예 ..
2023.06.26 -
[C++/BFS/프로그래머스 Lv 3] 네트워크
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를..
2023.06.26