2007/11/12 월요일
ㅋ nhn 기술 면접에서 떨어졌다. 머 실무경험이 거의 전무하다 보니 예상은 했지만, 좀 웃기다. ACM/ICPC 특전으로 주어진데서, 알고리즘 말고 실무 경험을 보다니, 그리고 면접관들이 ACM/ICPC가 먼지도 모르고, 토론에서도 솔직히 내가 제일 논리적이고 적당히 이야기했다고 생각하는데, 경력이 안되는건가? 쩝...아~~
'2007/11/12'에 해당되는 글 10건
- 2007/11/12 2007/11/12 월요일
- 2007/11/12 티스토리에서 프로그래밍 코드를 넣자
- 2007/11/12 티스토리에서 수식을 사용하자
- 2007/11/12 NCPC 2002
- 2007/11/12 NCPC 2003
- 2007/11/12 NCPC 2004
- 2007/11/12 NCPC 2005
- 2007/11/12 NCPC 2006
- 2007/11/12 NCPC 2007 (2)
- 2007/11/12 2007/11/11 일요일
NCPC 2002
http://www.ida.liu.se/projects/progcontest/progsm/2002/
- A
예전 예선 금고 문제와 유사한데, 조금더 생각해줘야 함.
우선 높이가 1일때, 금고가 1개 있을때는 다 구해준다.
d[k][m][t] 는 i번째 터트렸을때 터지면 밑을, 안터지면 위를 생각하면 되므로 아래와 같다. 그러나 위를 구할때는 최초 1개가 아닌 i+1개를 터트려야 하므로 t라는 변수를 추가했다.
d[k][m][t] = min(i = 2 ~m-1)( t + i + max(d[k-1][i-1][t], d[k][m-i][t+i])이다. (여기서 t는 밑에 t개를 놓았을때의 경우이다. t+i는 최대 쿠키의 개수보다 작거나 같아야 한다)
t는 내림으로, k와 m은 오름으로 구하면 된다.
실수: 2개중 큰것은데 처음에 더한걸로 구했다..ㅡㅜ
- E
다해봤다. 브랜치엔 바운드로 이걸로 하면 안되겠다. 중복만 제거해도 상당히 효과가 있다.
E.cppNCPC 2003
http://www.ida.liu.se/projects/progcontest/progsm/2003/
- B
네트워크 플로우다. ㅡㅜ 왜몰랐을까. 네트워크 lower 이다.
스타트 노드와 행노드와 행sum만큼의 capacity로 연결해주고, 열노드와 엔드노드를 열sum만큼의 capacity로 연결해주면 된다. 그리고 행과 열은 주어진 조건에 따라 >k 이면 leowr를 k+1만큼 < k 이면 capacity를 k-1 만큼 =k이면 capacity와 lower를 k로 설정에서 돌리면 된다.
- D
약간 짜증나는 문제. O(n*m)인거 같다. 우선 k(1~9999까지)의 역수를 (1/k)를 저장한후 각 테스트케이스 마다 n과 t(확률중 가장 작은것과 곱해서 100 이상 - 1 : 오차때문에)를 구한후 큰것부터 ~m까지 루프(i)를 돈다.
각 확률의 round범위(예로 3.4는 3.35 <= x < 3.45)를 1/k의 배수로 가능하지 않으면 다음 i로 넘어간다. 아니면 그값을 저장한다. i에서 다만족하더라도, 계산된 확률의 값이 100%가 되지 않으면 넘어간다.(여기서 문제는 round범위에 여러개가 있을경우등을 생각하면 어려울듯...ㅡㅜ & 오차까지 생각해줘야 한다)
- G
각으로 구해서 해당길이(각의 사이를) 다 만족하는 특정각의 값이 최소가 되는것을 구하면 된다.
근데 어떻게 구하지???ㅡㅜ
- A번
디짓을 세서 출력하는것. 어렵지는 않은데 입력 받는게 짜증남
- B
네트워크 플로우다. ㅡㅜ 왜몰랐을까. 네트워크 lower 이다.
스타트 노드와 행노드와 행sum만큼의 capacity로 연결해주고, 열노드와 엔드노드를 열sum만큼의 capacity로 연결해주면 된다. 그리고 행과 열은 주어진 조건에 따라 >k 이면 leowr를 k+1만큼 < k 이면 capacity를 k-1 만큼 =k이면 capacity와 lower를 k로 설정에서 돌리면 된다.
- D
약간 짜증나는 문제. O(n*m)인거 같다. 우선 k(1~9999까지)의 역수를 (1/k)를 저장한후 각 테스트케이스 마다 n과 t(확률중 가장 작은것과 곱해서 100 이상 - 1 : 오차때문에)를 구한후 큰것부터 ~m까지 루프(i)를 돈다.
각 확률의 round범위(예로 3.4는 3.35 <= x < 3.45)를 1/k의 배수로 가능하지 않으면 다음 i로 넘어간다. 아니면 그값을 저장한다. i에서 다만족하더라도, 계산된 확률의 값이 100%가 되지 않으면 넘어간다.(여기서 문제는 round범위에 여러개가 있을경우등을 생각하면 어려울듯...ㅡㅜ & 오차까지 생각해줘야 한다)
- G
각으로 구해서 해당길이(각의 사이를) 다 만족하는 특정각의 값이 최소가 되는것을 구하면 된다.
근데 어떻게 구하지???ㅡㅜ
NCPC 2005
http://ncpc.idi.ntnu.no/ncpc2005/
- B
win과 lose 인터벌 구하는것은 맞는데 어떤지는 모르겠음...ㅡㅜ
- C
전체적인 틀은 맞았는데, 바꿔주는 세부적인 것을 생각 못했슴..ㅡㅜ
- G
네트워크 플로우로 필요한 군인의 수를 알수 있다.
최소 거리는 ?? 조금 생각해봐야 할듯
- I
기하문제라고 착각할수 있음
계산이 맞았음. 그러나 변수가 long long int등의 변화로 값이 달라지는걸 생각 못함.
이럴경우에는 알고리즘이 잘못됐다고 생각할수 있기 때문에 조심해야 한다.
NCPC 2006
http://ncpc.idi.ntnu.no/ncpc2006/
- G
다이나믹 문제이다. 사실 문제가 확실히 않됐다. 한 시간단위에 여러곳을 움직일수 있다라고 생각했는데, 한 방향으로만 움직일수가 있다. 이렇게 돼면 해답처럼 다이나믹이 가능할거 같다.ㅋ
- H
생각을 조금 다르게 했다.
나는 d[i][j] = (더하기 d[i인근][j-1]) /i의 에지수를 했는데, 더하기(d[i인근][j-1]/i인근의 에지수) 가 맞다. 왜그렇게 생각한 걸까.
원하는 값은 결국 각각의 이동(1~k)번째 마다 한 출력의 한비트씩 보면서(전체를 다본다) 건을 만족하지 않는게 있으면 No, 전부 만족하면 Yes를 출력한다.
- G
다이나믹 문제이다. 사실 문제가 확실히 않됐다. 한 시간단위에 여러곳을 움직일수 있다라고 생각했는데, 한 방향으로만 움직일수가 있다. 이렇게 돼면 해답처럼 다이나믹이 가능할거 같다.ㅋ
- H
생각을 조금 다르게 했다.
나는 d[i][j] = (더하기 d[i인근][j-1]) /i의 에지수를 했는데, 더하기(d[i인근][j-1]/i인근의 에지수) 가 맞다. 왜그렇게 생각한 걸까.
원하는 값은 결국 각각의 이동(1~k)번째 마다 한 출력의 한비트씩 보면서(전체를 다본다) 건을 만족하지 않는게 있으면 No, 전부 만족하면 Yes를 출력한다.
NCPC 2007
http://ncpc.idi.ntnu.no/ncpc2007/
- G번
데이터를 높이순으로 감소시키고,(높이가 같다면 넓이가 큰것으로) 정렬시킨다.
그다음 1번부터 순서대로 돌면서 이미 돈 좌표에서 마지막에 연결시킨다(최대한 넓이가 작은것으로, 같다 면 넓은것을 먼저 선택). 마지막의 저장점은 은 벡터로 하면 되고 정렬시킬 필요는 없다.(자동적으로 정렬 만약 새로은 좌표가 저장되면 해당 인덱스를 새로운 좌표로 수정한다. 그리고 연결되지 않으면 해당 벡터에 추가 시키면 된다. 다돈후 저장점 벡터의 길이를 출력하면 된다.
이렇게 되는 이유가 해답에 나와 있는데, 설명이 약간 어렵게 된거 같다.
모순으로 증명한다. 최적의 해가 위의 방법과 다른 선택을 하는 가장 작은 순서를 d라고 하고, 위의 방법으로 선택한 것을 dlow라 하고, 최적의 해가 선택하는 것을 dopt라고 하자. 여기서 우리가 알수 있는것은 넓이는 dlow <= dpot이다.
여기서 최적의 해에서 dlow에 연결되는 좌표가 있을수도 있고 없을수도 있다. 없다면 d를 dlow에 연결시킨다.(연결된후의 큰것들은 신경쓰지 않아도 된다.) 만약 있다면(dwrong이라 하자) dwrong과 dopt를d와 dlow를 연결시키자.(dwrong의 넓이는 dlow보다 작으므로 dopt보다 작다.) 이렇게 하면 결국 우리의 선택은 최적해와 같게 된다.
또다른 방법
http://en.wikipedia.org/wiki/Dilworth%27s_theorem
- I (moogle)
다이나믹 문제다.
최초 생각은 d[시작점][끝점][저장할개수]로 다이나믹으로 풀었다.
저장개수 -> 시작점 -> 끝점 -> d[시작][중간][i] + d[중간][끝][저장개수 - i +1]중 가장 작은것 구했는데(O(n^4)), 해설을 보니 굳이 이렇게 할 필요가 없다. d[0][중간][저장개수-1] + d[중간][끝][2]중 가장 작은걸로 구하면 된다(O(n^3))
거의 맞는데 몇개의 테스트 케이스에 대해서 조금의 오차가 생기는데 왜그런지..ㅡㅜ
(이유는 모두다 저장하는 경우를 0으로 초기화 하지 않아서이다..ㅡㅜ)
2007/11/11 일요일
제길 잠이 안온다. 이럴때는 블로그나 관리할까? ㅋ
논문 논문 논문 미치겠네..ㅋ 그냥 베껴서 내버려??ㅋㅋ
논문 논문 논문 미치겠네..ㅋ 그냥 베껴서 내버려??ㅋㅋ
