📁문제 풀이

[Python] 백준 11404 플로이드 | 플로이드 워셜

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 해결 포인트 - 플로이드 워셜 알고리즘 - graph : 2차원 배열로 노드 별 각 노드까의 최소 거리를 저장한다. graph[i][j] 는 i에서 j로 가기 위한 최소 이동 거리를 의미함 - 각 간선 정보를 따라 무한수(INF)로 초기화 한 graph를 수정한다. 동일한 노선의 길이가 다른 간선이 있음으로 주의 필요 - a -> b 노선에 대..

[Python] 백준 18352 특정 거리의 도시 찾기 | 다익스트라 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 해결 포인트 - 다익스트라(Dijkstra) 알고리즘 - distance : X로부터 각 노드의 가장 짧은 경로. 경로가 없다면 무한수(INF) - graph : 각 노드가 연결되어 있는 정보 (연결 리스트) - q : 지금까지 계산 된 거리 중 간선이 가장 짧은 것을 ..

[Python] 백준 1753 최단 경로 | 다익스트라 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 해결 포인트 - 대표적인 다익스트라(Dijkstra) 알고리즘 문제 - 시작노드부터 각 노드까지 최소 거리를 저장하는 배열(distance)을 무한수(INF)로 초기화 - 연결 리스트 graph를 선언하여 각 노드의 연결 여부와 무게를 튜블형태로 저장 : graph[i][0]은 i와 연결된 노드를 의미하고 ..

[Python] 프로그래머스 N으로 표현 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - 8번 이상 연산은 불가능하다는 것을 인지하고 각 인덱스 크기 만큼의 연산 수행시 결과 수들을 저장하는 배열 선언 - dp[i]에는 i는 i+1번 연산시 표현 가능한 수들이 들어간다. - N이 5라면 55는 연산 2번을 의미하므로 해당하는 값을 미리 넣어 둔다. - 4중 for문 1) 연산 횟수 i 2) 해당하는 연산 횟수 이하 ..

[Python] 백준 1463 1로 만들기 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해결 포인트 - 전형적인 다이나믹 프로그래밍 문제이다. - 각 인덱스 번호를 구하기 위해서 필요한 최소 연산을 저장할 리스트를 입력 받은 N 크기로 생성. - 다이나믹 프로그래밍 바텀업(BottomUp) : 반복문 탑다운(TopDown) : 재귀 바텀업 방식이 스택 크기 제한으로부터 자유로움으로, 처음 연산을 저장하여 이후 동일한 연산 발생시 이를 사용하여 중복 연산을 피할 수 있다. - 최종적으로 1을 만드는 프로그램이므로 2부터 구하려는 n까지 각 수를 ..

[JAVA] 프로그래머스 신고 결과 받기 | HashMap | HashSet

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/92334 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - 파이썬처럼 배열에 다른 타입을 넣을 수 없기 때문에 헤맸으나 Map 클래스의 value에 Set 타입을 넣음 - 각 신고이력을 돌며 신고 당한 사람이 key값, 신고 한 사람들이 value - 각 유저 별 정지 메일을 카운트 하기 위해 LinkedHashMap을 정의(단순 HashMap으론 순서를 장담받을 수 없음) - 신고받은..

[JAVA] 프로그래머스 소수 찾기 | 에라토스테네스체 | 골든바흐의 추측

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12921 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - 2중 for문을 이용하여 간단하게 해결가능한 문제이지만 학습 겸 '에라토스테네스의 체' 개념을 사용하여 풀이했다. - 소수를 찾으면 해당 수의 배수는 모두 소수가 아니다. - boolean 배열을 n+2(0과 n 포함) 선언하여 소수를 만날 때마다 배수를 true 처리 한다. - 배열에서 false의 인덱스가 소수이다. 파이썬으..

[JAVA] 프로그래머스 모의고사 | ArrayList | Math

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42840?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - 학생별 패턴을 저장한 배열 정의 - answer를 돌면서 해당하는 번호에 학생이 작성한 답과 비교해 맞으면 ++ - Math의 .max 메소드 사용하여 최대값 찾기 - 최대값과 일치하는 학생이 몇명인지 알 수 없으므로 일치하는 번호를 ArrayList.add 를 이용하여 삽입 - 일치 학생의 수와 동일한..

[JAVA] 프로그래머스 포켓몬 | HashSet

🤫혼잣말 자바를 열심히 공부했던 기억 + 파이썬으로 알고리즘 문제풀이 자체에 대한 이해도 향상 이 두가지 덕분에 Python이 아닌 JAVA로 알고리즘 문제 풀이에 확실이 속도감이 있는 것같다! 하지만 JAVA만의 문법(HashSet, HashMap, Stream, String, StringBuilder, Arrays, Map ...)과 배열이나 문자열을 다루는 방식이나 불필요한 입력( 세미콜론(;), 괄호, 타입 입력 등)을 생각했을 때 파이썬이 코딩테이스에서 최강이라고 생각한다.. ~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/1845?language=java 프로그래머스 코드 중심의 개발자 채용..