내가 그때 이걸 알았더라면

이전 글에서 python으로 만들었던 스도쿠 풀이 프로그램을 누구나 바로 사용할 수 있도록 html, css, js로 다시 만들어보았다. 간단하게 알고리즘을 설명하자면 입력받은 스도쿠가 해결가능한지 확인한다. 재귀함수로 구현한 백트래킹 알고리즘을 사용해 입력받은 스도쿠의 해를 찾는다. 만약 해가 있다면, 밑에 출력한다. 해를 찾을 수 없다면, 'Unable To solve Sudoku'를 출력한다. 소스코드 참고 - https://github.com/siejwkaodj/sudoku_solver_online Sudoku Solver Made by Hansj 설명 빈 칸에 스도쿠에 적혀있는 1-9 사이의 숫자를 입력하세요. 0을 입력하면 다음 칸으로 넘어갑니다. 파일 업로드는 .csv 또는 .txt파일만 가..

저번 글에 이어 이번 글에서는 그래프를 읽어온 결과를 바탕으로 그래프 상에서 dfs를 해보겠다. 0. 그래프 구조 먼저, 저번 글에서 사용한 그래프 구조를 직접 그리면 다음과 같다. 1. dfs 코드 dfs는 Depth-First-Search의 약자로 현재 정점에서 다음 정점으로 갈 수 있는 경우, 탐색을 계속하며 다음 정점이 없는 경우에는 부모 정점으로 돌아가 다시 갈 수 있는 정점가 있는지 판단한다. 다음 정점이 있는 경우 계속해서 탐색을 하기 때문에 트리에서 탐색할 경우, 루트 노드에서 계속해서 높이를 내려가면서 탐색을 하므로 dfs라는 이름이 붙었다. 코드 전반은 다음과 같다. int dfs(vector &graph, vector& visited, int n){ cout

이 글에서는 fstream 라이브러리를 이용한(C++11 이상 버전 권장, 버퍼 객체 bool 타입으로 변환 가능해서) 파일 입출력 예제를 다뤄보겠다. 수업에서 배운 dfs, bfs, 다익스트라 알고리즘 등을 복습할 겸 C++로 코드를 짜보았다. 1. include 먼저 기본 입출력에 필요한 iostream, 그래프 정보를 저장하는 데 쓸 이차원 배열을 동적으로 생성하기 위한 vector, 파일 입출력을 위한 fstream 라이브러리를 include 해온다. #include #include #include using namespace std; *std 네임스페이스를 미리 선언했다. 이렇게 되면 원래는 std::fstream 형인 fstream을 그냥 fstream으로 사용할 수 있다. 2. 변수들과 파일..

java에서는 String 클래스에 문자열을 특정 문자열을 인수로 받아 쪼개주는 메서드인 .split()이 존재한다. 하지만, "." 이나 "\" 같은 예약어들은 함부로 사용할 수 없다. 그럴 땐 다음과 같은 방법을 이용할 수 있다. 1. "." 으로 split() 하기 .split("//."); .split("[.]"); 2. "\" 으로 split() 하기 .split("////"); 참고 블로그 : https://mousevm.tistory.com/224 String.split( ) 함수에서 구분자로 역슬래시("\") 사용하기. 오늘도 역시 삽질 끝에 알아낸 소중한 하나의 정보를 기록합니다. ㅋㅋ 오늘은 자바의 String.split( ) 함수에서 구분자로 역슬래시("\")를 사용해서 문자열을 분리..

자바에서 스윙 라이브러리를 사용하려고 다음과 같이 import시 오류가 나는 상황이 있었을 것이다. import javax.swing.*; 이때, java 11 이후로는 java.base 모듈만 기본으로 포함하므로, 그 이외의 다른 모듈들을 사용하기 위해서는 따로 불러오기가 필요하다. 따라서 module-info.java 파일에 다음과 같이 작성해준다. module { requires java.desktop; } 예시) 참고 블로그 : https://daily-life-of-bsh.tistory.com/129

1. 서론 다익스트라 알고리즘이란, 그래프 상에서 한 정점에서 다른 (모든) 정점으로의 최단경로를 구하기 위해 사용되는 알고리즘이다. 인접 리스트와 우선순위 큐를 이용해 손쉽게 구현할 수 있다는 장점이 있어 많은 사람들이 사용한다. 2. 설명 먼저, 다음과 같은 그래프가 있다고 가정하자. 다익스트라 알고리즘은 먼저 시작점 자신의 거리를 0으로 두고 다른 갈 수 있는 모든 점들의 최단거리값 (dist[])를 업데이트한다. 업데이트시 만약 [현재 노드의 cost + 현재 가리키는 노드로 가는 edge의 cost] 값이 가리키는 노드의 dist값보다 작다면, dist를 업데이트한다. 그 다음, 방문하지 않은 다른 모든 점들중 가장 dist값이 작은 노드를 시작점으로 잡고, 다시 dist를 업데이트한다. 이를 ..

1. 변수 한 개를 추가로 생성한다. void swap(int *a, int *b){ int tmp = *a; *a = *b; *b = tmp; return; } 2. xor 연산을 사용한다. void swap(int *a, int *b){ *a ^= *b; *b ^= *a; *a ^= *b; return; } 3. 덧셈 연산을 사용한다. void swap(int *a, int *b){ *a = *a + *b; *b = *a - *b; *a = *a - *b; return; } // 또는 더 간단하게 void swap(int *a, int *b){ *a += *b; *b = *a - *b; *a -= *b; return; } 1. 방법은 간편하지만 추가로 변수를 생성해야 한다는 단점이 존재하고 (메모리 ..

참고 링크 : https://gist.github.com/480/4681b67d2a906db8c6c1321cc678f05f github 리모트 리포지토리 변경하기 github 리모트 리포지토리 변경하기. GitHub Gist: instantly share code, notes, and snippets. gist.github.com 1. 기존 repository pull/push 하기 git pull git add . git commit -m "clean push" git push 2. 기존 repository remote 제거 git remote remove origin 3. 새 repository remote 추가 git remote add origin [깃 주소]

1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 양의 정수 n(1 ≤ n ≤ 100,000)과 n개의 원소로 이루어진 수열 An이 주어진다. 이때, An에서 가장 큰 구간합을 구하여라. 2. 해결 방법 1. Brute Force 먼저 가장 간단한 방법은, Brute Force 방식으로 크기 n의 int 배열을 만들어 i번째 자리에서 1~i-1번째 자리부터에서의 합을 구해 O(n^2)(1~i에서 O(n), 이를 1번째부터 i-1까지 반복하므로 O..

1. 문제 https://www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소 www.acmicpc.net 집합 A에는 속하지만, B에는 속하지 않는 원소들의 개수와 원소들을 모두 출력하는 문제이다. 집합에서 A - B (차집합)의 개념이 등장한다. 2. 풀이 방법 배열이나 리스트 등을 사용하면 해당 자료형 안에 특정 원소가 있는지 확인하려면 O(1)의 시간이 걸리기에, 접근하는데 시간이 O(1)이 걸리는 맵 자료형을 이용하여 문제를 해결했다. 먼저 A와 ..