본문 바로가기

algorithm14

백준 1238 파티 1. 문제 링크 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 2. 풀이 N명의 사람(노드) / M개의 경로(단방향) 그래프와 X(노드 번호)가 주어졌을 때, [모든 사람 -> X]의 최단거리 [X -> 모든 사람]의 최단거리 를 구하는 것이 핵심인 문제이다. [X -> 모든 사람]의 최단 거리의 경우 X를 출발점으로 하는 다익스트라 알고리즘을 쉽게 떠올렸다. 하지만 반대의 경우 출발 지점이 모든 사람이기 때문에.. 2021. 10. 2.
백준 1043 거짓말 1. 문제 링크 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 2. 풀이 문제의 핵심은 진실을 알고 있는 사람이 참석한 파티를 모두 제거하는 것 파티에 대한 참석자 배열과 참석자에 대한 파티 배열 2개를 만든 후 BFS방식을 통해 진실을 알고 있는 사람이 참석한 모든 파티를 제거할 수 있다. 간단한 알고리즘은 아래와 같다. 최초에 진실을 알고있는 사람을 모두 queue에 push qeueue가 비워질 때까지 queue에서 원소 하나 pop(진실을 알고 .. 2021. 10. 2.
2021 카카오 채용연계형 인턴십표 편집 1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 0 ~ n-1까지의 n개의 원소를 가진 표에 대해 편집을 하는 문제이다. 편집 명령어는 아래와 같다. "U X" : 위로 X만큼 이동 "D X" : 아래로 X만큼 이동 "C" : 지금 있는 위치의 원소 삭제 "Z" : 가장 최근에 삭제했던 원소 복원 처음 접근했던 방식은, 아래와 같았다. 길이 n.. 2021. 9. 30.
2021 카카오 채용연계형 인턴십 > 거리두기 확인하기 1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 2. 풀이 #include #include #include using na.. 2021. 9. 29.

티스토리툴바