분류 전체보기151 백준 1260 DFS와 BFS DFS와 BFS를 구현하는 문제이다. DFS의 경우 DFS(깊이우선탐색)은 자기자신을 호출하는 순환알고리즘의 형태를 갖는다. 재귀를 이용해서 구현!! 1번 노드에 인접한 모든 노드들에 대해서 간선이 있고, 방문하지 않았던 지점이라면 방문한다. 같은 방식으로 n개의 노드에 대해서 진행. BFS의 경우 BFS(너비우선탐색)은 재귀적으로 동작하지 않는다. 일반적으로 큐를 사용해서 반복적으로 구현한다. Prim, Dijkstra알고리즘과 유사하다. 큐를 이용해서 구현!!(FIFO방식) 1번노드에 인접한 모든 노드들에 대해서 간선이 있고 방문하지 않았던 지점이라면 방문하여 큐에 넣는다. 큐가 empty가 될 때까지 반복해서 진행. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17.. 2022. 2. 3. [백준] 11000 강의실 배정 c++ 문제 링크 https://www.acmicpc.net/problem/11000 풀이 방법 먼저 시작하는 회의 순으로 정렬한다. 회의가 끝나는 시간을 저장하는 우선순위 큐(pq)를 하나 만든 후, 맨 앞의 회의가 끝나는 시간을 저장한다. 지금 회의가 pq의 top이후에 시작한다면(같은 회의실을 사용할 수 있다면) pq의 top을 꺼내고, 지금 회의의 끝나는 시간을 pq에 push한다. 그게 아니라면(다른 회의실을 사용해야 한다면) 회의가 끝나는 시간을 pq에 push한다. 모든 회의를 순회했을 때 결국 pq의 size가 회의실 갯수가 될것이다. 구현은 어렵지 않았으나 풀이 방법이 생각이 안나서 굉장히 까다로웠던 문제였다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 .. 2022. 2. 2. 백준 1343 폴리오미노 효율적인 방법이라고 생각이 들진 않지만 다른 풀이와 비교했을 떄 시간복잡도가 괜찮은것같아서 풀이를 수정하지 않았다. 풀이방법 "XX"가 나오면 "BB"로 교체한다. "."가 나오면 result 값을 지우고 continue한다. 이렇게 완성된 문자열은 예를들어서 BBX.BB 이런 형태를 띌것이다. 이 완성된 문자열을 가지고 "BBBB"가 나오면 "AAAA"로 교체한다. "."가 나오면 result2값을 지우고 continue한다. 완성된 문자열에서 X가 하나라도 있다면 A,B로 만들수 없다는 뜻이므로 -1출력. Key point 핵심이랄 것 까지는 없는 것같고 문자열처리를 잘 해야했다. string의 replace, find함수를 사용할 수 있는 문제다. 2022. 2. 1. 백준 2437 저울 문제를 처음봤을 때 너무 꼬아서 접근을 했던 것 같다. max가될 수 있는 추 무게부터 min의 추 무게까지 그 사이값들 하나하나 맞춰지나 판별하고 있었다.. 정답은 나왔지만 결과는 당연히 시간초과. 방황했던 흔적은 아래와 같다. 다른 방법이 있겠지하고 검색한 결과 너무 간단해서 놀랐다. 누적합이라는 개념을 이해하고 있으면 쉽게 풀 수 있었던 문제인데, 누적합에 대해선 다음 사이트를 참고해서 이해했다. https://novlog.tistory.com/9 [C/C++] BOJ(백준) 2437 "저울" 문제 풀이 #문제정보 출처 : www.acmicpc.net/problem/2437 #문제분석 사용된 알고리즘 : 그리디(GREEDY), 누적합 문제풀이의 핵심은 측정 가능한 부분이 끊기지 않아야 한다는 것이다.. 2022. 2. 1. 백준 1543 문서검색 #1번째방법 Key point 첫번째 방법은 이중for문 돌려서 문자하나씩 비교해가면서 flag로 접근했다. substring 조각이 맞춰졌다면 그 인덱스만큼 더해주는 것이 키포인트가 될거같고 앞에 substring길이가 더 큰경우에 대해서 예외처리를 안해주면 런타임에러가 발생한다. #2번째방법 string의 substr함수를 사용하는 방법도 있던데 이걸로도 풀어봤다. 인자는 첫번째 문자위치(pos), 부분문자열의 길이(count) 두가지이고 리턴값은 [pos, pos+count]까지의 문자열을 반환한다. 만일 pos가 원래문자열길이보다 길다면 out of range 예외발생하니 주의해야한다. 쉽게말해서 substr는 그냥 인덱스와 길이를 적어넣으면 부분문자열 추출해주는건데 이문제에 적용하면 쉽게 풀수 .. 2022. 1. 31. 백준 1049 기타줄 여러가지 대리점 가격이 나오는데, 세트가 가장 싼 지점과 낱개가 가장 싼 지점 두가지만 생각하면 되는 문제였다. Key point 최소가 될 수 있는 총 3가지를 고려해야됨. 1)세트하고 나머지 낱개 2)낱개로 만땅 3)세트로 만땅 어려운 점 낱개로 만땅인 경우를 생각하지 못했다.. 그래서 정답률 34프로인가 2022. 1. 30. 이전 1 ··· 21 22 23 24 25 26 다음
