본문 바로가기

전체 글

 (403)
백준 20006번 - 랭킹전 대기열 (C++) https://www.acmicpc.net/problem/20006 20006번: 랭킹전 대기열 모든 생성된 방에 대해서 게임의 시작 유무와 방에 들어있는 플레이어들의 레벨과 아이디를 출력한다. 시작 유무와 플레이어의 정보들은 줄 바꿈으로 구분되며 레벨과 아이디는 한 줄에서 공백 www.acmicpc.net 처음에는 정렬을 해두고 풀어도 되는 줄 알았는데 순서대로 게임을 진행해야하는 조건이 있었다. (진짜 문제좀 잘 읽자) 그리디 , 구현 문제였다. 처음에는 우선순위큐 문제인가 생각했는데 기준이 달라지는 것이 아니기 때문에 우선순위큐는 필요없다. 나는 게임방의 기준을 rooms 벡터에 담아두고 어차피 순서가 바뀌지 않기 때문에 그 순서대로 다음 레벨을 비교해서 문제를 풀었다. 구현을 연습하는데 좋은 문제..
백준 10159번 - 저울 (C++) https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 이전에 푼 키 순서 문제와 거의 같다. 이렇게 "순서"에 관련된 문제들은 위상정렬도 생각하게 된다. 위상정렬은 inorder와 outorder를 새면서 bfs돌며 순서를 정하는 방식이다. 아무튼, 이 문제에서 플로이드-워셜로 관계 찾는 기법을 복습해보았다. 초기화를 하고 dp를 사용해 각 정점이 경유하여 갔을 때 더 빠르게 갈 수있으면 갱신하는 것이 플로이드 워셜이다. 그..
백준 2458번 - 키 순서 (C++) https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 두 가지 방식으로 풀어낼 수 있다. 1. dfs 2. 플로이드-워셜 1. 먼저 1번 방법을 알아보자. 내 키의 순서를 알 수 있다는 의미는 모든 노드와 연관되어 있다는 뜻이다. 더 풀어보자면 n번 노드에서 출발했을 때 모든 노드를 방문한다는 의미이다. 하지만 이 그래프는 단방향 그래프이다. 그리고 작은 키 -> 큰 키 로 이루어져 있다. 그러므로 두가지 dfs를 진행하는 것이 정 해이다. 작은키 -..
플로이드-워셜 알고리즘 플로이드-워셜 알고리즘은 그래프 이론에서 모든 정점간의 최단 경로를 찾기 위한 알고리즘이다. 이 알고리즘은 두 개의 단계로 이루어진다. 위 그래프를 예로 들어 초기 배열을 만들어보자. 그리고 각 노드를 경유지로 지정한다. 즉 지금은 인접노드만 가지고 있지만 1 → 2 → 3 이러한 경우도 계산한다는 뜻이다. 먼저 1번 노드를 경유한다고 가정하자. 그렇다면 1행은 스킵하고 2행을 진행한다. DP[4][2] = DP[4][1] + DP[1][2] 이므로 다음과 같은 점화식을 얻을 수 있다. DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j]) 위 점화식을 해석하면 정점 i 와 j의 최소 거리는 원래 지정되어 있던 값과 노드 k를 경유했을 때의 최소값이다. 그러므로 k도 1부터 N..
Spring Boot - Java 동적 페이지 웹 크롤링 Selenium Notion에서 Tistory로 자동업로드하는 프로젝트를 진행중에 정적 웹 크롤링과 동적 웹 크롤링이 다르다는 것을 알게 되었다. 그래서 동적 웹 크롤링을 따로 공부해야했다. Selenium 셀레니움은 웹 애플리케이션을 실행시켜볼 수 있는 프레임워크이다. 자동 로그인, 자동 글쓰기, 자동 클릭 등 많은 기능을 사용할 수 있다. 의존성 Gradle implementation 'org.seleniumhq.selenium:selenium-java:4.6.0' Chrome Driver 다운로드 크롬 우측 위 … 클릭 도움말 Chrome 정보 클릭 후 버전 확인 https://chromedriver.chromium.org/downloads 사이트에서 맞는 Chrome driver 다운로드 다운받은 chromedr..
JavaScript - 이벤트 핸들러 이벤트 핸들러 : 웹 페이지에서 사용자 상호작용과 관련된 동적인 기능을 구현하기 위해 사용되는 기술이다. Ex) 마우스 클릭, 키보드 입력, 스크롤 등 자바스크립트는 다양한 이벤트 핸들링 API를 제공한다. HTML 내부 이벤트 핸들러 Click me 여기서 버튼을 누르면 onClick이라는 이벤트 핸들러에 통제하에 실행된다. 그리고 아래 스크립트 태그에서 자바스크립트 코드를 정의하고 있다. 그러나 이것은 지양하는 방법이다. 유지보수가 어렵고 보안에도 좋지 않다. 그래서 Chrome 확장 프로그램에서는 아에 내부 이벤트 핸들러가 포함되어 있으면 실행조차 안되도록 만들어 버린다. HTML 외부 이벤트 핸들러 텍스트 입력: Click me document.addEventListener('DOMContentL..
백준 12919번 - A와 B 2(C++) https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 브루트포스, 재귀로 분류되어있는 문제이다. 문자열을 만들 수 있는 케이스는 두개가 있다. 그렇다면 재귀는 다음과 같이 이루어질 것이다. Recusstion(현재 문자열){ if(현재 문자열 == 목표 문자열) 함수종료 Recussiton(A를 더한 문자열) Recusstion(B를 더하고 뒤집은 문자열) } 이렇게 해도 답은 도출할 수 있다. 아마도 이 문..
백준 20055번 컨베이어 벨트 위의 로봇 (C++) https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 시뮬레이션 + 구현문제이다. 약간 삼성틱한 문제인데 역량 기출문제는 아니었다. 별다른 알고리즘이 필요한 것은 아니고 그냥 구현이 피곤한 문제였다. 아이디어는 빠르게 떠올렸는데 두 부분에서 해맸다. 1. 2차원배열의 위치 변경 2. 문제를 조금 잘 못 읽음 다른 사람들은 1차원 배열로 만들어서 풀이했는데 이것도 좋은 방법이다. 그러나 난 문제가 시키는대로 풀이했다. 이번에는 별..

티스토리툴바