xxheexx

#include using namespace std; pair start; int board[52][52]; vector solution(vector park, vector routes) { vector answer; int re[2]; for(int j=0;j=park.size()||nxt.first=park[0].length()||nxt.second

#include using namespace std; int A,B; int bfs(int start){ queue q; q.push(pair(start, 1)); while(!q.empty()){ pair x = q.front(); q.pop(); //cout

#include #define MAX 101 using namespace std; int cnt; vector graph[MAX]; void bfs(int v1, int v2){ queue q; vector visited(MAX); q.push(v1); visited[v1] = true; visited[v2] = true; while (!q.empty()) { int node = q.front(); q.pop(); for (int i=0; i

연결 리스트 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조, 원소들은 이곳 저곳에 흩어져 있음 성질 k번째 원소를 확인/변경하기 위해 O(k) 필요 임의의 위치에 원소를 추가/제거는 O(1) 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당 다소 쉬움 연결 리스트의 종류 단일 - 각 원소가 자신의 다음 원소의 주소 이중 - 각 원소가 자신의 이전 원소와 다음 원소의 주소 list 원형 - 끝과 처음 연결 배열 vs 연결리스트 list #include using namespace std; int main(void) { list L = {1,2}; // 1 2 list::iterator t = L.begin(); // t는 1을 가리키는 중..

정의와 성질 배열 - 메모리 상에 원소를 연속하게 배치한 자료구조 성질 O(1)에 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 Cache hit rate가 높음 메모리 상에 연속한 구간을 잡아야해서 할당에 제약 임의의 위치에 원소 추가, 제거 - O(N) 사용팁 fill(arr, arr+arr.size(), 0); //0으로 채워줌 STL vector 배열과 거의 동일한 기능, 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있음 #include using namespace std; int main(void) { vector v1(3, 5); // {5,5,5}; cout

#include using namespace std; vector solution(vector id_list, vector report, int k) { vector answer; map reportList; map reportUser; set temp; for(string id : id_list){ reportList.insert(pair(id, temp)); reportUser.insert(pair(id, 0)); } for(string s: report){ stringstream ss(s); string x, y; ss >> x >>y; set name = reportList.at(x); name.insert(y); reportList.erase(x); reportList.insert(pair(x,..

DFS (Depth First Search) 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 1. 시작하는 칸을 스택에 넣고 방문했다는 표시 남김 2. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번 진행 3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 4. 스택이 빌 때 까지 2번 반복 칸이 N개일 때 시간복잡도 : O(N) - 모든 칸이 스택에 1번씩 들어가므로 (0,0) pop (1,0) pop --- 반복 --- #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 ..

공백문자가 연속으로 나올 수 있고 맨 앞이나 뒤에도 나올 수 있기 때문에 처음에 그냥 split 메서드 이용해서 푸니까 런타임 에러 발생 StringTokenizer 이용 String s= "this-is-sentence"; StringTokenizer st = new StringTokenizer(s, "-", true); while(st.hasMoreTokens()){ System.out.println(st.nextToken()); } /*** this - is - sentence ***/ import java.io.*; import java.util.*; class Solution { public String solution(String s) { String answer = ""; //String s..

시간복잡도, 공간복잡도 시간복잡도 - 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계 제한 시간 1초 -> 프로그램이 3-5억번의 연산 안에 답을 내고 종료 빅오표기법 - 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법 공간복잡도 - 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계 512MB = 1.2억개의 int 실수 자료형 1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다. 2. double에 long long 범위의 정수를 함부로 담으면 안된다. 3. 실수를 비교할 때는 등호를 사용하면 안된다. (둘의 차이가 아주 작다는 의미로 1e-12 사용 권장) int main(void){ double a = 0.1+0.1+0.1; double b = 0.3; if(a..

import java.awt.*; import java.util.*; import java.io.*; public class Main { static int N; static int S; static ArrayList list = new ArrayList(); static int[] re; static int[] arr; static boolean[] vi; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = I..