분류 전체보기 (61) 썸네일형 리스트형 [프로그래머스] 카카오 프렌즈 컬러링북 (2017 카카오코드 예선) 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1829 단순 bfs문제이다. 1. 이차원 배열을 하나씩 순차 탐색한다. 2. 순차 탐색할 때 방문하지 않았고 색칠되어 있는 장소마다 bfs를 돌려준다. 3. bfs를 돌릴 때 queue에 들어간 개수를 카운팅해 영역의 크기를 max_area와 비교해 나간다. 3. bfs돌린 횟수가 결국 색칠한 영역의 개수이고 max_area(코드에서는maxx)가 제일 큰 영역의 크기이다. 1. 원소가 0인 부분은 색칠이 되어 있지 않은 부분이다. 색칠 되어 있지 않은 부분은 영역으로 치지 않는다. #include #include #include #include using namespace std; bool chec.. 백준 9012번: 괄호 (C++) 문제 링크 : https://www.acmicpc.net/problem/9012 간단한 stack문제다. 열린 괄호면 stack에 넣고 닫힌 괄호면 미리넣었던 열린괄호를 빼버린다.(쌍을 하나씩 제거하는 방식) 쌍이 서로 다 맞아서 모두 삭제가 되면 vps이다. - 닫힌 괄호가 나왔는데 스택이 비어있으면 vps가 아니다. (닫힌 괄호의 쌍이 없음.) - 닫힌 괄호가 나왔는데 스택 top이 열린 괄호가 아니라면 vps가 아니다. (마찬가지) - 쌍들을 모두 삭제 해주었는데 스택에 남아있는 괄호가 있다면 역시 vps가 아니다. #include #include #include using namespace std; bool is_vps(string str) { stack s; for (int i = 0; i < .. 1. Application Layer(어플리케이션 계층) - http 통신은 단방향 연결 , socket 통신은 연결을 지속하는 양방향 연결 Socket : 네트워크에 연결된 장치간의 프로세스끼리 데이터를 송수신 할 수 있게 우체통 역할을 한다. (OS에서 제공하는 인터페이스, system call) -tcp 전용 소켓, udp 전용 소켓이 있음. 1. socket() -> 소켓을 연다, udp 혹은 tcp 선택. 2. bind() -> (주소와 )포트번호를 할당. 3. listen() -> 서버 전용 명시 4. accept() -> 외부로 부터의 메시지를 기다림. 5. read() , write() -> 데이터를 읽거나 씀. 1. socket() 2. connect() -> 상대방의 소켓과 연결,(상대방 ip주소와 port number를 매개변수로) 3. r.. (시작 전에) 네트워크 기본 - 출발지부터 목적지 까지 전용회선을 예약해서 데이터를 보냄 (전용회선으로 데이터 송수신)(ex -전화) - 전용회선 역할이라 다른 사용자가 동시에 사용할 수 없음. -packet이라는 데이터로 쪼개서 데이터를 보냄. -한 선을 여러사용자가 이용할 수 있음. processing delay - 라우터가 패킷을 분류하는 시간 -> 라우터 성능 향상을 통해 개선 가능 queuing delay - 먼저 도착한 패킷들이 빠질 때까지를 기다리는 시간 -> 군중심리에 따라 변해서 개선 힘듦 transmission delay - 데이터가 처음부터 마지막 비트까지 뿜어져 나가기까지 걸리는 시간 -> bandwidth를 늘려 개선 propagation delay - 데이터가 선을 지나가는 데 걸리는 시간(한 라우터에서 다.. DFS (Depth First Search)(깊이 우선 탐색) DFS란 다음 분기로 넘어가기전에 해당 분기를 모두 탐색하는 탐색 방법입니다. 즉 임의의 노드에서 갈수있는 만큼 깊게 들어간 후 더 이상 진행할 수 없으면 그전으로 다시 돌아가 탐색을 시작합니다. 1을 시작으로 DFS 탐색을 한다면 1-2-3-6-7-4-5 이런 식으로 탐색이 진행됩니다. (인접해있는 노드 중 작은 노드부터 탐색한다고 가정했을 때) 물론 정확한 탐색순서는 저장되어있는 노드 순서에 따라 다르지만, 중요한 것은 하나의 노드로부터 가장 깊게까지 탐색을 하고 막히게 되면 그전으로 돌아가 다시 탐색을 진행한다는 것입니다. BFS는 큐를 사용하지만 DFS는 스택을 사용하여 쉽게 구현할 수 있습니다. 하지만 굳이 스택 STL을 이용하지 않고 재귀함수를 이용하면 편합니다. (재귀함수 자체가 스택처럼 저.. BFS (Breath First Search)(너비 우선 탐색) BFS란 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법입니다. 즉 끝까지 깊게 먼저 탐색하는 dfs랑 대비됩니다. 1을 시작으로 bfs탐색을 한다면 (1)->(2->3)->(4->5->6->7) 이런 식으로 탐색을 합니다. 괄호를 친부분은 같은 거리를 표시한 것 입니다. 즉 괄호 안에서의 탐색 순서는 큐에 넣은 순서에 따라 달라지기 때문에 코드에 따라 달라질 수 있습니다. 그래프는 vector를 이용하면 쉽게 표현 할 수 있습니다. 위의 그래프는 아래와 같이 표현됩니다. a[1].push_back(2); //노드 1에서 노드 2로 연결 a[1].push_back(3); a[2].push_back(1); a[2].push_back(3); a[2].push_back(4); a[2].push_back(5).. 백준 16236번: 아기 상어 (C++) 문제 링크 : https://www.acmicpc.net/problem/16236 bfs문제입니다. bfs로 먹을 수 있는 먹이를 계속 찾습니다. bfs가 끝날때 마다 먹이를 찾는데 걸리는 시간을 계속 더해줍니다. 만약 먹을 수 있는 먹이가 더이상 없다면 종료시켜줍니다. - 최단 거리의 먹이들 중 가장 위쪽에서 왼쪽인 먹이를 찾기위해 일단 최단 거리의 먹이를 전부 저장해야함 -> 처음 먹이를 찾을때의 거리(최단 거리)를 저장한 후 거리가 더 커지기 전까지의 먹이를 전부 저장한다. (bfs는 가까운 것부터 탐색하므로 거리가 같은 부분끼리 뭉쳐서 queue에 저장된다.) - 상어 정보를 저장하는 class (저장해야 하는 속성이 3개 이상이라 class를 정의함) - 같은 거리의 먹이들을 임시저장하기위한 v.. 백준 16235번: 나무 재테크 (C++) 문제 링크 : https://www.acmicpc.net/problem/16235 단순 구현 문제입니다. 1. map 이차원 배열을 vector 데이터 타입으로 선언해 공간마다 벡터를 갖게 합니다. 2. 봄과 여름을 동시에 처리합니다. sorting 된 벡터에서 나이가 낮은 나무부터 양분을 주며 나이를 증가시킵니다. 양분이 부족하면 그 후부터의 나무들을 모두 죽이며 양분으로 만듭니다. 3. 가을에 map 이차원 배열을 탐색하며 5배수의 나무가 있으면 주변에 모두 나이 1 나무를 번식시킵니다. 4. 겨울에 다시 양분을 합해줍니다. 5. k번이 지나면 남은 나무의 개수를 구해줍니다. #include #include #include using namespace std; int n, m, k; int feed_.. [프로그래머스] 문자열 압축 (2020 KAKAO BLIND RECRUITMENT) 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60057 문자열 절단 단위를 1,2,3 ..... 증가시켜가며 각각 문자열 길이가 최소인 경우를 찾는다. 1. 원래 문자열을 자를 문자열 절단 단위를 1부터 반절까지 증가시키며 자른다. 2. 문자열 절단 단위(i)가 하나 정해지면 처음붙터 문자열 단위 씩 자르면서 전 문자열과 비교한다. 2-1 전 문자열과 현재 문자열이 같다면 total_size에서 문자열 절단 단위(i)만큼 뺀다. 2-2 전 문자열과 현재 문자열이 다르다면 증가시켜온 same_count 정수의 자릿수만큼 total_size에 더한다. 3. 문자열 절단 단위마다 문자열 길이가 최소인 값을 찾는다. #include #include #.. 백준 16234번: 인구 이동 (C++) 문제 링크 : https://www.acmicpc.net/problem/16234 단순한 bfs 문제였습니다. 1. 한 좌표에서 bfs로 이차원 배열을 탐색합니다. 탐색 되지 않은 좌표들은 다시 bfs를 돌려줍니다. (다음 노드가 L 이상 R 이하인 부분만 탐색하는 bfs.) 2. 한 좌표에서 bfs를 돌려 탐색 된 부분들은 한 연합입니다. 연합나라들의 수를 분배합니다.(bfs를 돌릴 때 vector에 각 좌표를 저장해두면 쉽게 수를 분배할 수 있습니다. 3. 한 연합 안에서 사람 수들이 모두 같지 않으면 결국 이동을 해야 합니다. 4. 이동할 필요가 없으면 종료해줍니다. #include #include #include using namespace std; int n, L, R; int people[52.. 이전 1 ··· 3 4 5 6 7 다음
