본문 바로가기

알고리즘 문제/PS

Array Roate Clockwise/Anti-Clockwise /* * clockwise rotate * first reverse up to down, then swap the symmetry * 1 2 3 7 8 9 7 4 1 * 4 5 6 => 4 5 6 => 8 5 2 * 7 8 9 1 2 3 9 6 3 */ void rotate(vector &matrix) { reverse(matrix.begin(), matrix.end()); for (int i = 0; i < matrix.size(); ++i) { for (int j = i + 1; j < matrix[i].size(); ++j) swap(matrix[i][j], matrix[j][i]); } } /* * anticlockwise rotate * first reverse left to right, the.. 더보기
정올 1912 : 미로 탐색 문제: 정올 1912 풀이: - DFS 문제이다 - 다만, 가장 낮은 숫자의 방 부터 방문해야 하므로, 미리 인접 리스트를 정렬해 놓는다 (혹은 인접 리스트 대신에 힙을 써도 좋겠다. 즉, 힙을 원소로 가지는 벡터) - 본인의 경우 2차원 벡터를 선언하고, 노드 갯수(n)를 받자 마자 Resize를 수행해 주었는데 (왜냐하면 n을 받기 전에는 벡터를 n크기 만큼 초기화 할 수 없었으므로) 해당 방법은 실행 시간 169ms로 90점 밖에 받지 못하였고, 처음 부터 그래프 노드를 100001 만큼 늘리고 시작하니 실행시간 160ms로 통과되었다. 이상한 부분이다. #include #include #include using namespace std; int n, m; //vector v; vector v[10.. 더보기
BOJ 9019(DSLR) 풀이 - BFS 문제 D,S,L,R 명령어 별로 경우의 수를 나눠 큐에 담고 B를 만나면 break로 빠져 나오면 된다. 고찰 - '레지스터 결과'를 보고 '명령어'를 출력해야 하므로 struct Reg를 큐에 담도록 한다. - '명령어'는 string을 이용하면 '+' 오퍼레이터로 간단하게 구현이 가능하다. - visited[10000] 배열을 두어 시작점과, 중간 숫자 결과는 방문 처리 한다!! (그렇지 않으면, 시간초과 난다) #include #include #include using namespace std; int d(int a) { return (a * 2) % 10000; } int s(int a) { if (a == 0) a = 9999; else a -= 1; return a; } int.. 더보기
KMP 알고리즘(문자열 비교) "Is there a (longest) suffix which is also a prefix?" (접미사 중에서 접두사와 일치하는 가장 긴 것이 있는가?) ▶KMP 알고리즘 설명 - 문자열 검색 알고리즘, O(N + M). - N : 텍스트 길이, M : 패턴 길이 - 두 단계로 나뉜다. 1. KMP Substring(=pattern) Search, O(m) ABCDABCDABEE ABCDABE 를 비교하였을 때 매칭되지 않는 시점(C != E) 바로 직전의 접미사(suffix) 중에서 접두사(prefix)와 일치하는 가장 긴 길이는 얼마인가? ==> 정답 : 2 결과는 테이블 형태로 나타내는데 길이는 패턴 길이와 동일하다. 위의 예시에서 테이블은 [0 0 0 0 1 2] 이 된다. (코드) vector.. 더보기
BOJ2546(경비원) 풀이 - 거리 차이를 구하는 것이기 때문에, 한점을 기준으로 절대 거리를 구해서 빼주면 된다. from sys import stdin x,y = map(int, stdin.readline().split()) n = int(stdin.readline()) def dist_cal(idx, pos): if idx == 1: #북 return pos elif idx == 2: #남 return x + y + x - pos elif idx == 3: #서 return 2 * (x + y) - pos else : return x + pos pos = [] for _ in range(n + 1): idx, p = map(int, stdin.readline().split()) pos.append(dist_cal(idx.. 더보기
BOJ 9205(맥주 마시면서 걸어가기) 풀이(BFS) - 플로이드 와샬 혹은 BFS 문제이다. - 이웃한 점을 기준으로 서로간에 이동이 가능하면, 그래프를 정의해주는 것이 핵심이다. 즉, 아래와 같이 조건을 만족할 경우 그래프를 그려준다. point = [ list(map(int, input().split())) for _ in range(n + 2) ] edges = [[] for _ in range(N + 2)] #adjM = [[0] * (n + 2) for _ in range(n + 2)] for i in range(N + 2): for j in range(N + 2): if i == j: continue if abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) 더보기
BOJ 2578 코드 설명 빙고 판에서 3번 이상 줄이 그어지는 경우 "빙고"이며, 숫자를 없앤 카운트 수를 반환한다. 총평 단순 배열 문제라고 생각하였지만, '선이 세 개 이상 그어지는 순간 "빙고"라고 외친다' 조건 때문에 생각을 조금 더 해야 한다. #include #include using namespace std; int bingo[5][5]; int bin_total = 0; int check_row(int y, int x) { int bin = 1; for (int i = 0; i < 5; i++) { if (bingo[y][i] != -1) { bin = 0; break; } } return bin; } int check_col(int y, int x) { int bin = 1; for (int i = 0.. 더보기
BOJ 3055 시뮬레이터 문제이다. 어디서 참고한 코드 같지만, 출처는 기억이 나지 않는다. 문제를 풀기 위하여 bfs()를 한번만 돌릴 수도 있지만, 시뮬레이터 재현을 위해 '물'과 '고슴도치'의 이동을 한번씩 하게 하였다. 여기서 핵심은 moveWater(), moveHedge() 함수의 while(qsize--) 이렇게 하면, 시간 순서상으로 한번씩 Stage 각각 넘어갈 수 있게 된다. bfs 혹은 큐를 이용한 문제에서 사용할 수 있는 좋은 테크닉이라 기록에 남긴다. #include #include using namespace std; int r, c; const int HEDGE = 0; const int WATER = 1; char Map[50][50]; bool visit[50][50][2]; // 상하좌.. 더보기

티스토리툴바