DOTY

9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 몇 주 전에 하려다가 머리가 안 굴러가서 포기했던 문제. #include using namespace std; int N; int answer; int check(int chess[15][15], int x, int y) { int tmp_X = x-1; int min = y-x; int sum = x+y; while(tmp_X >= 0) { if(min + tmp_X >= 0) { if(chess[tmp_X][min + tm..

1707번: 이분 그래프 (acmicpc.net) 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 뻘짓해서 좀 걸렸던 문제.. #include using namespace std; int check[20001]; int flag; // 0 : NO , 1 : YES vector graph(20001); // div : 1 or 2 void dfs(int vertex, int div) { if(flag == 0) { return; } int size = graph[vertex].size(); check[vert..

2665번: 미로만들기 (acmicpc.net) 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net #include using namespace std; int N; int x_p[4] = {0, 0, 1, -1}; int y_p[4] = {1, -1, 0, 0}; int room[50][50] = {0, }; int check[50][50] = {0, }; void bfs() { queue q; int x, y; q.push(make_pair(0, 0)); check[0][0] = 0; while(!q.empt..

1520번: 내리막 길 (acmicpc.net) 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 시간이 생각보다 좀 걸렸던 문제... DFS와 Memoization을 사용했던 문제인데 2년 전에 공부한 것을 다 까먹었다..ㅠㅠㅠ #include using namespace std; int x_p[4] = {0, 1, 0, -1}; int y_p[4] = {1, 0, -1, 0}; int road[500][500]; int memo[500][500]; int M, N; int dfs(int x, int y) { if..

12100번: 2048 (Easy) (acmicpc.net) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제는 Easy라고 적혀있지만 나는 Easy하지 않았던 문제... 머리가 안돌아가서 몇 시간 풀어봤지만 정답 보기에는 너무 아쉬워서 계속 시도한 문제... 내가 이겼다. 흐헤헤 #include using namespace std; int N; int max_no; void play(int board[][20], int cnt); // 1. 위로 void playUp(int b..

13023번: ABCDE (acmicpc.net) 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net #include using namespace std; int fri[2000]; int check[2000]; int answer; vector con; void backtracking(int people, int cnt) { if(cnt == 5) { answer = 1; return; } check[people] = 1; for(int i = 0; i < con[people].size(); i++) { if(check[con[people][i]] == 0) { backtracking(con[people][i], cn..

HEAP은 최대나 최솟값을 빠르게 찾게 해주는 알고리즘. 완전 이진 트리를 기반으로 만들어진 알고리즘이다. 최대 힙과 최소 힙이 있으며 최대 힙을 구현했다. 1. main int main(void) { fill_n(heap_arr, 100, 0); // 배열 초기화 heap_size = 0; int node; while(node != -1) { cout heap_arr[index*2+1]) { swap(heap_arr[index*2], heap_arr[index], index * 2); index *= 2; } else { swap(heap_arr[index*2 + 1], heap_arr[index], index * 2 + 1); index = index * 2 + 1; } } heap_arr[heap_..

코딩테스트 연습 - 두 큐 합 같게 만들기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 시간 초과 해결에 애쓴 문제 #include using namespace std; int solution(vector queue1, vector queue2) { int answer = -2; int cnt = 0; int q1 = 0; int q2 = 0; int queue_size = queue1.size(); long sum1 = 0; long sum2 = 0; for(int i = 0; i < queue..

코딩테스트 연습 - 성격 유형 검사하기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr #include using namespace std; string solution(vector survey, vector choices) { string answer = ""; map result; result.insert({"R", 0}); result.insert({"T", 0}); result.insert({"C", 0}); result.insert({"F", 0}); result.insert({"J", 0}..

코딩테스트 연습 - 기지국 설치 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제는 생각보다 간단했지만 특정 조건에서 조금 애먹었던 문제 #include #include using namespace std; int solution(int n, vector stations, int w) { int answer = 0; int between; for(int i = 0; i < stations.size()-1; i++) { if(stations[i] + w < stations[i+1] - w) { be..