본문 바로가기

분류 전체보기

 (386)
백준 1194번 - 달이 차오른다, 가자. (C++) https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net bfs 최단거리 문제임은 자명한데, 주어진 다른 조건이 있어 쉽지 않은 문제이다. 문제를 보며 깨달아야하는 것은 들고있는 열쇠마다 타일에 접근하는 것의 의미가 다름을 깨달아야한다. 즉 2,2 가 a라고 할 때 열쇠 a,b,c를 가지고 있는 것과 열쇠 a만을 가진 것은 의미가 전혀 다르다는 의미이다. 그래서 bfs를 돌 때 각 bfs 노드들은 x,y 말고도 현재 열쇠의..
기존 MySQL을 사용하고 있을 경우 Docker Mysql 포트 충돌 컨테이너 생성 중, 3306:3306 사용했을 때 오류 내용 (HTTP code 500) server error - Ports are not available: exposing port TCP 0.0.0.0:3306 -> 0.0.0.0:0: listen tcp 0.0.0.0:3306: bind: Only one usage of each socket address (protocol/network address/port) is normally permitted. 말그대로 3306포트는 오직 하나의 소켓만이 사용할 수 있는데 이미 점유중이라는 의미이다. netstat -ano gitbash 혹은 cmd(관리자모드)에 들어가 위 명령어를 실행하면 현재 사용중인 포트 번호들을 볼 수 있다. 3306포트는 6036..
백준 12893번 - 적의 적(C++) https://www.acmicpc.net/problem/12893 12893번: 적의 적 첫 줄에 용재 주위 사람의 수 N(1 ≤ N ≤ 2,000)과 적대관계의 수 M(0 ≤ M ≤ 1,000,000)이 주어진다. 두 번째 줄부터 M개의 줄에 거쳐 서로 적대관계에 있는 사람의 번호 A, B(1 ≤ A, B ≤ N)가 주어진다. www.acmicpc.net 문제를 처음 접했을 때 그래프 문제라는 것은 바로 파악할 수 있었다. 그러나 이 문제는 이분 그래프의 정석이라고 난이도 기여에서 말하던데 이분 그래프를 자세히 공부해본적이 없어서 조금 어려웠던 듯 하다. 우선 먼저 적대관계 그래프를 그려서 문제의 의미를 파악해보자. 1 2 2 3 3 4 4 5 입력이 들어온다면 위와 같은 적대 그래프가 만들어질 것이..
백준 1786번 - 찾기(C++) https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net KMP 알고리즘의 기본 문제이다. 문제에서도 친절하게 KMP알고리즘에 대해 설명하고 있다. https://tigerfrom2.tistory.com/400 문자열 찾기 - KMP 알고리즘 KMP 알고리즘이란? KMP 알고리즘이란 문자열에서 단어를 빠르게 골라낼 수 있는 알고리즘이다. 러프하게 생각하면 쉽게 문자를 찾아낼 수 있지만 이것은 아주 느리다. KMP의 아이디어 KMP의 중요한 tige..
문자열 찾기 - KMP 알고리즘 KMP 알고리즘이란? KMP 알고리즘이란 문자열에서 단어를 빠르게 골라낼 수 있는 알고리즘이다. 러프하게 생각하면 쉽게 문자를 찾아낼 수 있지만 이것은 아주 느리다. KMP의 아이디어 KMP의 중요한 아이디어는 접미사와 접두사이다. 접미사와 접두사는 단어를 반으로 잘라 왼쪽이 접두사 오른쪽이 접미사가 된다. ABCDAB 가 있으면 ABC는 접두사 DEF는 접미사가 된다. 자, 이걸 어떻게 쓸 수 있을까. 위 단어는 접두사와 접미사가 일치하는 것이 없다. 그러니 다른 예제를 보자. ABA 라고 생각하자. 접두사와 접미사에 모두 A가 있다. 그리고 ABAABA 라는 인풋에서 ABA를 찾는다고 생각해보자. ABAABA ABA 1개를 찾았다. 원래같으면 ABAABA ABA ABA 이런식으로 슬라이딩 윈도우처럼 ..
최소 스패닝 트리 (MST) - 프림 알고리즘 최단거리 알고리즘에는 우리가 익히 잘 아는 다익스트라 알고리즘, BFS가 대표적이다. 그러나 이 두개의 알고리즘은 모든 정점을 지나지 않고 무조건 최단거리를 찾는다. 그래서 모든 정점을 방문해야하는 문제를 해결할 수 없다. 때문에 MST 최소 스패닝 트리가 필요하다. 그래프에서 모든 정점을 지나는 트리를 그린다는 의미이다. 1. 프림 알고리즘 프림 알고리즘은 "정점" 을 아무거나 한 개 선택한다. 그리고 정점의 인접 정점들 중 가장 거리가 가까운 정점으로 이동한다. 그리고 지금까지 지나온 정점들 중 가장 가까운 곳으로 간다. 그림을 통해 이해하자. 자세히 설명해보면, 스탭1: 아무 정점이나 넣는다. 보통 1을 넣는다. 그리고 1에서 가장 가까운 곳으로 이동하면서 dist 배열을 업데이트한다. 스탭2: 현..
SWEA - 10806번 수 만들기 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXTC4piqD_IDFASe SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com A수 -> B수 이동 최소거리는 유서깊을 정도로 흔한 레파토리이다. 그래서 처음 생각한 풀이는 다익스트라였다. 왜냐하면 K = 1억이고 방문체크만해준다면 O(N)으로 풀이할 수 있기 때문이다. 그러나 이 방법을 사용하려면 최악의 경우 1억개 모두 dist 배열에 + 한 갯수를 저장해야하는데 이러면 int 배열을 사용하면 4억 바이트 = 4000KB = 약 400MB를 사용해야해서 불가능하다. 그래서..
백준 16928번 - 뱀과 사다리 게임(C++) https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 다익스트라, 그래프 등 많은 것을 고민했지만 그냥 bfs 풀이가 가장 쉬운 풀이이다. #include #include #include using namespace std; map jump; bool visited[101] = { false, }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL..

티스토리툴바