내가 그때 이걸 알았더라면

이전 글에서 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파일만 가..

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와 ..

1. 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 길이가 n일 수열이 주어질 때, 이 수열에서 가장 긴 증가하는 부분 수열의 길이(연속일 필요는 없지만 증가해야 함)를 구하면 되는 문제이다. 2. 풀이 방법 LIS 문제의 해결법은 이 블로그에 잘 나와 있다. https://seungkwan.tistory.com/8 가장 긴 증가하는 부분 수열 (Longest..

1. 문제 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장 났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고 있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장 났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 입력 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 ..

참고한 블로그 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html [알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 알고리즘을 풀다 내가 삽입 정렬도 구현하지 못하는 것을 발견했고, 잊지 않고자 기록한다... 먼저 삽입 정렬이란 다음과 같다. (오름차순 정렬이라고 가정) https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC 삽입 정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 삽입 정렬(揷入整列..

https://m.blog.naver.com/ndb796/221236874984 25. 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 ... blog.naver.com https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%ACTopology-sort [알고리즘] 그림으로 알아보는 위상 정렬(Topology sort) 위상정렬은 순서가 정해져 있는 노드..

> 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효..

> 문제 문제 링크 : https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 문제 요약 : 총 n개의 방문자 수가 주어질 때, x일간 방문한 최대 방문자수와 그 방문자수가 있는 구간의 개수를 구하여라. > 풀이들 첫 번째 풀이 : 구간 x 안에 있는 사람들의 합을 각각 구하고, 그걸 n - x + 1번만 반복하면 되는 줄 알았다. 하지만 시간 초과가 떠서 다른 방법을 생각해야만 했다. (시간 복잡도가 O(n-x+1) * O(x) => O(x*..

백준 9461 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 나선을 따라 가며 n번째의 삼각형의 변의 길이를 찾는 문제이다. 삼각형의 변의 길이는 이전 삼각형과 5번째 전 삼각형의 변의 길이를 더한 것과 같다는 점을 이용해 문제를 해결할 수 있다. 정삼각형의 한 각의 크기는 60도이므로, 이 점을 이용해 5번째 전의 삼각형을 추론할 수도 있을 것이다. 코드는 다음과 같다. t = int(input()) for i in range(t):..

N - Queen 문제 중 한 종류인 8-Queen 문제이다. N - Queen 문제는 결국 n을 입력받아 n * n 사이즈 보드 안에 n개의 퀸을 겹치지 않고 배열할 수 있는 경우의 수가 얼마나 되는지를 세는 알고리즘이다. 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예시 입력과 출력은 다음과 같다. 이외에도 표로 나머지 경우를 정리하면 다음과 같다. n 1 2 3 4 5 6 7 8 경우의 수 1 0 0 2 10 4 40 92 이외에도 9..