지난 9월 23일 acm-icpc 인터넷 예선을 치뤘다.목표는 대학 순위 9등 전체 순위 20등이었는데대학 순위 6등 전체 순위 15등으로 목표치보다 결과가 좋아서 기분이 좋다. 시간순으로 이벤트를 설명하자면일단 시작하고 K 등록을 봤는데 작년에는 팀명 팀번호? 이었던거 같은데 비밀번호를 입력하라고 했다.ㅋㅋㅋㅋ다행이 팀아디 비번 팀명 3개를 적어놔서 0분 솔브했다. 이후 한글 문제를 찾다가 H를 내가 읽었고 두 수에서 최댓값과 세 수 에서 최댓값을 구하는 문제이었다.배열을 소팅하고 3개조합을 뽑는 포문을 짠다면 ijk 3중 포문을 돌릴텐데 사실 최대값이므로 k는 j+1이거나 n이어야 하는게명확하다 위 방법으로 구현하였고 6분 솔브하였다. 조금만 더 빨리 풀었으면 퍼솔이었을텐데 아쉽다. 이후 팀원이 I를..
카카오 코드 페스티벌 본선 쑤아리 질러ㅓㅓㅓㅓㅓㅓ예에ㅔㅔㅔㅔㅔㅔ 경기창조혁신어쩌구경제뭐센터에서 9월 9일에 했다. 판교를 처음 가봤는데 회사들이 다닥다다닥 붙어있었다.신기해애ㅔ에에ㅔㅔㅔ (카와이이ㅣㅣㅣㅣㅣㅣㅣ) 광주에서 9시 30분 고속버스를타고 부릉부릉 떠나서 1시쯤 성남에 도착해 셔틀버스타고 1시 20분쯤? 에 최종 도착했다.생각보다 직원분들이 되게 많았다. 샌드위치 3개 정도 쿰척쿰척하고 대회장에 들어갔다. 이런 느낌으로 세팅해두었다. 14시부터 대회 시작인데 13시 40분 부터 입장했던거 같고 연애인들의 코드 페스티벌 격려? 응원? 영상을 틀어줬다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 진짜 뜬금 없었다.약간 mbc에브리원 10주년 축하합니다 같은 느낌의 축하 영상느낌이었다.정지훈 나왔을 때가 진짜 뜬금없어서..
두 개의 네비게이션 문제 그래프가 주어지고 1번 회사에서 N번 집까지 가는동안 경보음을 최소로 듣는 경우를 구하는 것이다. 문제 풀이 먼저 출발지인 회사에서 집으로 가는 경로 들은 여러곳이 있을 것이다.dist[x] 를 x에서 부터 n까지 가는 최단거리라고 정의하자.그렇다면 현재 위치 u와 연결된 v들에 대해서 dist[v]+w(u,v) == dist[u] 라면 v는 u에서 가는 최단 경로이다.아니라면 v로 가면 경보음이 울리게 된다. 이와 같은 정리를 이용해서 아이폰과 안드로이드를 사용하였을 때 u->v의 경보음이 울리는지울리지 않는지 판별하면 된다.모든 위치 u와 그와 연결된 v에 대해서 위의 값을 구하고 새로운 그래프를 만든후 다시 한번 최단경로 알고리즘을 돌리면 된다. 약간 디테일한 구현 방법으로..
일기장으로 변해가는 알고리즘 블로그의 현황 8/24 ~ 8/25 기간 동안 삼성전자에서 대학생 우수 프로그래머 캠프를 진행하였다.대상자는 pro 등급 취득자(SW역량 평가 B형) 또는 icpc, koi 입상자를 대상으로 신청메일을 보내고 신청을 받아 진행된것 같다. 대략적으로 서울 R&D 센터에서 시작해서 인재개발원과 Digital City를 거쳐서 끝나게 되었다.크게 어떤것들을 했는지 설명해보자면 사업부별로 어떠한 일들을 하는지 대략적으로 설명해주는 세미나 시간들과 비교적 최근에 입사한 분들로 이루어진 멘토분들과 점심식사하고 커피를 마시면서 개인적인 질문들을 주고받는 시간들이 있었다. 보통 많이들 궁금해하는게 근무환경? 일듯 싶다. 다른 대기업은 어떤 근무환경인지 정확하게는 모르지만 삼성전자에서 크게 ..
8.17에 열린 SCPC 본선에 참가했다. 작년이랑 같은 장소에서 했고 올해는 키보드, 마우스, 장패드 기타 등등을 줬다. 키보드 예쁘다 ㅋㅋㅋㅋㅋ 이것 저것 줏어먹으면서 구경하다가 1시 반부터 본선을 시작했다. 4시간 동안 짱구를 열심히 굴려서 1, 2번을 풀고 3번 서브테케를 긁었다. 1번은 SCPC 2017 문제를 통틀어서 가장 쉬운문제가 아니었나 싶다.문자열에서 모음이 순서대로 나오는 최단길이를 구하고 그 중 가장 빠른 위치를 출력하는 문제였다.그냥 O(N^2)으로 구하면 된다. 128 명 본선에 참가한 것으로 아는데 125명이 풀었다. 2번은 2개의 볼록다각형이 있을 때 두 볼록 다각형간의 가장 짧은 거리를 구하는 문제이다.A 볼록다각형의 모든 점에서 B 볼록다각형의 모든 선분에 대해서 점과 선..
오늘은 카카오 코드 페스티벌이 있었다. 1시부터 7시까지 6시간 동안 6문제를 푸는 온라인 예선전이었다. 문제를 푸는 방식이 탑코더와 비슷하게 함수를 구현하는 방식이었다. 채점환경도 clang이고 약간 낯선 환경이었지만 뭐 크게 상관없었다. 6문제를 A, B, C, D, E, F로 보면 난이도는 A < B < E < D < F < C 순으로 보인다. C가 의외로 생각해줘야 하는 예외가 많고 F는 비교적 풀이만 생각해내면 구현은 어렵지 않을 것 같았다. 대회 결과는 { A,B,C,D,E } 5문제를 해결하였고, 아마도 본선에 진출할듯싶다. 간단하게 풀이를 적어보자면 A. 2차원 맵에서 색칠된 부분이 몇 개인지 최대로 색칠된 영역은 몇 칸인지를 구하는 문제였다. 간단한 2차원 플러드필 문제이다. B.2차원 ..
어제 scpc 2차 예선을 봤다.1번 문제 읽고 이건 나중에 풀어야겠다 싶어서 2번을 읽었다.열심히 오래 달리는 문제였는데 마침 이번 주에 확장된 유클리드 호제법 문제를 풀면서 디오판토스 방정식을 푸는 걸 정리해둬서 그걸 이용해서 풀었다.그리고 3번을 읽고 흐음 서브테케는 할 수 있을 듯 해서 다시 1번을 돌아가 1번을 제대로 읽고 점화식을 조금 적어보니까 6가지 상태에서 (A->B, A->C, B->C, B->A, C->B, C->A) 마지막 단어에 대한 정의가 내려지기에 그걸 이용해 풀었다.다시 3번을 대충 O(240(n+m)logn) 복잡도에 풀어서 냈는데 아무래도 해쉬맵을 이용하고 복잡도 자체가 너무 크기에 불가능한 방법이었던 것 같다. 47점을 긁고 10번 제출이 끝날 때까지 이런저런 최적화를 ..
이제 scpc도 3년 차!1, 2, 4번은 오전에 문제 읽고 풀이가 바로 떠올라서 오후에 바로 구현하였고3번은 처음에 2-sat인가 했지만 2-cnf식이 안 떠올라서 고민하다가 2-cnf식으로 변형이 되어서 2-sat으로 풀었다.5번은 정말 도통 몰랐는데 6명 정도 만점을 받은 것 보니 갓 문제였던 것 같고 더 공부해야겠다!! 1번은 스택을 이용해서 풀었고2번은 그리디를 이용했는데 반밖에 증명을 안 했다 더 생각 해봐야겠다.3번은 전구가 켜저있거나 꺼져있을 때에 따라 스위치들의 2-cnf식을 세울 수 있고 따라서 2-sat으로 풀 수 있다.4번은 주어진 단순다각형을 단조 다각형으로 판별할 수 없는 방향벡터 d의 범위는 오목 꼭짓점에서 정의 될 수 있다.따라서 모든 오목 꼭짓점에서 안되는 범위들을 모으고 ..
본인이 PS를 하면서 자주 사용하는 STL들을 정리하겠습니다. 1. vector동적배열이다. 임의의 위치에 있는 원소 접근과, 뒤에서 원소를 추가하는 연산은 O(1)(분할상환분석)을 보장한다. 2. stack스택 자료구조이다. 3. queue큐 자료구조이다. 4. deque동적배열이다. 임의의 위치에 있는 원소 접근과, 앞과 뒤에서 원소를 추가하는 연산은 O(1)을 보장한다. 5. set균형잡힌 이진트리이다. 원소 삽입과 삭제, 탐색 등의 연산은 O(logn)을 보장한다. 6. pair2개의 데이터를 저장할 수 있는 변수이다. 비교 연산시 1순위 first 2순위 second로 판별한다. 7. map딕셔너리 자료구조이다. 원소 삽입과 삭제, 탐색 등의 연산은 O(logn)을 보장한다. 8. algorit..
** 본문은 C에 대한 기본적인 이해가 있음을 가정하고 작성하였습니다. 기본적으로 a+b연산을 하는 코드는 다음과 같다. 헤더파일은 C의 헤더파일을 모두 사용할 수 있고 거기에 추가적으로 stl 컨테이너들도 사용할 수 있다.using namespace std; 문장은 c++에서 사용되는 문법으로 이름공간중 std라는 이름공간을 그냥 사용하겠다는 뜻이다.이 문장이 없다면 std 이름공간에 포함된 cin이나 cout함수는 std::cin과 std::cout 등과 같은 방법으로 사용해야 한다.이러한 타이핑의 귀찮음을 없애기 위해 위 문장을 헤더파일 밑에 선언한다. 헤더파일은 cin, cout 등 c++에서의 기본 입출력 함수및 기타 등등을 포함하는 기본적인 헤더파일이다.cin은 입력 함수이다. 별도의 입력타입..