Amazing circle of numbers 1 to 32

웹서핑을 하다가 신기한 짤을 하나 보게 되었다. 흔히 서울대 애들이 흥분하는 짤이라고 하는데 너무 신기해서 가져와봤다. 간단하게 설명하자면 원에는 1부터 32까지의 수가 중복 없이 들어 있으며, 인접한 두 수를 더하면 제곱수가 된다. 너무 신기하다! 원리가 궁금했다. 그래서 찾아보던 와중 또 신기한 사실을 발견했다. n=32일 때만 우연하게 가능한 줄 알았는데 32 이상의 자연수면 가능하다고 한다. 어떻게 가능한 건지 수학적으로 증명된 것은 찾지 못했지만.. n이 다른 숫자일 때 정말 가능한지, 가능하다면 그 배열이 어떻게 되는지 궁금했다. 자료를 찾다보니 위의 문제는 해밀턴 순환을 찾는 문제와 같다고 해서 직접 구현해보기로 했다. 해밀턴 순환을 찾는 문제는 그래프와 백트래킹 알고리즘을 이용해서 풀 수 ..

→2022.04.10

Algorithm/Baekjoon Online Judge

[백준] 9935번 문자열 폭발 (Java)

백준 9935번 문자열 폭발 : https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 www.acmicpc.net 예전에 풀었던 키로거 문제에서 문자열 처리할 때 스택을 사용했던 기억이 나서 스택을 사용해서 구현했다..

→2020.03.08

Algorithm/Programmers

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 매칭 점수 (Java)

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 매칭 점수 : https://programmers.co.kr/learn/courses/30/lessons/42893 코딩테스트 연습 - 매칭 점수 | 프로그래머스 매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다. 그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다. 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 programmers.c..

→2020.03.07

Algorithm/Programmers

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 블록 게임 (Java)

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 길 찾기 게임 : https://programmers.co.kr/learn/courses/30/lessons/42894 코딩테스트 연습 - 블록 게임 | 프로그래머스 [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] 2 programmers.co.kr 2019 카카오 공채의 마지막 문제 블록 게임..

→2020.03.06

Algorithm/Programmers

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 길 찾기 게임 (Java)

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 길 찾기 게임 : https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 | 프로그래머스 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 이번 문제는 딱히 알고리즘이랄 건 없고, 트리 자료구조를 구현할 수 있는지를 묻는 문제이다. 입력으로 nodeinfo를 받으면 각각의 정보를 Node로 변환하여 배열에 저장해준다. 그 후, 정렬을 해줘야 한다. 정렬을 하는 이유는 루트 노드부터 시작해서 순서대로 ..

→2020.03.06

Algorithm/Programmers

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 무지의 먹방 라이브 (Java)

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 무지의 먹방 라이브 : https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 | 프로그래머스 programmers.co.kr 이번 문제는 효율성 테스트가 있는 문제였다. 회전판(배열)에는 N개의 음식이 있고, 각 음식에는 1부터 N까지 번호가 붙어있다. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. K초 후에 무지가 몇 번 음식을 먹을 차례인지 구하는 문제다. 단순하게 생각하면 while문으로 시간을 흐르게 하면서 각 음식의 값을 1씩 낮추면서 반복하면 된다. 하지만 음식의 개수가 최대 20..

→2020.03.06

Algorithm/Programmers

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 후보키 (Java)

[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 후보키 : https://programmers.co.kr/learn/courses/30/lessons/42890# 코딩테스트 연습 - 후보키 | 프로그래머스 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 관계형 데이터베이스에서 후보 키의 최대 개수를 구하는 문제다. 후보 키를 만족하려면 아래의 두 조건을 만족해야 한다. 유일성(Uniqueness..

→2020.03.06

Algorithm/Programmers

[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 블록 이동하기 (Java)

프로그래머스 2020 KAKAO BLIND RECRUITMENT 블록 이동하기 : https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 | 프로그래머스 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 구현하는 데 상당히 오랜 시간이 걸린 2020 카카오 공채 마지막 문제 블록 이동하기다. 평소에 bfs를 활용하여 map에서 이동하는 문제를 많이 풀어봐서 금방 풀 줄 알았지만, 회전하는 부분이 까다로워서 오래 걸렸다. 처음에는 로봇의 왼쪽 좌표, 오른쪽 좌표를 둘 다 클래스에 저장하여 조작을 ..

→2020.03.01

티스토리툴바