분류 전체보기 (61) 썸네일형 리스트형 백준 15649번: N과 M (1) (Kotlin 코틀린) 문제 링크 : www.acmicpc.net/problem/15649 단순 백트래킹 문제이다. 1. Dfs를 이용해 모든 수열을 탐색한다 (단 이미 방문한 숫자가 나오는 경우는 제외 - 백트래킹) 2. m개의 숫자가 완성되어 수열이 완성되면 숫자를 출력한다. (숫자를 탐색할 때 오름차순으로 탐색하니 자동으로 사전 순으로 출력된다.) import java.io.* import java.util.* val br = BufferedReader(InputStreamReader(System.`in`)) val bw = BufferedWriter(OutputStreamWriter(System.out)) var n = 0 var m = 0 val check = BooleanArray(10, { false }) fun .. git 기본 명령어 commit : 디렉토리에 있는 모든 파일에 대한 스냅샷을 기록하는 것, -> 각 커밋은 변경 내역을 기록함 git commit : 새로운 커밋을 생성(저장) git branch noah : noah라는 브랜치를 해당 커밋에서 생성 (브랜치는 특정 커밋에 대한 참조에 지나지 않기에 가벼움) git checkout noah : noah브랜치로 이동. git merge noah : noah브랜치의 커밋내용을 합쳐서 생성 (해당 브랜치만 merge한 곳으로 이동) - noah가 해당브랜치의 자식이면 noah로 이동만함 git rebase noah : 분기한 이후의 커밋들을 모아서 복사한 뒤 noah 뒤로 이어 붙임 (커밋트리의 히스토리를 수정하게됨) merge vs rebase -> merge는 히스토리 이력.. 백준 9663번: N-Queen (C++) 문제 링크 : www.acmicpc.net/problem/9663 단순 백트래킹 문제다. 그냥 무작정 다 배치한 다음 확인을 하면 n^n이라는 어마어마한 시간복잡도가 나오게 된다. 결국 백트래킹을 사용해야한다. 1. 한 줄씩 queen을 놓아본다. 2. queen을 놓을 수 없는 상황이오면 바로 돌아간다.(백트래킹) #include #include using namespace std; vector queen; int n; int result = 0; bool can_exist(int x,int y) //해당 위체에 queen놓을 수 있는지 { for (int i = 0; i < queen.size(); i++) { int x2 = queen[i].first; int y2 = queen[i].second;.. 백준 1753번: 최단경로 (C++) 문제 링크 : www.acmicpc.net/problem/1753 단순한 다익스트라 알고리즘 문제다. 내 블로그에 다익스트라 알고리즘에 대해 다 설명해 놓았다. 다익스트라 알고리즘 : wlshddlek.tistory.com/36?category=887632 #include #include #include using namespace std; vector a[20002]; int d[20002]; int INF = 987654321; void dijkstra(int start) { fill(&d[0], &d[20001], INF); priority_queue q; q.push(make_pair(0,start)); d[start] = 0; while (!q.empty()) { int node = q.top(.. 백준 1717번: 집합의 표현 (C++) 문제 링크 : www.acmicpc.net/problem/1717 응용없는 단순한 유니온 파인드(disjoint set)알고리즘이다. 1-1. type이 0이면 두 노드들의 root를 합친다. -> d배열에 각 노드들의 부모를 가리키도록 저장한다.(재귀로 끝까지 가보면 root가 나오게 됨) 1-2. type이 1이면 두 노드의 집합 여부를 출력한다. (root노드가 같으면 결국 같은 집합임) #include using namespace std; int d[1000002]; int find_root(int a) //해당 집합의 root 찾아서 반환 { if (d[a] == a)return a; return find_root(d[a]); } void make_union(int a, int b) //두 집합.. 백준 14891번: 톱니바퀴 (C++) 문제 링크 : www.acmicpc.net/problem/14891 특별한 알고리즘이 없는 단순 구현, 시뮬레이션 문제이다. 자세한 설명은 코드 주석으로 달아놨다. 1. 해당 톱니를 움직인다. 2. 왼쪽 톱니들을 확인하며 움직일 톱니들을 움직인다. 3. 오른쪽 톱니들을 확인하며 움직일 톱니들을 움직인다. 4. 점수들은 계산해준다. #include #include #include using namespace std; deque wheel[4]; void move_wheel(int id, int dir) //id톱니 dir방향으로 움직이기 { if (dir == -1) //반시계방향 { wheel[id].push_back(wheel[id][0]); wheel[id].pop_front(); } else //시.. 백준 1167번: 트리의 지름 (C++) 문제 링크 : www.acmicpc.net/problem/1167 tip) 임의의 한 점에서 제일 먼 점은 반드시 지름의 양 끝 점 중에 하나라는 사실만 생각해내면 된다. 1. 임의의 한 점에서 제일 먼 점을 찾는다. (지름의 끝 점 중 하나를 찾는다) 2. 그 점으로 부터 제일 먼 점까지의 거리를 구한다 -> 제일 먼 점을 찾는건 bfs 나 dfs로 구한다. #include #include #include #include using namespace std; vector a[100002]; bool check[100002]; int max_cost = 0; int result = 0; int find_corner(int start) { queue q; q.push(make_pair(start, 0));.. 백준 12865번: 평범한 배낭 (C++) 문제 링크 : www.acmicpc.net/problem/12865 다이나믹 프로그래밍 문제이다. (knapsack 문제) 1. 특정 아이템을 넣을지 말지의 경우를 모두 저장하며 구해나간다. - 아이템 마다 결정할 때 가방의 무게가 w ~ k일 때의 모든 경우를 저장하여야 한다. (w미만은 어차피 넣을 수 없으니 고려할 필요가 없음) 2. 마지막 아이템까지 다이나믹 프로그래밍을 진행하면 결국 가방 무게가 k일때의 d[k]값이 정답이다. - knapsack문제를 2차원 배열에 저장하며 계산한다면 좀 더 이해하기 직관적일 것이다. 하지만 메모리를 아끼기 위해 1차원 배열로 알고리즘을 구현하였다. - 1차원 배열을 이용한다면 배열을 계속 갱신할 때 뒤에서 부터 갱신하여야 한다. 뒤에서 부터 갱신하여야 그 전의.. 프로그래머스 SQL 문제 (MySQL) - 2 문제 링크 : programmers.co.kr/learn/courses/30/lessons/59039 -> SELECT ANIMAL_ID FROM ANIMAL_INS WHERE NAME IS NULL ORDER BY ANIMAL_ID 문제 링크 : programmers.co.kr/learn/courses/30/lessons/59407 -> SELECT ANIMAL_ID FROM ANIMAL_INS WHERE NAME IS NOT NULL ORDER BY ANIMAL_ID 문제 링크 : programmers.co.kr/learn/courses/30/lessons/59410 -> SELECT ANIMAL_TYPE, IFNULL(NAME,"No name"), SEX_UPON_INTAKE FROM ANIMAL_.. 프로그래머스 SQL 문제 (MySQL) - 1 문제 링크 : programmers.co.kr/learn/courses/30/lessons/59034 -> SELECT * FROM animal_ins ORDER BY animal_id 문제 링크 : programmers.co.kr/learn/courses/30/lessons/59035 -> SELECT name, datetime FROM animal_ins ORDER BY animal_id DESC 문제 링크 : programmers.co.kr/learn/courses/30/lessons/59036 -> SELECT animal_id, name FROM animal_ins WHERE intake_condition = "Sick" ORDER BY animal_id 문제 링크 : programmers.co.. 이전 1 2 3 4 ··· 7 다음