전체 글
-
https://www.acmicpc.net/problem/17213 17213번: 과일 서리 민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. www.acmicpc.net 접근 하기 중복조합 N개의 과일에서 중복을 허용해서 M개를 고르는 문제이다. 선택된 M개의 과일에는 순서가 없기 때문에 조합이 적용된다. 단 모든 과일은 한번씩은 선택되어야 한다. 그렇다면 애초에 이 과일들은 한번씩 선택한 것으로 간주하고 나머지 N개의 과일에서 M-N개를 중복해서 고르는 중복 조합(nHr)으로 처리하면 된다. 중복조합의 개수? 그럼 중복조합의 개수는 어떻게 구할 것인가? 중복조합은 코드..
[BJ]17213. 과일서리https://www.acmicpc.net/problem/17213 17213번: 과일 서리 민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. www.acmicpc.net 접근 하기 중복조합 N개의 과일에서 중복을 허용해서 M개를 고르는 문제이다. 선택된 M개의 과일에는 순서가 없기 때문에 조합이 적용된다. 단 모든 과일은 한번씩은 선택되어야 한다. 그렇다면 애초에 이 과일들은 한번씩 선택한 것으로 간주하고 나머지 N개의 과일에서 M-N개를 중복해서 고르는 중복 조합(nHr)으로 처리하면 된다. 중복조합의 개수? 그럼 중복조합의 개수는 어떻게 구할 것인가? 중복조합은 코드..
2022.12.13 -
BJ_S2_12891_DNA문자열 문제링크 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/UL0g9xMs61E - YouTube www.youtube.com 소스보기 동영상 설명을 보고도 전혀 구현이 안된다..
[BJ]S2_12891_DNA문자열BJ_S2_12891_DNA문자열 문제링크 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/UL0g9xMs61E - YouTube www.youtube.com 소스보기 동영상 설명을 보고도 전혀 구현이 안된다..
2022.12.01 -
SWEA 모의 4008 숫자 만들기 문제링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/AlZzI73F--E 소스보기 동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다. 소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성..
[SWEA]SWEA 모의 4008 숫자만들기SWEA 모의 4008 숫자 만들기 문제링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/AlZzI73F--E 소스보기 동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다. 소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성..
2022.09.25 -
이번에는 최단 경로의 마지막 알고리즘인 플로이드 워셜 알고리즘에 대해서 살펴보자. 플로이드 워셜 알고리즘 플로이드 워셜의 특징 이제까지 다익스트라와 벨만포드 알고리즘을 이용한 최단 경로를 구해봤다. 한 점에서 모든 점까지의 최단 거리를 구할 수 있었고 여차하면 음의 간선까지 처리할 수 있었는데 또 필요한 최단 거리 알고리즘이 있을까? 있으니까 여기서 글을 쓰고 있다. ㅎ 이번에 알아볼 알고리즘은 플로이드 워셜 알고리즘이다. 플로이드는 이전까지의 알고리즘과 달리 모든 정점에서 모든 정점까지의 최단거리를 구하기 위한 알고리즘이다. 물론 다익스트라, 벨만포드의 모든 정점을 출발점으로 해서 N번 돌리면 모든 정점에서의 최단거리를 구할 수 있다. 하지만 플로이드 워셜은 대체로 다익스트라, 벨만포드를 N번 돌릴 때..
[최단경로] 04. 플로이드 워셜이번에는 최단 경로의 마지막 알고리즘인 플로이드 워셜 알고리즘에 대해서 살펴보자. 플로이드 워셜 알고리즘 플로이드 워셜의 특징 이제까지 다익스트라와 벨만포드 알고리즘을 이용한 최단 경로를 구해봤다. 한 점에서 모든 점까지의 최단 거리를 구할 수 있었고 여차하면 음의 간선까지 처리할 수 있었는데 또 필요한 최단 거리 알고리즘이 있을까? 있으니까 여기서 글을 쓰고 있다. ㅎ 이번에 알아볼 알고리즘은 플로이드 워셜 알고리즘이다. 플로이드는 이전까지의 알고리즘과 달리 모든 정점에서 모든 정점까지의 최단거리를 구하기 위한 알고리즘이다. 물론 다익스트라, 벨만포드의 모든 정점을 출발점으로 해서 N번 돌리면 모든 정점에서의 최단거리를 구할 수 있다. 하지만 플로이드 워셜은 대체로 다익스트라, 벨만포드를 N번 돌릴 때..
2022.09.07 -
이번 포스트에서는 음의 가중치를 갖는 간선에서 최단 거리를 구할 수 있는 벨만포드 알고리즘에 대해 살펴보자. 벨만포드(Bellman-Ford) 알고리즘 다익스트라의 한계 이전 글에서 다룬 다익스트라 알고리즘은 검증된 그리디한 알고리즘으로 매번 최선의 선택을 하기 때문에 상당히 빠른 시간에 최단 경로를 구할 수 있다. 하지만 나중에 발견된 경로에서 음의 가중치가 발견되면 이전의 선택이 최선이 아니기 때문에 사용할 수 없다. 벨만포드 알고리즘 벨만포드는 다익스트라 처럼 가중치 그래프에서 출발점에서 다른 모든 정점까지의 최단 거리를 찾는 알고리즘이다. 단 다익스트라와 달리 음의 가중치를 처리할 수 있으며 간선 중심의 알고리즘이다. 벨만포드는 최단 거리의 정점만을 찾아다니지 않고 시작 정점에서 각 정점까지의 최..
[최단경로] 03. 벨만포드 알고리즘이번 포스트에서는 음의 가중치를 갖는 간선에서 최단 거리를 구할 수 있는 벨만포드 알고리즘에 대해 살펴보자. 벨만포드(Bellman-Ford) 알고리즘 다익스트라의 한계 이전 글에서 다룬 다익스트라 알고리즘은 검증된 그리디한 알고리즘으로 매번 최선의 선택을 하기 때문에 상당히 빠른 시간에 최단 경로를 구할 수 있다. 하지만 나중에 발견된 경로에서 음의 가중치가 발견되면 이전의 선택이 최선이 아니기 때문에 사용할 수 없다. 벨만포드 알고리즘 벨만포드는 다익스트라 처럼 가중치 그래프에서 출발점에서 다른 모든 정점까지의 최단 거리를 찾는 알고리즘이다. 단 다익스트라와 달리 음의 가중치를 처리할 수 있으며 간선 중심의 알고리즘이다. 벨만포드는 최단 거리의 정점만을 찾아다니지 않고 시작 정점에서 각 정점까지의 최..
2022.09.06 -
이번 포스트에서는 발음이 정말 생소한 다익스트라 알고리즘에 대해서 살펴보자. 이 알고리즘은 에츠허르 다익스트라라는 네델란드 개발자분이 고안한 알고리즘이라고 한다. 튜링상을 받은 어마어마한 분이다.! 다익스트라 알고리즘이란? 다익스트라 알고리즘은 특정 시작 정점에서 거리가 최소인 정점을 계속해서 선택해 나가다보면 결과적으로 최단거리를 구할 수 있다는 생각에서 출발한 알고리즘이다. 다익스트라 알고리즘은 현재 상태에서 가장 최선이라고 생각되는 정점들을 쭉~탐색해 나가는 그리디 알고리즘이다. 검증이야 이미 다익스트라 아저씨가 잘 해놓은 상태이다. ㅎ 아래와 같은 그래프를 생각해보자. 출발점 S에서 목적지 D로 가는 경로는 총 3가지가 가능하다. S->D로 한방에 갈 수도 있지만(W_SD = 50) 이 길은 시골..
[최단경로] 02. 다익스트라이번 포스트에서는 발음이 정말 생소한 다익스트라 알고리즘에 대해서 살펴보자. 이 알고리즘은 에츠허르 다익스트라라는 네델란드 개발자분이 고안한 알고리즘이라고 한다. 튜링상을 받은 어마어마한 분이다.! 다익스트라 알고리즘이란? 다익스트라 알고리즘은 특정 시작 정점에서 거리가 최소인 정점을 계속해서 선택해 나가다보면 결과적으로 최단거리를 구할 수 있다는 생각에서 출발한 알고리즘이다. 다익스트라 알고리즘은 현재 상태에서 가장 최선이라고 생각되는 정점들을 쭉~탐색해 나가는 그리디 알고리즘이다. 검증이야 이미 다익스트라 아저씨가 잘 해놓은 상태이다. ㅎ 아래와 같은 그래프를 생각해보자. 출발점 S에서 목적지 D로 가는 경로는 총 3가지가 가능하다. S->D로 한방에 갈 수도 있지만(W_SD = 50) 이 길은 시골..
2022.09.01