SW/Algorithm
-
[SW expert] 1907 모래성 쌓기 삼성 알고르즘 문제SW/Algorithm 2020. 2. 6. 10:15
1907. 모래성 쌓기 문제 링크 풀이 들어가기전1000*1000 = n^2 이니깐 완전 탐색은 불가!!! 1초당 반복문 수행 횟수가 10^8(1억)을 넘으면 시간 초과 가능성.O(n^3) : 대략 크기가 2560인 입력까지 1초O(n^2) : 40960인 입력 까지 1초O(NlogN) : 20000000인 입력 까지 1초O(n) : 160000000인 입력 까지 1초2017/12/30 - [SW/Algorithm] - [알고리즘] Begin Algorithm[알고리즘] Begin Algorithm문제 해결 과정 문제를 읽고 이해하기 재정의와 추상화 계획 세우기 계획 검증 계획 수행 회고하기 (코드와 함께 자신의 경험을 기록 & 오답 원인 & 다른사람코드확인) 간결한 코드 작성하기 #define FOR(..
-
[BOJ] 7562.나이트 이동(BFS)SW/Algorithm 2018. 7. 9. 20:49
깃허브 코드보기 /**************************************************************** 날짜: 2018/07/09 작성자: 임중현 문제: 백준 7562.나이트의 이동 풀이: 방향(8방향)을 설정하고 bfs로 한줄씩 찾아가면서 처음으로 찾는것이 최소로 움직이는 횟수 노드의 뎁스를 알아야 함으로 DFS가 아닌 BFS로 풀면 된다. *****************************************************************/ #include using namespace std; int dx[]={-1,-2,-2,-1,1,2,2,1}; int dy[]={-2,-1,1,2,-2,-1,1,2}; struct Position{ int x,y; P..
-
[BOJ] 2902.kmp는 왜 kmp일까? (string)SW/Algorithm 2018. 7. 2. 21:01
깃허브 코드보기 /**************************************************************** 날짜: 2018/07/02 작성자: 임중현 문제: BOJ 2902.kmp는 왜 kmp일까? 풀이: 첫번째 문자 + 하이픈 뒤글자들만 저장시켜 출력한다. *****************************************************************/ #include using namespace std; int main() { string input,output=""; cin>>input; output+=input[0]; for(int i=1;i
-
[BOJ] 7513.준살 프로그래밍 대회(맵)SW/Algorithm 2018. 6. 11. 15:16
깃허브 코드보기 /****************************************************************날짜: 2018-06-08작성자: 임중현문제: 백준 7513.준살 프로그래밍 대회 풀이: 들어온 단어를순서대로 맵에 매핑하고 숫자(마지막에들어오는)대로 뽑음 *****************************************************************/ #includeusing namespace std; int main(){int t;cin>>t;for(int tc=1; tc>m;map mapping;string input; for(int i=0;i>input;mapping.insert(make_pair(i,input));}cin>>n;string s..
-
[BOJ] 10799.쇠막대기(스택)SW/Algorithm 2018. 6. 5. 11:23
깃허브 코드보기 /**************************************************************** 날짜 : 2018/06/04 Mon 작성자: 임중현 문제 : 백준 10799.쇠막대기 (https://www.acmicpc.net/problem/10799) 풀이 : '()' 이것이 나오면 그전에 '(' 개수 만큼 잘린게 나온다. '))' 이렇게 연속으로 나오면 1개가 더 추가되서 나오는 것을 예시를 통해 알 수 있다. 문제점: 메모리초과 -> *****************************************************************/#include#include#includeusing namespace std; long long ans; /*/..
-
[알고리즘] 다익스트라 알고리즘 (최단거리)SW/Algorithm 2018. 1. 17. 20:00
다익스트라 알고리즘 (Dijkstra Algorithm) 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다. O(v^2)의 복잡도 이지만 우선순위큐를 사용함으로 O(Elogv)의 시간 복잡도를 가지게 된다. E는 간선 v는 노드 // E => 최악의 경우 E번의 탐색한 노드를 집어 넣는 경우가 발생한다. 시작점에서 연결되있지 않은 노드도 무한대 크기만큼 연결되어있다가정하고 알고리즘을 수행한다. E[][] 는 간선들의 크기를 나타낸다.(그래프) D[]는 시작점에서 모든 정점을 가는 최소값을 가지게 된다. q는 시작점에서 q에 있는 정점들을 방분한다. D[v]=min(D[v],D[select_v]+E[select_v][v]) 풀이 시작점 하나를 잡는다. q에 시..
-
[알고리즘] BacktrackingSW/Algorithm 2018. 1. 6. 21:00
Backtracking 미로찾기 막다른 골목이면 이제까지 온 길을 돌아오게 된다. (백트레킹 -> 스택 & 재귀?) right hand / left hand -> 오른손(왼손)으로 벽을 짚고 간다.(출구가 중간에 있으면 안될 경우도 생김) N-Queen NxN 크기의 체스판에서 퀸을 같은 행, 같은 열, 같은 대각선 위에 놓지 않을 수를 구하기. 문제 해법 4개의 퀸을 모두 다른 행에 놓으면서 해가 되는 퀸의 열의 위치가 어디인지 계산 Candidate 해 모두 다른 행에 대한, 가능한 모든 열의 조합 [(1,1),(2,1),(3,1),(4,1)], ..... , [(1,4),(2,4),(3,4),(4,4)] => 4-퀸 = 4 4 4 * 4 해의 개수 (n^n) State-Space Tree : 모든 ..