전체 글 (118) 썸네일형 리스트형 다익스트라(Dijkstra) 알고리즘 간단 정리 1. 필요한 변수, 배열 1) 노드간 관계도 map 2) 각 노드로의 최단거리를 저장할 배열 : result[] 3) 알고리즘용 queue( priority_queue 가 아니여도 되네....?) -> 아마 동작 시간을 고려해서 pq를 쓰는거 같긴한데... 애매하네 4) 최종 결과 : result[목적지 노드] 2. 기본 동작 코드 : 무조건 queue로만, 배열을 사용하면서 할 필요성이 0 1) 각 노드의 최단거리를 MAX로 초기화 시켜놓기 2) 시작지를 queue에 넣음으로써 루프 시작, BFS랑 유사 3) for문으로 나랑 연결되어 있는 노드들의 최단거리를 모두 업데이트 -> 기존의 그 노드로 가는 최단길이 vs 지금 내 위치를 거쳐서 그 노드로 가는 길이를 비교하여, 최솟값으로 초기화 4) 위에 .. 프로그래머스 : [1차] 뉴스 클러스터링 c++ https://programmers.co.kr/learn/courses/30/lessons/17677?language=cpp# 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 풀이는 나중에... #include #include #include using namespace std; vector v1,v2; int solution(string str1, string str2) { int answer = 0; //일단 만약 대문자면 다 소문자로 바꾸고 시작하자 for(int i=0;i 백준 18500 : 미네랄 2 c++ https://www.acmicpc.net/problem/18500 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 빡구현 감 안잃기 포인트 1. 떨어져야할 클러스터 지정 다 한 다음에는, 최소 수직거리 구해서 통으로 내리기 #include #include #include #include #include #include using namespace std; int d_r[4] = { 1,-1,0,0 }; int d_c[4] = { 0,0,1,-1 }; int r, c; int n; char map[101][101]; .. 백준 1765 : 닭싸움 팀 정하기 C++ https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 풀이 1. 처음 입력을 받을때 그래프 연결하듯이 입력받는다. 2. visited를 관리하는데, 여기서 visited란 방문했다라는 표현보다는, 특정 팀에 속해있다로 이해하는게 맞다 -> 따라서 처음 루프를 확인할때 visited가 1이면 answer를 올리지 않는다. 이미 팀에 속해있고, 이 팀에 추가 멤버를 영입하는 과정이기 때문 3. 루프 1) visited가 1이면 answer는 올리지 않음 2) 내 친구면 우리팀으로 영입 -> 이미 영입 되어있어도 answer에 .. 백준 11967 : 불켜기 C++ https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 세상 비효율적으로 푼거같지만, 한방에 바로 통과해서 기분좋아서 오랫만에 풀이 정리 풀이 1. 일단 기본 map과 visited를 별개로 관리 -> 왜냐하면 visited는 불켜짐과는 상관없이 bfs에만 사용하는 용 2. map을 새로운 struct로 관리 -> 각 방에서 킬 수 있는 스위치들 vector로 관리 -> 지금 불 켜짐 여부 ( 한번.. . Just imagine what task was given by heaven before you were sent to earth c++ StringStream 사용법 생각보다 심플하고, 아주아주 유용할거같다 기능 : 띄어쓰기, \n 줄바꿈 이 두개를 구분하게 해주는 아주 유용한 함수~~ 1) 해더에는 sstream 2) 필요한 인풋들 - 나누고 싶은 string - 나눠진걸 결과에 담을 string 배열 - 옮겨담기용 string 하나, int index 하나 #include #include #include using namespace std; int main() { string a = " gfd qwe asdd sdf sdf"; stringstream ss(a); string result[5]; string token; int index = 0; while (ss >> token) result[index++] = token; for (int i = 0; i < 5;.. 백준 6198 : 옥상 정원 c++ (monotone stack) https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net monotone stack이란? -> 스택 내부를 오름차순 또는 내림차순으로 유지 해주는 알고리즘 https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/ monotone stack monotone stack은 몇몇 문제들의 시간 복잡도를 O(n)정도로 줄어주는 강력한 테크닉입니다. justicehui.github.io.. 이전 1 2 3 4 ··· 15 다음
