본문 바로가기

전체 글

 (147)
[BOJ 1799] 비숍 이문제를 일반적인 백트래킹 방식으로 풀면 N이 최대 10일때 최대 2^100 경우의수가 생겨 시간초과가 된다. 그래서 발상의 비약이 필요한 문제고 그 아이디어는 체스판을 분할하는것이다. 체스판을 보면 흑과 백으로 나뉘어지는데 이것이 비숍의 공격방향과 일치한다. 비숍의 입장에서는 흑과 백은 서로 독립적이라 붙어만 있을뿐이지 서로 영향을 미치지 못한다. 따라서 흑과 백으로 나누면 N이 10일때 N이 5인 체스판 두개로 생각할수 있고 시간복잡도는 2^(25) = 33554432로 충분히 시간안에 해결할수 있는 문제가 된다. 비숍의 공격방향은 대각선이라 BFS같이 상하좌우로 움직이는것과는 달리 약간의 수학적 테크닉이 사용된다. / 방향 대각선은 x+y로 나타낼수있다. \ 대각선은 x-y+n-1로 나타낼수 있다...
[BOJ 1600번] 말이 되고픈 원숭이 BFS 문제는 일반적으로 기본문제만 풀수있는 수준과 심화 문제를 풀수있는 수준이 극명하게 갈리는데 이 문제는 바로 그 경계선이 되는 수준의 문제인것 같다. 정답률이 20퍼다. 본인이 번뜩이는 창의성이 부족한 평범한 사람이라면 분명히 이 문제에서 막히게 될것이고 이것은 발상의 비약이 필요한 순간이라고 할수 있다. 물론 내 이야기다. 알고리즘을 풀면서 어떻게 이런 생각을 하는지 감탄을 넘어서 존경하게되는 순간과 희열을 느끼는 순간과 벽을 느끼는 순간이 종종 있는데 이 문제도 그런류의 문제인것 같다. 나 역시 이문제를 좀 고민해보고 답지를 본 입장으로서 새로운 발상에 눈을 뜬 기분이였다. 일단 딱봐도 BFS를 발상하는것은 어렵지 않다. 문제는 원숭이는 말처럼 움직이는 횟수가 최대 K번이기 때문에 일반적인 BF..
[BOJ 2504번] 괄호의 값 이번문제는 스택 괄호쌍의 응용으로 쉽지 않은 문제였다. 다른 사람의 풀이 설명은 알고리즘이 동작하는 것 위주로 설명하는데 나로서는 쉽게 받아들여지지 않았다. 단순히 이 알고리즘 풀이만 외운다면 이 문제야 풀수 있겠지만 응용력은 기를수 없어보였다. 항상 어떤 문제를 풀때 아이디어가 뭐고 어떻게 발상했는지를 모르면 다른문제에 적용을 할수가 없어서 나는 내 언어로 완전히 바꾸고 이해를 해야 하는 타입이였다. 그래야만 한문제를 풀어도 열문제를 푼 효과를 얻을수 있기 때문이다. 모르는 문제를 답지를 보고 풀고 그 아이디어를 제대로 배웠다면 수십가지의 응용들도 해결할 능력을 얻기 때문에 모르는 것 위주로 문제를 풀어야하고 그게 좋은 방향인걸을 스스로 잘 알지만 역시 문제 앞에서 지고 말았다는 생각이 들어 항상 기분..
[BOJ 11003번] 덱을 이용한 최솟값 문제 처음에 이문제를 보고 덱을 이용해서 원소를 앞뒤로 삭제 추가 해주면서 포인터를 이용해서 최솟값만 그때 그때 뽑아주면 된다고 생각했지만 최악의 경우 N은 1000000 인데 시간복잡도가 N^2logN 이 돼서 아무리 최적화 해봐도 통과되지 않았다. 일단 원소가 앞에서는 삭제되고 뒤에서는 추가 되니까 덱을 발상하는것을 어렵지 않았다. 그리고 한칸씩 슬라이딩 윈도우가 지나가면서 변하는 최솟값을 구하는것인데 이부분을 구현하기가 어려웠다. 그래서 답을 확인했고 이번에 덱의 활용법을 새로 배웠다. 일단 한칸씩 이동하기 때문에 덱 전체를 그때마다 sorting하는것은 너무 낭비라는것을 이해해야 한다. 이 부분에서 시간초과가 났다 이미 알고있는 원소를 충분히 활용하면서 최솟값을 찾아내는 방법은 덱의 성질을 이용하는 것..
모두의 네트워크(3) 물리계층 트위스트 페어 케이블(UTP, STP)을 일반적으로 랜 케이블이라고 부름 랜 케이블은 다이렉트 케이블, 크로스 케이블이 있음 크로스 케이블은 다이렉트 케이블과 달리 데이터 충돌을 막기위해 송신과 수신 선을 교차한 구조 다이렉트 케이블은 한쪽은 1,2번 송신 3,6번 수신 다른쪽은 1,2번 수신 3,6번 송신 크로스 케이블은 양쪽다 1,2번 수신 3,6번 송신 하지만 교차해서 충돌없이 통신 가능 리피터: 신호 증폭하는 기능을 가진 네트워크 중계 장비 (리피터) 허브: 포트를 가지고 여러대의 컴퓨터와 통신할수 있는 장비, 전기신호 정형 및 증폭(리피터) 한 포트에서 다른 포트로 데이터를 전송하면 나머지 포트에도 데이터가 전송됨 -> 보안 문제 발생 -> 더미 허브라고도 함
모두의 네트워크(2) 프로토콜: 통신하기 위한 규약 OSI 모델: 데이터를 응용 계층, 표현 계층, 세션 계층, 전송 계층, 네트워크 계층, 데이터 링크 계층, 물리 계층인 7개의 계층으로 나누어서 전송하는 모델 응용 계층: 애플리케이션 서비스 제공 표현 계층: 데이터 변환 세션 계층: 세션 체결, 통신방식 결정 전송 계층: 신뢰할수 있는 통신 구현 네트워크 계층: 다른 네트워크와 통신하기위한 경로 설정 및 논리 주소 결정 데이터 링크 계층: 네트워크 기기 간의 데이터 전송 및 물리주소 결정 물리 계층: 시스템 간의 물리적인 연결과 전기 신호 변환 및 제어 TCP/IP 모델: 데이터를 응용 계층, 전송 계층, 인터넷 계층, 네트워크 접속 계층인 4개의 계층으로 나누어서 전송하는 모델 캡슐화와 역캡슐화: 캡슐화는 컴퓨터 통신에..
모두의 네트워크(1) 네트워크 구조 네트워크: 두개 이상의 컴퓨터 간의 연결 인터넷: 전 세계의 큰 네트워크부터 작은 네크워크까지 연결하는 거대한 네트워크 패킷: 컴퓨터 간의 데이터를 주고 받을때 네트워크를 통해 전달하는 데이터의 기본 단위(큰 데이터는 작은 패킷으로 분할) 랜(LAN)과 왠(WAN) 랜(LAN): 건물 안이나 특정 지역을 범위로 하는 근거리 통신 네트워크 왠(WAN): U+ 같은 통신회사인 인터넷 서비스 제공자(ISP)가 제공하는 서비스를 사용하여 구축한 광역 통신 네트워크 랜은 범위가 좁고 속도가 빠르며 오류가 발생할 확률이 낮음 왠은 범위가 넓고 속도가 느리며 오류가 발생할 확률이 높음 가정에서는 인터넷 서비스 제공자와 인터넷 공유기를 연결하고 유무선 랜을 통해 네트워크를 구성 회사에서 하는 랜 구성 D..
소개팅 웹 애플리케이션(5)_최종 이렇게 소개팅 웹 애플리케이션이 마무리 되었습니다. 앞서 포스팅한 모든 기능을 한꺼번에 동영상으로 편집해보았습니다. 앞으로 추가하고 싶은 기능은 단순한 쪽지만이 아니라 네트워크를 사용한 실시간 채팅 기능을 구현하고 싶고 실제 운영 서비스까지 해볼수 있다면 좋겠습니다. 자세한 코드는 아래 제 깃허브에 올려놓았습니다. https://github.com/joshiaLee/meetingapp GitHub - joshiaLee/meetingapp: meetingapp meetingapp. Contribute to joshiaLee/meetingapp development by creating an account on GitHub. github.com 처음에 소개팅 어플을 만들어야겠다고 시작했을때 기본적인 백엔드 ..

티스토리툴바